출처 : https://www.youtube.com/watch?v=syGPNOhsnI4

AVL Tree 의 성질

• 노드 쏠림을 제거한 이진 탐색 트리의 보완형
• 노드의 삽입 / 삭제시 스스로 균형을 잡는 트리
• 삽입 순서에 따른 쏠림 현상을 방지해주기 위해 균형도라는 것을 이용하며 절대값 2 미만이면 균형트리이다.

균형도

• 높이는 아래에서부터 올라가 계산한다. 자식 노드 중 가장 큰 값 + 1 로 본인의 높이를 계산한다

• 리프노드의 깊이는 항상 0 이며, 널 노드는 항상 -1이다

  

• 부모 노드 균형도 = [ 좌측 노드 높이 - 우측 노드 높이 ]

  

• 균형도가 양수이면 좌측, 음수이면 우측으로 쏠려있는 것을 알 수 있다

불균형 문제

1. 부모 노드의 균형도가 2이고 좌측 자식의 균형도가 1인 경우

   Left-Left 로 서브 트리가 비대해지는 것 = LL 문제

   LL 회전으로 해결

2. 부모 노드의 균형도가 -2이고 우측 자식의 균형도가 -1인 경우

   Right-Right 로 서브 트리가 비대해지는 것 = RR 문제

   RR 회전으로 해결

   

3. 부모 노드의 균형도가 2이고 좌측 자식의 균형도가 -1인 경우

   Left-Right 로 서브 트리가 비대해지는 것 = LR 문제

   RR회전 → LL회전으로 나누어서 해결

4. 부모 노드의 균형도가 -2이고 우측 자식의 균형도가 1인 경우

   Right-Left 로 서브 트리가 비대해지는 것 = RL 문제

   RR회전 → LL회전으로 나누어서 해결