[Data Structure] AVL(Adelson-Velsky and Landis) 트리란?

안녕하세요 Foma 💻 입니다!

 

오늘은 저번에 정리했던 이진 탐색 트리를 더 업그레이드(?)한 자료구조인 AVL 트리에 대해서 알아보도록 하겠습니다.

 

(혹시 이진 탐색 트리에 대해 모르시는 분들은 여기 에서 보고 와주세요!)

 

바로 시작할게요~

---

AVL(Adelson-Velsky and Landis) 트리란? 🤔

 

컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 스스로 균형을 잡는 이진 탐색 트리이다.
스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다.  - 위키 백과 -

 

즉, 한 마디로 스스로 균형을 잡는 이진 탐색 트리라고 보시면 됩니다.

 

"AVL 트리가 왜 필요하지?"

 

이진 탐색 트리를 만들 때 아래와 같이 한 쪽으로 데이터가 쏠린 경우 딱 봐도 균형이 왼쪽으로 치우쳐져 있죠?

 

이런 경우엔 이진 탐색 트리를 탐색할 때 O(n)의 시간복잡도를 가지게 됩니다.

 

 

 

 

이렇게 비효율적으로 이진 탐색 트리가 구성되는 것을 막기 위해 트리를 구성할 때 균형을 잡아주는 것이죠.

 

이것이 바로 AVL트리가 필요한 이유이고 균형을 잡아줌으로써 탐색할 때 O(logn)에 가깝게 만들어 주는 것이죠!

---

Balance Factor

 

그렇다면 이진 탐색 트리의 균형은 어떤 식으로 잡는 것일까요?

 

균형을 잡을 때 핵심되는 것은 바로 Balance Factor라는 것인데요.

 

Balance Factor는 왼쪽과 오른쪽의 자식의 높이 차이를 뜻합니다.

 

Balance Factor를 트리에 표현하면 아래와 같습니다.

 

(왼쪽 자식의 높이 - 오른쪽 자식의 높이를 빼서 계산했습니다.)

 

 

그러면 BF가 -2부터 2까지 존재하죠?

 

이 때 균형이 잡혔다는 것은 BF가 최대 1까지 차이나는 것, 즉 -1부터 1까지일 때를 의미합니다.

 

고로 2나 -2를 가지고 있는 것은 불균형하다는 것이죠.

---

회전(균형 잡기)

 

불균형한 트리르 바로잡기 위해선 회전이 필요합니다.

 

왼쪽으로 돌리는 회전(L), 왼쪽에서 오른쪽으로 돌리는 회전(LR), 오른쪽에서 왼쪽(RL)으로 돌리는 회전, 오른쪽(R)으로 돌리는 회전 이렇게 4가지가 있습니다.

 

7 4 3 2 5 8 10 11 9 순으로 삽입된다고 가정하고 설명드리겠습니다.

 

가장 먼저 7이 삽입되겠죠?

4가 삽입되는 순간 7의 왼쪽 자식이 높이가 1이므로 BF는 1이 됩니다.

 

3이 삽입되는 순간 7의 왼쪽 자식 높이가 2가 되므로 BF가 2가 됩니다.

 

고로 불균형한 트리가 되는 것이죠.

 

 

이것을 바로 잡기 위해선 어떻게 해야 할까요?

 

왼쪽으로 치우쳐져 있는 트리이므로 오른쪽으로 회전을 해서 균형을 잡아주어야 할 것입니다.

 

회전을 해주는 방법은 불균형이 시작된 노드부터 끝의 자식 중 중간값을 시작된 노드로 대체하고 값에 따라 자식을 배치합니다.

 

 

2가 삽입되면 아래와 같이 구성될 것입니다.

 

 

 

5가 삽입되면 아래와 같이 구성될 것입니다.

 

 

 

8이 삽입되면 아래와 같이 구성될 것입니다.

 

 

 

 

 

10이 삽입되면 아래와 같이 구성될 것입니다.

 

 

 

11이 삽입되는 순간 BF가 -2가 되며 균형이 깨지게 됩니다.

 

이 때는 오른쪽의 자식이 치우쳐져 있으므로 왼쪽으로 회전을 해줘야겠죠?

 

회전을 하면 아래와 같이 트리가 구성됩니다.

 

 

마지막으로 9를 삽입하면 아래와 같이 트리가 구성될 것입니다.

 

이 때는 조금 더 복잡해지는데요.

 

 

 

초록색으로 표시한 3개의 숫자를 왼쪽으로 회전해야 하기 때문인데요.

 

 

이러한 경우 회전을 하게 되면 그 아래 있는 자식들은 떼어지게 됩니다.

 

 

이 때는 떼어진 자식들을 차례로 위와 같이 삽입하고 균형을 잡아주면 됩니다.

 

이렇게 모두 삽입하면 균형잡힌 이진 탐색 트리가 완성되게 됩니다.

 

 

 

---

오늘은 이렇게 AVL 트리가 무엇이고, 왜 필요한지, 그리고 균형을 잡아가는 방법에 대해 알아보았습니다.

 

다음 시간에는 AVL트리를 코드로 어떻게 구현하는지에 대해 알아보겠습니다.