AVL 트리

Adelson-Velskii and Landis Tree

트리내 각각의 노드마다 1 이하의 균형치(Balance Factor, +1,0,1)를 가지기 위해, 삽입과 삭제를 할때마다 균형치를 검사하여 RR, LL, LR, RL 회전연산을 시행하는 이진탐색트리

• 발표자인 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 이름을 따서 명명

특징

• 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리
• 이진 트리의 삽입·삭제 과정에서 한 방향으로 치우치거나, 높이 차이로 인해서 수행 시간이 증가되는 것을 막기 위해 균형 유지
• B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림

회전 동작

개요

• LL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전
• LR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전
• RL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전
• RR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전

동작 예시

• LL 회전

• LR 회전

• RL 회전

• RR 회전

같이 보기

• B 트리
• B+ 트리
• B- 트리
• B* 트리
• AVL 트리
• T 트리
• R 트리
• 비트맵 인덱스