AVL 트리 (심화) - 더블 로테이션

이 글은 기본적인 AVL 트리에 대해 알고 있는 사람들을 위한, 좀 더 심화 버전의 글이다. 또는 AVL 트리를 조금 공부했지만 헷갈려서 정리가 필요한 사람을 위한 글이 될 수도 있다.

 

AVL 트리는 컴퓨터 전공 대학생이나 개발 분야로 취직하고자 하는 사람들은 흔히 공부를 하는 주제이다. 보통 LL, RR, RL, LR 등의 상황에서 왼쪽 회전, 오른쪽 회전 등을 공부하였을 것이다. 하지만 여기서 우리는 조금 다른 표현을 쓴다. AVL이라는 개념이 처음 나왔을 때 없었던, 후세에 연구되어 좀 더 개선된 방식이다.

 

기존에, 우리는 아래와 같은 로테이션을 공부하였다. (이 부분은 그냥 훑고 지나가자) 오른쪽에 있던 2가 왼쪽 위로 올라가면서, 1이 왼쪽 아래로 내려가는 상황을 Left Rotation이라고 부른다. 그리고 그 반대는 Right Rotation이다.

그래서 우리는 아래와 같이 지그재그 형태로 Unbalance한 트리를 바로잡는 규칙으로써, 1을 기준으로 Left 로테이션 한번, 3을 기준으로 Right 로테이션 한번이 이루어진다. left_rotation(1) --> right_rotation(3)

 

 

그런데 이게 알고리즘으로는 나름 명확히 나오긴 하지만 사람이 직관적으로 이해하긴 꽤나 까다롭다. 그림으로 보면 리프에 있던 "2"가 한칸씩 위로 올라가고 있는 형상인데, 우리가 함수 인자로 사용하는 노드는 그 부모인 "1",  "3"이기 때문이다.

 

그래서 이게 불편했던 연구자들이 그냥 left_rotate, right_rotate 함수를 하나의 rotate 함수로 합쳐 버렸다. 회전의 축이되는 부모가 아니라 실제로 부모 자리로 이동하는 이동 주체를 인자로 하는 것이다. 기존 함수와 대응을 시키자면 아래와 같다.

 

left_rotate(u) = rotate(u.left)

right_rotate(u) = rotate(u.right)

 

하지만 우리는 그냥 편하게, 왼쪽이든 오른쪽이든 무관하게 "올라가는 놈"을 인자로 잡고 함수를 사용하면 된다. 즉 위의 경우엔 rotate(2), rotate(2) 이렇게 두번 수행하는 것이다. 시각 적으로도 "2"를 올려야 하는 상황이니 더 이해하기 편하다. 여기서 우린 좀 더 효율을 추구하기 위해 더블 로테이션이라고 하는 rotate2(2)라는 개념까지 사용할 수 있다. 인자가 동일하게 유지되기 때문에 가능해지는 것이다.

 

다른 예를 들어 보겠다.

 

 

이러한 그래프가 있다고 하자. 지금은 균형이 잡힌 AVL 그래프이다. 하지만 여기서 8을 삭제하면?

 

 

불균형해진다. 우선은 10 왼쪽의 서브트리가 그 자체로 불균형하므로, 고쳐보자.

여기서 우리는 4가 7자리의 루트로 올라가야 한다는 것을 안다. 기존에는 2을 중심으로 Left Rotate 시키고 그 다음 7을 중심으로 Right Rotate시켰지만, 여기서는 그냥 4를 두 칸 올리기 위해 Rotate2(4) 라고 하여 더블 로테이션을 수행한다. 이렇게 하면 레프트, 라이트 고민할 필요 없이 그냥 4가 7자리로 올라가고, 서브트리 자체의 불균형은 해소된다.

 

 

하지만 이 트리는 루트인 10을 기준으로 전체적인 균형이 어긋났다. 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 2 이상이 나기 때문이다. 꽤나 까다로운 상황인데, 오른쪽에 있는 15를 루트로 올려야 한다. 기존 방식대로라면 20을 기준으로 라이트 로테이션을 수행하고, 10을 중심으로 레프트 로테이션을 해야 할 것 같다. 하지만 여기서 더블 로테이션을 이용한다면 우리는 다시 15를 바로 타겟으로 잡고 Rotate2(15)를 수행한다.

 

하지만 문제는 노드 15는 이미 하위 서브트리를 가지고 있기에 이 자식놈들을 어떻게 처리해야 하는지가 헷갈리는 것이다.

 

 

이럴 때 사용할 수 있는 규칙이 위와 같다. 이는 이미 증명이 된 규칙이니 그대로 적용하면 된다. 여기서 우리가 신경써야 할건 10(w), 20(v), 15(u) 세가지 뿐이다.

 

 

그리고 그 아래에 있던 서브트리들은 새로운 부모에 그대로 같은 순서로 배치시켜 주면 신기하게도 균형이 맞는다. 여기서 쿨한 점은 조상 입장의 u v w를 직관적으로 재배열한 뒤, 그 아래의 서브트리들은 그냥 그대로 위치를 유지시키고 바뀐 조상이랑 연결만 시켜주면 깔끔하게 규칙이 맞는다는 것이다. 물론 이 또한 트리의 특성을 생각하면 너무 당연한 것이긴 해도 말이다.