[Algorithm] 균형 검색 트리의 대표적인 예시, AVL Tree란 무엇일까? AVL Tree를 이루는 노드와 Tree의 수선 방법

균형 검색 트리란?

이진 검색 트리에서 검색, 삽입, 삭제의 평균 시간은 Θ(log n) 시간인데, 균형이 잘 맞지 않는 경우에는 최대 Θ(n)의 시간이 될 수 있다.
따라서 이진 검색 트리의 균형이 잘 맞을 수 있게 특정 성질들을 정의해준 것이 균형 이진 검색 트리이다.

 

이러한 균형 이진 검색 트리에는 AVL 트리와 RB(레드-블랙) 트리가 있는데, 이진 검색 트리에 균형을 맞춰주는 균형 이진 검색 트리 외에도 균형 다진 검색 트리 또한 존재한다.

균형 다진 검색 트리의 대표로는 B-트리가 있다.

AVL(균형 검색 트리)란?

AVL 트리는 이진 검색 트리가 항상 균형을 유지하도록 한 균형 이진 검색 트리 중의 하나이다. 이진 검색 트리의 검색, 삽입, 삭제의 속도는 트리의 height와 강하게 연관되어 있기 때문에, 이진 검색 트리의 좋은 성능을 위해서는 균형을 맞추는 방법으로 height를 낮게 유지할 수 있다.

AVL 트리라는 이름
AVL 트리는 Adelson-Velskii와 Landis 두 사람이 고안했기에 AVL 트리라는 이름을 가지게 되었다.

AVL 트리의 성질
AVL 트리의 가장 핵심적인 성질은, 트리 내의 어떤 노드도 좌서브트리와 우서브트리의 높이 차가 1보다 크지 않은 상태로 유지된다는 점이다. 트리 내의 모든 노드가 이 성질을 만족해야 AVL 트리가 된다.

AVL 트리를 이루는 노드 객체

AVL 트리를 구성하기 위해서 노드 객체가 갖춰야 할 구조가 있다.
item : 해당 노드가 가지고 있는 데이터
left : 좌서브트리의 루트 노드 참조
right : 우서브트리의 루트 노드 참조
height : 해당 노드를 루트로 하는 트리의 높이

AVL 트리의 수선

AVL 트리에서 삽입 또는 삭제로 인해 균형이 깨진 경우, 균형이 깨진 서브트리의 root를 기준으로 회전시켜 균형을 맞춰줄 수 있다.
균형이 깨진 경우를 총 4가지로 분류할 수 있는데, 서브트리의 root를 기준으로 어느 child가 더 깊은지에 따라 분류하여 칭한다.

편의를 위해 수선하고자 하는 트리의 root를 t라고 하자.

1. LL 타입 : t.left.left가 가장 깊다.

2. LR 타입 : t.left.right가 가장 깊다.

3. RR 타입 : t.right.right가 가장 깊다.

4. RL 타입 : t.right.left가 가장 깊다.

위와 같이 균형이 깨진 경우를 분류했고, 몇 가지 규칙을 발견할 수 있다.

LL 타입과 LR 타입은 L 서브트리가 더 깊기 때문에 우회전 시켜줘야 한다.
RR 타입과 RL 타입은 R 서브트리가 더 깊기 때문이 좌회전 시켜줘야 한다.
LL 타입과 RR 타입은 한 번의 회전으로 수선이 된다.
LR 타입과 RL 타입은 회전을 통해 LL 또는 LR 타입의 중간과정을 거치고, 한번 더 회전시켜 줘야 한다.

균형을 맞추는 로직

위에서 균형이 맞지 않는 경우에 수선을 하여 균형을 맞춰주는 rotation에 대해 알아봤다.

이러한 rotation 메서드의 호출 시점은 언제일까? 트리의 균형이 깨지는 경우는 삽입과 삭제의 메서드가 호출된 다음 또는, 균형을 맞추는 메서드에 의해 부모 트리의 균형이 깨진 경우이다.

tree에서 삽입과 삭제는 재귀적으로 호출되기 때문에, 빈 곳에 삽입하는 경우가 아닌 모든 경우에 먼저 균형이 맞는지의 여부를 판단한 다음 필요에 따라 균형을 맞춰주는 메서드를 실행하면 균형을 유지하면서 삽입과 삭제를 할 수 있다.

 

참고

https://yoongrammer.tistory.com/72

 

더 공부할 부분

AVL Tree를 코드로 디자인 해 보기.