[자료구조] AVL트리란?

 

이진탐색트리의 이상적인 모습은 아래와 같다. 이를 균형이진트리라고 한다. 부모 노드의 왼쪽 자식은 부모보다 값이 작고 오른쪽 자식은 부모보다 값이 크다. 이 규칙은 깨지지 않는다.

 

그러나, 아래와 같은 불균형이진트리도 이진탐색트리의 일종이다.

 

한쪽으로 치우쳐진 모양의 이진트리를 경사이진트리라고 한다. 경사이진트리는 삽입, 삭제, 탐색 등 모든 경우에서 최악의 시간 복잡도를 갖기 때문에 불균형이진트리를 균형이진트리로 만들어주는 방법이 고안됐는데 그중 하나가 ✅AVL트리이다.

 

AVL트리에서 모든 노드의 양쪽 서브트리의 높이 차는 -1, 0, 1 중 하나다. 

이때 BF가 노드 양쪽 서브트리의 높이차를 말한다. 

이때 그래프가 위와 같은 모양이 되면 노드 20과 30의 입장에서 BF 값이 2가 된다. 즉, AVL 트리가 깨지게 된다. 이 트리를

 

AVL 트리로 맞추기 위해서는 문제가 일어난 노드를 기준으로 회전이라는 것을 해야 한다. 

AVL 트리가 기준에서 벗어난 경우에는 4가지 종류가 있다. LL(Left-Left), LR(Left-Right), RR(Right-Right), RL(Right-Left)이다.

 

 

✅ LL(Left-Left)

 

BF 값이 -1, 0, 1이 아닌 노드를 기준으로 왼쪽 자식 노드 깊이가 2개인 경우를 말한다. 

 

이를 해결하기 위해서는 오른쪽으로 회전이 필요하다.

 

 

중간 값을 가지는 20이 부모 노드가 되고 남은 두 노드는 값에 따라 왼쪽, 오른쪽 자식 노드가 된다.

 

 

✅ RR(Right-Right)

 

BF 값이 -1, 0, 1이 아닌 노드를 기준으로 오른쪽 자식 노드 깊이가 2개인 경우를 말한다. 

 

이를 해결하기 위해서는 왼쪽으로 회전이 필요하다.

 

 

중간 값을 가지는 20이 부모 노드가 되고 남은 두 노드는 값에 따라 왼쪽, 오른쪽 자식 노드가 된다.

 

 

✅ LR(Left-Right)

 

BF 값이 -1, 0, 1이 아닌 노드를 기준으로  자식 노드가 왼쪽으로 한 번, 오른쪽으로 한 번 들어간 경우를 말한다.

 

이런 경우를 해결하기 위해서는 두 번의 회전이 필요하다. 우선 문제가 되는 노드 30을 기준으로 왼쪽에 있는 노드(이 경우에는 20)가 좌회전을 한 번 하고, 다시 문제가 되는 노드 30을 기준으로 우회전을 진행하도록 한다.

 

 

30을 기준으로 좌회전한 모습이다. 나는 이때 값이 20인 노드가 위로 올라오고 10이 내려가는 것이 잠깐 헷갈렸는데 생각해보면 당연한 일이다. 20의 값이 더 크고 10이 더 작으니 자식 노드와 부모 노드가 뒤바뀌는 것이 맞다.

 

 

20을 기준으로 우회전한 모습이다.

 

 

✅ RL(Right-Left)

 

BF 값이 -1, 0, 1이 아닌 노드를 기준으로  자식 노드가 오른쪽으로 한 번, 왼쪽으로 한 번 들어간 경우를 말한다.

 

 

이 경우를 해결하기 위해서도 두 번의 회전이 필요하다. 문제가 되는 10을 기준으로 오른쪽 회전을 한 번 한다. 여기도 값 20인 노드의 값이 더 작으니 20과 30의 위치가 바뀌는 것이 옳다.

 

 

그 후 문제가 되는 노드를 기준으로 왼쪽 회전을 하면 문제가 해결된다.

 

 

 

참고 : https://www.geeksforgeeks.org/deletion-in-an-avl-tree/

Deletion in an AVL Tree - GeeksforGeeks