이진탐색트리 - AVL 트리

AVL 트리

---

AVL 트리는 이진탐색트리의 한 종류로

편향된 트리구조가 나올 수 있는 이진탐색트리를 균형을 유지하도록 하여 시간복잡도가 평균 O(logN)을 유지하도록 한 트리이다.

 

AVL 트리는 균형을 유지하기 위해 회전연산을 수행한다.

LL 회전, RR 회전, LR 회전, RL 회전이라고 불리우는데, 회전 연산의 핵심 원리는 중간 값이 루트 노드가 된다는 것이다.

LL, RR 등등은 노드의 왼쪽, 오른쪽 위치로 인해 붙여진 이름의 차이일 뿐,

원리는 모두 할아버지, 부모, 자식이 있을 때, 중간 값이 루트가 되고 나머지 두 노드는 크기에 따라 왼쪽, 오른쪽에 위치하게 된다.

 

BF(Balanced Factor, 균형인수)

---

균형인수(BK) = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이

균형인수는 AVL 트리가 트리의 균형을 유지하기 위해 사용하는 기준이다.

위의 그림에서 루트 노드의 왼쪽 서브트리의 높이는 3이고, 오른쪽 서브트리의 높이는 1이다.

균현 인수를 구해보면 3-1=2가 된다.

AVL 트리는 균형인수가 -1, 0, 1이 아닌 경우 연산을 수행하여 균형을 유지한다.

균형 인수가 -1, 0, 1만 허용되므로 왼쪽 서브트리와 오른쪽 서브트리의 높이차가 최대 1을 넘어서지 않는다는 것을 의미한다.

AVL 트리는 매우 엄격한 균형을 유지하는 트리이다.

 

회전연산

---

LL 회전

왼쪽 자식이 왼쪽 서브트리를 가지는 LL 케이스 (Left-Left)가 발생하여 BF>1 이 발생하는 경우, 회전연산을 수행한다.

왼쪽 자식 노드가 새로운 루트가 되고, 기존의 루트 노드는 왼쪽 자식 노드의 오른쪽 자식이 된다.

이진 탐색 트리에서 왼쪽은 오른쪽보다 작으므로 중간값에 해당하는 노드가 중간으로 위치하는 것이다.

 

RR 회전

오른쪽 자식이 오른쪽 서브트리를 갖는 RR 케이스가 발생하는 경우 BF<-1이 발생하여, 회전연산을 수행한다.

오른쪽 자식노드가 루트노드가 되고 나머지 해당 노드는 왼쪽, 손자 노드는 오른쪽에 위치하게 된다.

동작원리는 마찬가지로 크기에 따라 중간 값이 루트 노드가 되는 것이다.

 

LR 회전

왼쪽 서브트리가 오른쪽 서브트리를 갖는 LR 케이스가 발생한 경우이다.

이때는 손자 노드가 중간 값이므로 손자 노드와 자식 노드에 대회 LL 회전을 수행하고, 그 이후 RR 회전을 수행한다.

이중 회전 연산을 수행하는 경우이다.

 

RL 회전

오른쪽 자식 노드가 왼쪽 서브트리를 갖는 경우이다.

마찬가지 원리로 손자 노드에 대해 오른쪽 회전 연산 수행 후 왼쪽 수행 연산을 수행한다.

 

삽입과 삭제 연산에 위와 같은 회전 연산이 수행되어 트리의 균형을 유지한다.