AVL트리

AVL 트리

특징

• ‘AVL 트리’는 균형이 갖춰진 이진 트리이다.
• 균형을 갖추기 위해 회전(Rotation)을 통해 재구성할 수 있다.

  균형

  • 균형 인수가 -1, 0, +1 인 상태

균형 인수

• 왼쪽 자식의 높이 - 오른쪽 자식의 높이

불균형 상태

LL 형식

• 노드가 Left1-Left2로 편향되어 있는 상태

  재구성

• 결과적으로 편향된 노드들을 가진 노드(2)를 root가 된다.

1. 노드(2)가 가지고있던 오른쪽 자식 노드들을 root(1)의 왼쪽 자식 노드로 설정한다.
2. 기존의 root(1)는 노드(2)의 오른쪽 자식 노드로 설정한다.

RR 형식

• 노드가 Right1-Right2로 편향되어 있는 상태

  재구성

• LL형식의 재구성 방식을 반대로 수행한다.

1. 편향된 노드의 왼쪽 자식 노드를 root의 오른쪽 노드로 설정한다.
2. 편향된 노드의 왼쪽 자식 노드를 root로 설정한다.

LR 형식

• 노드가 Left1-Right1로 편향되어 있는 상태

1. 편향된 노드에 RR회전을 수행하여 불균형 노드를 왼쪽으로 몰아 넣는다.
2. 몰아넣은 노드에 LL회전을 수행한다.

RL 형식

• 노드가 Right1-Left1로 편향되어 있는 상태

1. 편향된 노드에 LL회전을 수행하여 불균형 노드를 오른쪽으로 몰아 넣는다.
2. 몰아넣은 노드에 RR회전을 수행한다.