Gidhub BE Developer

AVL 트리

2018-06-13
goodGid

AVL 트리

  • AVL : 높이 균형 이진 트리
    • 트리 전체를 재 균형 시키지 않고도 트리의 균형 유지
    • 삽입, 삭제 연산 시간이 짧음
    • 검색시간 : O(logN)
    • 왼쪽 / 오른쪽 서브트리의 높이 차 <= 1
    • AVL 트리는 메인 메모리에 거주하는 내부 구조로
      트리 크기가 너무 커서 메인 메모리에 구축할 수 없을 경우
      –> 균형 m-원 탐색 트리

AVL 삽입

  • 삽입되는 위치에서 루트로의 경로에 있는 조상 노드들의 균형인수에 영향을 줄 수 있음

  • 불균형이 탐지된 가장 가까운 조상 노드의 균형인수를 ± 1 이하로 재 균형 시켜야 함


AVL 삽입 예


Recommend

Index