앞서 본 이진 탐색 트리는 아주 좋은 구조이지만 단점도 존재한다.
일반적으로 이진 탐색 트리의 탐색 연산은 의 시간 복잡도를 가지고, 트리의 높이를 더해질수록 노드의 수가 두 배씩 증가한다.
하지만 이진 탐색 트리는 균형이 맞지 않을 경우 에 가까운 시간 복잡도를 보인다.
위 그림은 1부터 5까지의 정수가 순서대로 저장되었을 때의 이진 탐색 트리이다. 이는 이진 탐색 트리의 조건을 만족하지만, 트리의 높이는 노드의 수에 맞게 생성되었다.
하지만 정수 3이 먼저 저장되기만 해도 결과가 아래 그림과 같이 달라진다
저장 순서만 달라져도 루트 노드를 기준으로 균형이 잡힌 트리의 모습을 볼 수 있다.
이와 같이 이진 탐색 트리는 저장 순서에 따라서 탐색의 성능에 큰 차이를 보이는 점이 이진 탐색 트리의 단점이다.
이진 탐색 트리의 단점을 해결한 트리를 균형 잡힌 이진 트리라 부르고 종류는 아래와 같다.
- AVL 트리
- 2-3 트리
- 2-3-4 트리
- Red-Black 트리
- B 트리
중 AVL 트리를 통해 이진 탐색 트리가 자동으로 균형 잡는 것을 공부한다.
AVL 트리
AVL 트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형 상태를 파악해서 스스로 균형을 잡는 트리이다.
AVL 트리에서 균형의 정도를 표현하기 위해 균형 인수(Balance Factor)를 사용한다.
균형 인수의 계산은 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이를 통해 도출해 낼 수 있다.
위 그림이 각 노드별 균형인수이다.
균형을 잡기 위한 트리 구조의 재조정을 AVL 트리의 리밸런싱(rebalancing)라고 한다.
균형 인수의 절댓값이 클 수록 트리의 균형이 무너진 상태이다. 따라서 AVL 트리는 균형 인수의 절댓값이 2 이상인 경우에 균형을 잡기 위한 리밸런싱을 진행한다.
리밸런싱이 필요한 네 가지 상태
AVL 트리의 균형이 무너지는 상태는 4가지로 정리된다. 그리고 각 상태별로 리밸런싱 하는 방법에도 차이가 있다.
첫 번째 LL회전
그림을 보면 루트 노드를 기준으로 왼쪽에 정수 3이 저장된 자식 노드, 그 자식 노드 아래에 정수 1이 저장된 자식노드가 연달아서 연결되어있고, 균형 인수 +2가 연출되었다.
균형 인수 +2가 연출된 상태를 가르켜 'Left Left 상태' 줄여서 LL상태라고 한다.
LL상태에서 발생한 불균형을 해소하기 위한 리밸런싱 방법을 LL회전이라고 한다.
위 그림은 LL상태를 일반화한 것이다. T1, T2, T3, T4를 높이가 동일한 서브트리라고 가정한다면 이들은 기존의 노드에 영향을 미치지 않는다 그리고 값을 NULL로 치환하면 처음 LL상태의 모습을 보인다.
두 번째 RR회전
RR회전은 LL회전과 비교했을 때 다른 점은 방향이다.
LL상태가 왼쪽으로 길게 늘어진 모습이라면, RR상태는 오른쪽으로 길게 늘어진 모습이고
LL회전이 LL상태를 균형잡기 위한 회전을 의미한다면, RR회전은 RR상태를 균형잡기 위한 회전이라고 생각하면 된다.
세 번째 상태 LR회전
LR회전은 LR상태를 균형잡기 위한 회전이다.
LR회전은 다음과 같은 모습을 보인다.
위 그림이 간단한 LR상태를 나타내고 있다.
LR상태는 LL상태나 RR상태에 비해 균형을 잡기가 복잡하다. 그 이유는 한 번의 회전으로 균형을 잡을 수 없기 때문에 LL상태 또는 RR상태로 바꾼 후 균형을 잡아주어야 한다.
LL상태 혹은 RR상태로 변경하기 위해서는 알아야하는 RR회전, LL회전의 특징은 아래와 같다
처음 그림의 RR상태가 있다고 했을 때, 9를 NULL로 치환하고 RR회전을 진행하면
다음과 같은 그림이 된다.
그럼 위를 과정을 통해 아래 상황도 가능한 것을 알 수 있다.
위 와 같은 특징을 사용해 LR상태(or RL상태)를 LL상태(or RR상태)로 변경하고 균형을 잡는 과정으로 정리할 수 있다.
