[비선형 자료구조] - 균형 이진탐색트리

앞서 이진 탐색 트리는  O(logN) 이라는 시간 복잡도를 가져, 탐색 측면에서 이점이 있는데,

삽입 순서에 따라 한쪽으로 치우친 사향트리가 될 경우, O(N)의 시간 복잡도를 갖게 되어, 이점이 사라진다. 따라서 이러한 케이스에 대한 이진 탐색 트리의  단점을 보완하기 위해, 균형을 잡는 여러 방법들 중 AVL 트리에 대해 학습해보고자 한다.

이진 탐색 트리의 기본적인 특징은 여기서  참고!

🌳  균형 이진 탐색 트리란?

▪ 노드의 삽입과 삭제을 진행하면서, 균형을 자동으로 맟춰주도록 동작한다. 

▪ 모든 노드의 좌우 서브 트리 높이가 2이상 차이 나지 않는 트리

▪ 트리의 양쪽 높이 차이가 2이상 날 경우 : 삽입, 삭제, 탐색 등의 시간 복잡도 증가

      ex. 사향트리 - 시간복잡도 : O(N)

▪ 종류에는  AVL 트리, Red-Black 트리가 있고, 여기선 AVL 트리에 대해서 다뤄보고자 한다. 

 

🌳  AVL 트리의 특징

▪ 모든 트리들의 Balance Factor (균형 차이) 를 -1, 0, 1 내에서만 갖게 한다. 

▪ Balance Factor : 기준 노드에 대해!! 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

 

⚖️ Balancing 방법 - Rebalancing

▪ Balance Factor > 0 : 좌측 서브 트리의 높이가 더 큼

▪ Balance Factor < 0 : 우측 서브 트리의 높이가 더 큼

 

▪ 회전 연산 사용 

▪ 단순 회전 - LL, RR

▪ 이중 회전 - LR, RL

 

🌳알아둬야 할 사항

🗹 여기서 작성된 각 회전 명칭들은 균형이 깨진 상황을 바탕으로 명명된 것이라, 해결 방안 (회전 방향)은 반대 방향으로 진행한다고 생각하면 된다.!

🗹 또한 가장 위쪽노드를 기준으로 어떻게 균형이 깨졌는지를 설명한 것임 참고.!

🗹 이진 트리는 좌 -> 우로 키 값이 정렬되어 있음. 따라서 회전 적용 시, 노드의 키 값 크기를 생각하면서 회전 적용하기.!

⭐ 각 노드들의 높이는 leaf 노드에서부터 0으로 시작하며, 아래에서 위로 올라가면서 높이를 추가하게 된다.  따라서 부모 노드의 높이는 두 자식 노드의 높이 중 더 큰 값에 1을 더한 수를 갖게 된다. 

 

 

출처 : 유튜브 [코드라떼] 자바 자료구조 - AVL 트리 개념

 

🗹 자식이 없는 노드는 null 노드라 하며, 이때는 높이를 -1로 가져간다. 

 

 

🌳회전 종류

✅ 단순 회전 - Left-Left (LL)

▪ 노드가 좌측 - 좌측으로 치우쳐져 있는 상태 

▪ 시계 방향(오른쪽 방향)으로 1회 회전시켜 균형을 맞춰준다. 

 

 

✅ 단순 회전 - Right-Right (RR)

▪ 노드가 우측 - 우측으로 치우쳐져 있는 상태 

▪ 반시계 방향(왼쪽 방향)으로 1회 회전시켜 균형을 맞춰준다. 

 

 

✅ 이중 회전 - Left-Right (LR)

 

▪ 노드가 기준 노드(맨 위 노드)에서부터 좌측 - 우측 순으로 치우쳐져 있는 상태 

▪ 단순 회전으로 먼저 바꿔줘야 한다. 

▪ 따라서 가장 아래쪽 노드와 중간 노드를 RR 케이스 회전(왼쪽 회전)을 먼저 시켜서 LL 케이스로 바꾼 다음, LL 케이스 회전(오른쪽 회전)으로 진행해준다.  

 

 

✅ 이중 회전 - Right-Left(RL)

 

▪ 노드가 기준 노드(맨 위 노드)에서부터 우측 - 좌측 으로 치우쳐져 있는 상태 

▪ 단순 회전으로 먼저 바꿔줘야 한다. 

▪ 따라서 가장 아래쪽 노드와 중간 노드를 LL 케이스 회전(오른쪽 회전)을 먼저시켜서 RR 케이스로 바꾼 다음, RR  케이스 회전(왼쪽 회전)으로 진행해준다.