AVL 트리
AVL : 높이 균형 이진 트리- 트리 전체를 재 균형 시키지 않고도 트리의 균형 유지
- 삽입, 삭제 연산 시간이 짧음
- 검색시간 : O(logN)
- 왼쪽 / 오른쪽 서브트리의 높이 차 <= 1
- AVL 트리는
메인 메모리에 거주하는 내부 구조로
트리 크기가 너무 커서 메인 메모리에 구축할 수 없을 경우
–> 균형 m-원 탐색 트리
AVL 삽입
-
삽입되는 위치에서 루트로의 경로에 있는 조상 노드들의 균형인수에 영향을 줄 수 있음
-
불균형이 탐지된
가장 가까운 조상 노드의 균형인수를 ± 1 이하로 재 균형 시켜야 함
AVL 삽입 예
