열혈 자료구조 - 12.1 균형 잡힌 이진 트리 : AVL 트리의 이해

이진 탐색 트리의 문제점

- 이진 탐색 트리는 데이터를 삽입할 때 작으면 왼쪽 크면 오른쪽 이런식으로 삽입이 이루어짐

- 1부터 4까지 데이터를 삽입하면 아래와 같이 트리가 구성됨

- 이진 탐색 트리의 탐색 연산은 아래의 복잡도를 보이지만 위와 같은 경우처럼 트리가 형성되면 O(n)의 시간 복잡도를 가짐

- 저장 순서에 문제가 있을 경우 제대로 된 효율을 낼 수 없음

- 저장 순서에 변화를 주게되면 제대로된 효율을 내게 유도할 수 있음

 

AVL 트리

- 위와 같은 이진 탐색 트리의 균형 문제를 해결한 트리

- 균형을 유지하기 위해 균형 인수라는 개념을 도입

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

- 이 균형 인수의 절댓값이 2 이상일 경우 균형이 무너졌다고 판단하고 조정

- 조정할 때도 이진탐색트리의 조건에 맞춰야 함

 

균형이 무너진 상태와 회전

- LL 상태와 LL회전 : LL 상태의 트리를 균형잡히게 LL 회전

    -> 서브 트리의 루트 노드를 pNode로 그 아래 노드를 cNode로 잡고 pNode를 cNode의 오른쪽 자식 노드로 연결

    -> 노드가 자식 노드(서브 트리)를 가질 수 있기 때문에 아래와 같이 일반화 할 수 있음

- RR 상태

- LR 상태

    -> LL 상태로 바꾸고 회전을 시킴

    -> LL 상태로 바꾸기 위해 아래 빨간 부분을 RR 회전을 시킴

    -> 두 노드간에 RR 회전을 시키면 부모 자식 간의 관계가 바뀌고 우측 연결이 좌측 연결로 바뀌는 모습을 보임

    -> 즉 LR 상태를 RR 회전을 시켜 LL 상태로 만들고 LL 회전을 시킴

- RL 상태

    -> LR 상태와 마찬가지로 일부를 LL 회전시켜 RR 상태로 만들고 RR 회전을 시킴