이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)

규칙

• 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음
• 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼
• 중복된 키를 허용하지 않음
• 각가의 서브 트리도 이진 탐색 트리를 유지

특징

• 이진 탐색 트리 규칙에 의해 데이터가 정렬됨
• 이진 트리에 비해 탐색이 빠르다. (균형 유지 필요)
  • 균형 상태 : O(logN)
  • 불균형 상태 : O(N)

탐색

• 찾고자 하는 데이터를 루트 노드부터 비교 시작
• 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동.
• 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다.
• 찾는 데이터가 없으면 null반환

삽입

• 루트 노드부터 비교 시작
• 삽입할 키가 현재 노드의 키보다 작으면 왼쪽, 크면 오른쪽 노드로 이동.
• Leaf 노드에 도달 후 키 비교 삽입 후 종료

삭제

• 삭제 대상 노드가 Leaf 노드인 경우
  • 삭제 대상 부모 노드의 해당 자식 링크 null로 변경
  • 삭제 대상 노드 삭제
• 삭제 대상 노드가 하나 있는 경우
  • 자식 노드를 삭제 대상 노드의 부모 노드에 연결
  • 삭제 대상 노드 삭제
• 삭제 대상 노드가 두개 있는 경우
  • 삭제 대핫 노드의 왼쪽 서브 트리에서 가장 큰 노드 혹은 삭제 대핫 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택
  • 위에서 선택한 노드를 삭제 대상 노드 위치로 올림
  • 위치 변경 과정에서 다른 자식 노드들의 링크 연결 작업 진행
    • 삭제 대상 노드 왼쪽 노드 == 선택된 왼쪽 노드
    • 삭제 대상 노드 오른쪽 노드 == 선택된 오른쪽 노드
  • 삭제 대상 노드 삭제

코드

import java.util.LinkedList;
import java.util.Queue;
​
public class Main {
​
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree(20);
        bst.addNode(10);
        bst.addNode(30);
        bst.addNode(1);
        bst.addNode(15);
        bst.addNode(20);
        bst.addNode(13);
        bst.addNode(35);
        bst.addNode(27);
        bst.addNode(40);
        bst.levelOrder(bst.head);
        //20 10 30 1 15 20 35 13 27 40
​
        bst.removeNode(20);
        bst.levelOrder(bst.head);
        //15 10 30 1 13 20 35 27 40 
    }
}
​
class Node {
​
    int key;
    Node left;
    Node right;
​
​
    public Node(int key, Node left, Node right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }
​
}
​
class BinarySearchTree {
​
    Node head;
​
    BinarySearchTree(int key) {
        this.head = new Node(key, null, null);
    }
​
    public void addNode(int key) {
        if (this.head == null) {
            this.head = new Node(key, null, null);
        } else {
            Node cur = this.head;
​
            while (true) {
                Node pre = cur;
​
                if (key < cur.key) {
                    cur = cur.left;
​
                    if (cur == null) {
                        pre.left = new Node(key, null, null);
                        break;
                    }
                } else {
                    cur = cur.right;
​
                    if (cur == null) {
                        pre.right = new Node(key, null, null);
                        break;
                    }
                }
            }
        }
    }
​
    public void removeNode(int key) {
        Node parent = null;
        Node successor = null; //지우려는 대상의 후계자 ->
        Node predecessor = null; // successor의 부모
        Node child = null; // successor 의 자식
​
        Node cur = this.head;
        while (cur != null) {
            if (key == cur.key) {
                break;
            }
​
            parent = cur;
            if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
​
        if (cur == null) {
            System.out.println("key 값에 해당하는 노드가 없습니다.");
            return;
        }
​
        // Leaf node
        if (cur.left == null && cur.right == null) {
            if (parent == null) {
                this.head = null;
            } else {
                if (parent.left == cur) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
        }
        // 자식 노드 하나
        else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null) {
            if (cur.left != null) {
                child = cur.left;
            } else {
                child = cur.right;
            }
​
            if (parent == null) {
                this.head = child;
            } else {
                if (parent.left == cur) {
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            }
        }
        // 자식 노드 둘
        else {
            predecessor = cur;
            successor = cur.left;
​
            while (successor.right != null) {
                predecessor = successor;
                successor = successor.right;
            }
​
            predecessor.right = successor.left;
            successor.left = cur.left;
            successor.right = cur.right;
​
            if (parent == null) {
                this.head = successor;
            } else {
                if (parent.left == cur) {
                    parent.left = successor;
                } else {
                    parent.right = successor;
                }
            }
        }
    }
​
    public void levelOrder(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
​
            System.out.print(cur.key + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
}

AVL Tree 코드

package main.iyk2h;

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;
    }

    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;
    }

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

        node.right = rNode.left;
        rNode.left = node;

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

        return rNode;
    }

    public Node lrRotate(Node node) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    public Node rlRotate(Node node) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    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 void delete(int key) {
        this.head = delete(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.right), height(node.left)) + 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 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) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                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.right), height(node.left)) + 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;
    }

    public void levelOrder(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            System.out.print(cur.key + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
}


public class Main {

    public static void main(String[] args) {
        AVLTree avl = new AVLTree();

        avl.insert(30);
        avl.insert(20);
        avl.insert(40);
        avl.insert(10); // LL
        avl.levelOrder(avl.head);
        //30 20 40 10 
        avl.delete(40);
        avl.levelOrder(avl.head);
        //20 10 30 

        avl.insert(40);
        avl.delete(10); // RR
        avl.levelOrder(avl.head);
        //30 20 40 

        avl.insert(25);
        avl.delete(40); // LR
        avl.levelOrder(avl.head);
        //25 20 30 

        avl.insert(27);
        avl.levelOrder(avl.head);
        //25 20 30 27 
        avl.delete(20); // RL
        avl.levelOrder(avl.head);
        //27 25 30 
    }
}