• AVL 트리
• AVL 삽입
• AVL 삽입 예

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

AVL 삽입

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

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

AVL 삽입 예