Chapter12 탐색(Search) 2

2018/02/27 - [프로그래밍/자료구조] - Chapter11 탐색(Search) 1

12-1 균형 잡힌 이진 탐색 트리: AVL 트리의 이해

이진 탐색 트리의 단점을 개선한 또 다른 이진 탐색 트리를 소개한다.

이진 탐색 트리의 문제점과 AVL트리
이진 탐색 트리의 탐색 연산은 O(log2n)의 시간 복잡도를 가진다. 이진 탐색 트리는 균형이 맞지 않을 수록 O(n)에 가까운 시간 복잡도를 보인다.

이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보인다. 이러한 탬삭 트리의 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 하며, 그 종류는 대략 다음과 같다.

- AVL 트리

- 2-3 트리

- 2-3-4 트리

- Red-Black 트리

- B 트리

자동으로 균형을 잡는 AVL 트리와 균형 인수(Balance Factor)

AVL 트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 멋진 트리이다.

AVL 트리에서는 균형의 정도를 표현하기 위해서 '균형 인수(Balance Factor)'라는 것을 사용한다.

균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

AVL 트리는 슌형 인수의 절댓값이 2 이상인 경우에 균형을 잡기 위한 트리의 리밸런싱(rebalancing)을 수행한다.

리밸런싱이 필요한 첫 번째 상태와 LL회전

AVL트리의 균형이 무너지는 상태는 4가지로 정리되고, 각 상태 별 리밸런싱 방법에도 차이가 있다.

"자식 노드 두 개가 왼쪽으로 연기어 연결되어서 균형 인수 +2가 연출되었다"

'Left Left 상태' 줄여서 'LL상태'라 한다. 그리고 이러한 LL상태에서 발생한 불균형의 해소를 위해 등장한 리밸런싱 방법을 가리켜 'LL회전'이라 한다.

리밸런싱이 필요한 두 번째 상태와 RR회전

"RR상태와 LL상태의 차이점, RR회전과 LL회전의 차이점은 방향이다."

리밸런싱이 필요한 세 번째 상태와 LR회전

"LR상태를 한 번의 회전으로 균형이 잡히는 LL상태나 RR상태로 바꾼다."

"LR상태는 RR회전을 통해서 LL상태가 되게 할 수 있다."

LR회전은 부분적 RR회전과 LL회전의 조합으로 이뤄진다.

리밸런싱이 필요한 네 번째 상태와 RL회전

리밸런싱이 필요한 마지막 상태인 RL상태는 자식노드가 연결된 방향이 LR상태와 반대일 뿐이다. RL회전은 부분적 LL회전과 RR회전의 조합으로 이뤄진다.