AVL 트리는 Balanced Binary Search Tree이다. AVL 트리는 각각 노드마다 왼쪽, 오른족 서브트리의 높이 차이에 대한 정보를가지고 서브트리의 높이 차이가 1보다 크지않다는 성질을 가진다.(위키피디아 )
즉, 양쪽 서브트리의 높이 차이가 1이하이다.
균형잡힌 AVL 트리는 n개의 원소가 있을 때 O(logn)의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다.
시간 복잡도
평균
최악의 경우
Rotation
트리의 재구성 작업을 Rotation(회전)이라고 한다.
LL
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
y는 z의 왼쪽 자식, x는 y의 왼쪽 자식이다. 이때 T1, T2, T3, T4는 각각의 서브트리이다.
z의 오른족 자식과 왼쪽 자식이 불균형하므로 right Rotation 한번으로 균형을 잡아줄 수 있다.
if (bal >1&& key < node->left->key) returnright_rotate(node);
LR
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
y는 z의 왼쪽 자식, x는 y의 오른쪽 자식이다. 이러한 경우에는 회전을 두번시켜줘야한다. 우선 y를 왼쪽 회전을 한번 시켜주고 z를 오른쪽 회전시켜주면 균형이 잡히게 된다.
if (bal >1&& key > node->left->key){node->left =left_rotate(node->left);returnright_rotate(node);}
RR
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
y는 z의 오른쪽 자식이고, x는 y의 오른쪽 자식이다. 이러한 경우는 LL과 마찬가지로 한번의 rotation으로 균형을 잡을 수 있다.
if (bal <-1&& key > node->right->key) returnleft_rotate(node);
RL
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
y는 z의 오른쪽자식, x는 y의 왼쪽 자식이다 .이러한 경우는 위의 LR과 정 반대인 경우이다. 이 때는 오른쪽 회전 후 왼쪽 회전을 하면 균형을 맞출 수 있다.
if (bal <-1&& key < node->right->key){node->right =right_rotate(node->right);returnleft_rotate(node);}