이진 탐색 트리 자료구조 2

 

이진 탐색 트리의 편향 발생(불균형 이진트리)

Case 1) 이진 탐색 트리에 삽입되는 순서 : 20 → 10 → 30 → 5

Case 2) 이진 탐색 트리에 삽입되는 순서 : 5 → 10 → 20 → 30

 

균형 이진 탐색 트리

• Balanced Binary Search Tree
• 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리
• AVL 트리, Red-Black 트리

AVL 트리

• 노드가 삽입, 삭제될 떄 트리의 균형을 체크하고 유지하는 트리
• 각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지
• BF(Balance Factor) # 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이

 

AVL 트리 - Rebalancing

균형이 꺠진 경우,

• BF가 ' + ' 이면 왼쪽 서브 트리에 이상이 있음
• BF가 ' - ' 이면 오른쪽 서브 트리에 이상이 있음

회전 연산

• 단순 회전 - LL, RR
• 이중 회전 - LR, RL

AVl 트리 - LL

LL(Left - Left)

• 회전 1회
• 오른쪽 방향으로 회전

 

---

 

AVl 트리 - RR

RR(Right - Right)

• 회전 1회
• 왼쪽 방향으로 회전

---

 

 

AVl 트리 - LR

LR(Left - Right)

• 회전 2회
• RR 회전 후 LL 회전

---

 

 

 

 

AVl 트리 - RL

RL(Right - Left)

• 회전 2회
• LL 회전 후 RR 회전

 

구현

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int key;
    int height;
    Node left;
    Node right;

    public Node(int key, Node left, Node right) {
        this.key = key;
        this.height = 0;
        this.left = left;
        this.right = right;
    }
}

class AVLTree {
    Node head;

    public int height(Node node) {
        if(node == null){
            return -1;
        }
        return node.height;
    }

 

 

 

LL 구현

public Node rightRotate(Node node) {
        Node lNode = node.left; // 현재 node의 왼쪽 자식에게 마킹

        node.left = lNode.right;
        lNode.right = node;    // '/' 모형을 '^' 모형 트리로 변경

        node.height = Math.max(height(node.left), height(node.right)) + 1; // node의 높이 update
        lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;

        return lNode;
    }

RR 구현

 public Node leftRotate(Node node) {
        Node rNode = node.right;

        node.right = rNode.left; // '\' 모형은 '^' 모형 트리로 변경
        rNode.left = node;

        node.height = Math.max(height(node.left), height(node.right)) + 1;
        rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;

        return rNode;
    }

 

LR 구현

 public Node lrRotate(Node node) { // < 모형 트리 ^ 로 변경 (위에서 로직을 다 만들어서 호출만 하면 됨)
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

RL 구현

 public Node rlRotate(Node node) {// > 모형 트리 ^ 로 변경
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }