[Tree] AVL 트리, AVL Tree

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- AVL 트리 (AVL Tree)

• AVL 트리는 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진 탐색 트리
• AVL 트리는 임의의 노드 x에 대해 x의 왼쪽 서브트리 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리임
• AVL 트리의 높이는 O(log(n))으로 유지됨

 

- 연산 

• Trinode restructuring
  • 회전
    
    1. AVL 트리 규칙이 위배된 노드가 n, n의 위배된 방향 자식 노드가 x
    2. x의 서브트리를 n의 서브트리로 만듬
    3. n을 x의 회전 방향 서브트리로 만듬
    4. x를 n의 부모에 연결 
  • 오른쪽 방향 회전 : 왼쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 오른쪽으로 회전
  • 왼쪽 방향 회전 : 오른쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 왼쪽으로 회전 
  • 4가지의 회전(Rotation) 연산
    1. LL 회전 : n의 왼쪽 서브트리의 왼쪽 서브트리에 새로운 노드가 삽입되어 규칙이 위배됨
       • n에 대한 오른쪽 방향 회전
    2. RR 회전 : n의 오른쪽 서브트리의 오른쪽 서브트리에 새로운 노드가 삽입되어 규칙이 위배됨
       • n에 대한 왼쪽 방향 회전
    3. LR 회전 : n의 왼쪽 서브트리의 오른쪽 서브트리에 새로운 노드가 삽입되어 규칙이 위배됨
       • x에 대한 왼쪽 방향 회전 후 n에 대한 오른쪽 방향 회전
    4. RL 회전 : n의 오른쪽 서브트리의 왼쪽 서브트리에 새로운 노드가 삽입되어 규칙이 위배됨
       • x에 대한 오른쪽 방향 회전 후 n에 대한 왼쪽 방향 회전
• Insertion
  1. 이진 탐색 트리의 삽입 연산을 수행
     • 이때, 새로 삽입한 노드가 균형을 깰 수 있음
  2. 새로 삽입한 노드로부터 루트로 올라가며 각 노드의 높이 값을 갱신
     • 이때, 가장 먼저 불균형이 발생한 노드를 발견하면 이 노드를 기준으로 균형을 맞추는 작업을 수행 : Trinode restructuring
• Deletion 
  • 삽입 연산과는 다르게 삭제 연산에서는 Trinode restructuring 후에도 서브트리의 루트 노드가 전체 AVL 트리의 균형을 깰 수 있음 : 루트에 이르는 동안 균형이 깨지지 않는지 검사해야 함
    
    1. 이진 트리의 삭제 연산을 수행
    2. 삭제된 노드로부터 루트로 올라가며 불균형이 발생한 경우 적절한 회전 연산 수행

 

- 수행 시간

• 회전 연산은 O(1) 소요
• 탐색, 삽입, 삭제 연산의 수행은 AVL 트리의 높이에 비례하므로 O(log(n)) 소요