[자료구조] 이진 탐색 트리 (Binary Search Tree) 2

1. 균형 이진 트리

• 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리
  

  

2. 이진 탐색 트리의 편향 발생

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

  

3. 균형 이진 탐색 트리 (Balanced Binary Search Tree)

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

  

4. AVL 트리

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

5. AVL 트리 - 리밸런싱 (LL, RR, LR, RL)

• 균형이 깨진 경우
  • BF가 '+'이면 왼쪽 서브 트리에 이상이 있음
  • BF가 '-'이면 오른쪽 서브 트리에 이상이 있음
• 회전 연산
  • 단순 회전 - LL, RR
  • 이중 회전 - LR, RL
• LL (Left-Left)
  • 회전 1회
  • 오른쪽 방향으로 회전
    

    

• RR (Right-Right)
  • 회전 1회
  • 왼쪽 방향으로 회전
    

    

• LR (Left-Right)
  • 회전 2회
  • RR 회전 후 LL 회전
    

    

• RL (Right- Left)
  • 회전 2회
  • LL 회전 후 RR 회전
    

    

6. 코드

// AVL 트리 - 삽입
class Node {
    int key;
    int height;
    Node left;
    Node right;
    
    public Node(int key, Node left, Node right) {
        this.key = key;
        this.height = height;
        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.left = lNode.right;
        lNode.right = node;
        
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        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);
    }
    
    // 왼쪽 서브 트리와 오른쪽 서브 트리의 균형 계산
    // -1, 0, 1 중 하나면 정상
    public int getBalance(Node node) {
        if(node == null) return 0;
        
        return height(node.left) - height(node.right);
    }
    
    // 노드 삽입
    public void insert(int key) {
        this.head = insert(this.head, key);
    }
    
    public Node insert(Node node, int key) {
        if(node == null) return new Node(key, null, null);
        
        if(key < node.key) {
            node.left = insert(node.left, key);
        } else {
            node.right = insert(node.right, key);
        }
        
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        
        int balance = getBalance(node);
        
        // LL
        if(balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }
        
        // RR
        if(balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }
        
        // LR
        if(balance > 1 && key > node.left.key) {
            return lrRotate(node);
        }
        
        // RL
        if(balance < -1 && key > node.right.key) {
            return rlRotate(node);
        }
        return node;
    }
    
    public void levelOrder(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        
        while(!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.data + " ");
            
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
}

// AVL 트리 - 삭제
class AVLTree2 extends AVLTree {
    public void delete(int key) {
        this.head = delete(this.head, key);
    }
    
    public Node delete(Node node, int key) {
        if(node == null) return null;
        
        if(key < node.key) {
            node.left = delete(node.left, key);
        } else if(key > node.key) {
            node.right = delete(node.right, key);
        } else {
            if(node.left == null) { // 자식 노드 1개인 경우
                return node.right;
            } else if(node.right == null) { // 자식 노드 1개인 경우
                return node.right;
            } else { // 자식 노드 2개인 경우
                Node predecessor = node;
                Node Successor = node.left;
                
                while(successor.right != null) {
                    predecessor = successor;
                    successor = successor.right;
                }
                
                predecessor.right = successor.left;
                node.key = successor.key;
            }
        }
        
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        
        int balance = getBalance(node);
        
        // LL
        if(balance > 1 && getBalance(node.left) > 0) {
            return rightRotate(node);
        }
        
        // RR
        if(balance < -1 && getBalance(node.right) < 0) {
            return leftRotate(node);
        }
        
        // LR
        if(balance > 1 && getBalance(node.left) < 0) {
            return lrRotate(node);
        }
        
        // RL
        if(balance < -1 && getBalance(node.right) > 0) {
            return rlRotate(node);
        }
        
        return node;
    }
}