C AVL 트리(AVL Tree) 설명

  ※ 트리의 개념과 이진탐색트리를 포함해서 설명이 진행되므로 모르면 아래 링크로 확인 !

  ※ C 트리(Tree)설명

C 트리(Tree) 설명

---

 

이진탐색트리의 문제점

- 트리의 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다.

  ※ 위와 같은 순서로 데이터가 누적이 된 상태에서 D의 값을 찾으려면 모든 노드를 탐색하게되며, 이렇게 되면 이진 탐색 트리를 쓰는 의미가 없어진다.

 

이러한 이진탐색트리의 단점을 해결한 트리를 가리켜 균형잡힌 이진트리라하며 그 중 AVL트리에 대해 설명하고자한다.

 

AVL 트리

- Adelson-Velsky and Landis에서 따온 이름이다.

- 이진탐색트리의 단점을 해결한 균형잡힌 이진트리 중 처음으로 발명되었다.

- AVL 트리는 균형의 정도를 표현한 균형 인수(Balance Factor)를 사용한다.

  ※ 계산법 : 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

- 균형이 무너졌을 때, 구조의 재조정(Rebalancing)의 종류는 LL, RR, LR, RL이 있다.

 

 

균형 인수(Balance Factor)

- 노드 위에 적힌 숫자가 균형 인수이다.

- 균형 인수의 절대값이 크면 클수록 트리의 균형이 무너진 상태이다.

  ※ 따라서 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 재조정을 진행한다.

 

 

LL(Left Left), RR(Right Right) 상태

- 위 그림의 왼쪽 트리를 보면 루트 노드의 균형인수가 2이다.

- 왼쪽의 자식 노드가 연이어 연결된 상태인데 이런 상태를 가리켜 LL(Left Left)상태라고 한다.

  ※ 반대로 오른쪽으로 자식 노드가 연이어져 있으면 RR(Right Right)상태라 한다.

- 이러한 LL상태에서 불균형 해소를 위한 리밸런싱을 LL회전이라고 한다.

  ※ 반대로 오른쪽으로는 RR회전이라 한다.

- 키값이 5인 노드를 Child node(이하 CNode), 키값이 10인 노드를 Parent node(이하 PNode)라고 한 뒤, LL회전의 방법은 다음과 같다.

  1. PNode를 CNode의 오른쪽 자식으로 보낸다.

    ※ 이 때, PNode가 CNode의 자식 노드가 되므로 PNode의 기존 자식 참조값은 비워준다.

  2. CNode를 Root노드로 설정한다.

  ※ RR은 반대로 생각해주면 된다.

 

 

 

LR(Left Right), RL(Right Left) 상태

- 왼쪽 자식 노드에 오른쪽 자식 노드가 연결된 상태인데 이런 상태를 가리켜 LR(Left Right)상태라고 한다.

  ※ 반대로 오른쪽 자식 노드에 왼쪽 자식노드가 이어져있으면 RL(Right Left)상태라 한다.

- 이러한 LR 상태에서 LL회전을 하게되면 이진탐색트리의 규칙에 위배되므로 왼쪽 자식 노드를 RR회전을 먼저 진행해 불균형 상태를 LL로 만든뒤, 루트 노드를 LL회전 해줘서 리밸런싱을 한다.

- 키값이 1인 노드를 Leaf node(이하 LNode), 키값이 5인 노드를 Child node(이하 CNode), 키값이 10인 노드를 Parent node(이하 PNode)라고 한 뒤, LL회전의 방법은 다음과 같다.

  1. 먼저 CNode를 RR회전을 해줘서 LNode를 CNode의 자리에 옮기고 CNode를 LNode의 왼쪽 자식으로 옮긴다.

    ※ 이 과정이 끝나면 트리가 LL상태가 되어있다.

  2. (LL 회전 시작) PNode를 LNode의 오른쪽 자식으로 보낸다.

  3. LNode를 Root 노드로 설정한다.

  ※ RL은 반대로 생각해주면 된다. (자식 노드를 LL회전한 뒤 Root 노드를 RR회전)