Chap12. 균형 잡힌 이진 탐색 트리, AVL 트리
이진 탐색 트리의 단점
앞서 공부했던 이진 탐색 트리는 (https://tose33.tistory.com/654) 단점이 있다.
이진 탐색 트리의 데이터 탐색의 시간복잡도는 트리의 높이에 해당하기 때문에 데이터가 N개일때 O(logN)인데, 트리의 균형이 맞지 않을수록 O(N)에 가까워 진다.
다음과 같이 1부터 5까지의 숫자를 순서대로 삽입한 이진 탐색 트리를 생각해보자
1
\
2
\
3
\
4
\
5
위 이진 탐색 트리의 높이는 5로 탐색 시간은 O(N)이 되버린다.
하지만 아래와 같이 3을 먼저 삽입한 후에 순서대로 숫자를 삽입하면 높이는 3이 된다.
3
/ \
1 3
\ \
2 5
이런 이진 탐색 트리의 단점을 개선한 트리를 균형 잡힌 이진 트리라고 하고 여러 종류가 있는데 다음과 같다
AVL, 2-3, 2-3-4, Red-Black, B 트리
AVL 트리
AVL 트리는 균형잡인 이진 탐색 트리의 한 종류이며 G. M. Adelson-Velskii와 E. M. Landis에 의해 고안된 트리이며 이들의 이름을 따서 이름도 정해졌다.
AVL 트리는 트리의 균형의 정도를 표현하는 균형 인수라는 것을 계산해서, 균형을 잡기위해 트리를 재조정하는 리벨런싱을 진행한다.
균형 인수의 공식은 다음과 같다.
균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이
따라서 균형 인수의 절댓값이 클 수록 균형이 무너진 상태인것을 알 수 있다.
AVL 트리는 균형 인수가 2 이상인 경우에 리벨런싱을 진행한다.
AVL 트리의 균형이 무너지는 상태는 4가지가 있고, 이 균형이 무너진 상태를 리벨런싱하는데도 각기 다른 방법이 있다.
1. LL상태와 LL회전
다음과 같이 균형인수가 +2인 상태를 LL상태라고 한다.
5
/
3
/
1
이 경우 루트 노드인 5를 보면, 자식 노드 두 개가 왼쪽으로 연이어 연결되어 균형인수가 2가 된다.
그리고 이런 LL 상태에서 발생한 불균형을 해소하는 리벨런싱 방법이 LL 회전 이다.
3
/ \
1 5
그런데 만약 트리가 다음과 같다고 생각해보자.
5
/ \
3 T4
/ \
1 T3
/ \
T1 T2
T1~T4는 높이가 동일한 서브트리이다.
이 경우 이 서브트리들은 노드 3과 노드 5의 균형 인수에 영향을 미치지 않는다.
왜냐하면 균형인수의 식은 균형인수 = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이기 때문이다.
따라서 위 트리도 LL 상태의 트리이다.
위 트리의 불균형을 해소하기 위해 마찬가지로 LL 회전이 필요한데, 이 경우 문제가 있다. 바로 T3 서브트리 의 존재다.
LL 회전을 하려면 노드 3의 오른쪽 자식이 노드 5가 되어야 할텐데, 노드 3은 이미 오른쪽 자식이 있다.
그런데 만약 T3 서브트리가 없다고 생각하고 LL 회전을 진행하면 T3이 들어갈수 있는 자리가 보이는데 바로 노드 5의 왼쪽 자식이다.
3
/ \
1 5
/ \ / \
T1 T2 T3 T4
위의 사진을 보면 LL 회전을 Right Rotation이라고 해서 착각하기 쉬운데 회전하는 노드 (여기서는 50)이 오른쪽 방향으로 회전하기 때문에 LL 회전은 곧 Right Rotation을 의미한다.
2. RR 상태와 RR 회전
LL 상태가 왼쪽으로 길게 늘여진 상태라면 RR 상태는 방향만 반대로 오른쪽으로 늘여진 상태고,
RR 회전은 마찬가지로 RR 상태의 불균형을 해소하기 위한 회전이다.
3. LR 상태와 LR 회전
LR 상태는 자식 노드가 왼쪽, 그리고 오른쪽에 있는 상태이다.
5
/
1
\
3
LR 회전은 부분적인 LL 회전과, 부분적인 RR 회전으로 이루어진다.
먼저 RR 회전의 결과를 생각해 보자.
위 RR 회전 (Left Rotation)에서 노드 80이 없다고 생각해보면 RR 회전의 결과는 다음과 같다.
1. 부모 노드인 50과 자식 노드인 70의 관계가 바뀌었다. (70이 부모노드, 50이 자식이 되었다.)
2. 오른쪽으로 형성되있던 자식의 관계과 왼쪽으로 바뀌었다. (50의 오른쪽 자식이 70이었는데, 70의 왼쪽 자식이 50이 되었다)
이러한 RR 회전을 이용하면 LR 상태를 LL 상태로 만들수 있고, 그 이후로는 LL 회전을 해서 불균형을 해소하면 된다.
LR 상태 -> RR 회전 수행 -> LL 상태 -> LL 회전
4. RL 상태와 RL 회전
RL 상태도 마찬가지로 LR 상태와 반대되는 상태이고, 그 불균형의 해소도 LR 회전과 반대된다.
RL 상태 -> LL 회전 수행 -> RR 상태 -> RR 회전