Binary Search Tree

binary tree에서 검색 효율이 좋은 자료구조다. 

 

 

장점

이진 탐색과 링크드 리스트 자료구조를 결합한 형태로 각 장단점을 보완한 것이 BST

 

이진탐색 : O(logn) 으로 탐색한다. 매번 원소를 비교 시, 비교 대상이 절반으로 줄어든다. 

링크드 리스트 : 추가 삭제 시 O(1) 

 

 

 

시간 복잡도

트리 높이에 비례한다. 따라서, balanced/unbalanced인지에 영향을 받는다. 

balanced경우, 탐색이 O(logn)이지만, unbalanced 되면 O(n)이 된다. 

이 경우, 다시 rebalancing이 필요하다. 이 기법을 갖는 자료구조가 AVL, red black tree

 

 

 

특징 

1 모든 key값은 unique.
  그렇지 않으면 조건 2,3 번에 위배된다. 그래서 중복된 key입력이 보이면 count로 중복을 없앨 수 있다. 

2 root 노드 left subtree의 모든 노드는 root key 보다 작다. 

3 root 노드 right subtree의 모든 노드는 root 노드 key 보다 크다. 

4 left/right subtree또한 이진 검색 트리다. 

 

 

 

연산 

find ( key )

root에서부터 key를 비교하며 타고 내려간다. 

하지만, leaf를 지나게 되면 key와 같은 값을 못 찾은 경우가 있을 수 있다.

 

insert ( key ) 

새로운 key는 root에서부터 key를 비교하며 내려가며 새로운 key를 넣을 자리를 찾는다. 

 

delete ( key )

key값을 갖는 노드를 root부터 내려가면서 찾는다. 

그리고, 노드의 자식이 0, 1, 2 경우에 따라 삭제 연산을 처리한다. 

 

0개 : 자식 제거

parent.(왼/오)자식  = null 

 

1 개 : 지워진 자식의 자식 올리기

parent.(왼/오) 자식 = (왼/오)자식의 (왼/오)자식 

 

2 개:오른쪽 자식 중 가장 작은 값 ( 또는, 왼쪽 자식 중 자식 중 가장 큰 값 올리기 )

 

 

display ( 노드 ) 

inorder 순회하면 정렬된 상태로 출력한다. 

 

 

주의

노드가 root인 경우

트리가 빈 경우 

child 삭제/추가는 parent 노드에서 처리하는데 child가 left/right인지 구분

 

 

 

 

 

구현 

 
class BinarySearchTree{
    public class Node{
        int key;
        Node left, right;
        public Node(int key) {
            this.key = key;
        }
    }
    
    Node root;
 
    
    // bst에서 key 유무확인 
    public boolean find(int key) {
        Node cur = root;
        while(cur != null) {
            if(cur.key == key) {
                return true;
            }else if(key < cur.key) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        return false;
    }
    
    // bst에 key 삽입
    public void insert(int key) {
        Node newNode = new Node(key);
        // 비었을 경우 
        if(root == null) {
            root = newNode;
            return;
        }
        
        // cur는 newNode가 들어갈 위치를 찾는다. 
        Node cur = root;
        Node parent = root;
        boolean isLeftChild = true;
        while(cur != null) {
            parent = cur;
            if(key < cur.key) {
                cur = cur.left;
                isLeftChild = true;
            }else {
                cur = cur.right;
                isLeftChild = false;
            }
        }
        
        if(isLeftChild) {
            parent.left = newNode;
        }else {
            parent.right = newNode;
        }
    }
    
    // inorder 순회로 정렬된 원소 출력 
    public void display(Node cur) {
        if(cur != null) {
            display(cur.left);
            System.out.println(cur.key);
            display(cur.right);
        }
    }
    
    // key 값을 갖는 node 제거 
    public void delete(int key) {
        // key값 갖는 node 찾기 
        Node cur = root;
        Node parent = root;
        boolean isLeftChild = true;
        
        while(cur.key != key) {
            parent = cur;
            if(key < cur.key) {
                cur = cur.left;
            }else if(key > cur.key) {
                cur = cur.right;
            }
            
            if(cur == null) {
                return;
            }
        }
        
        
        // key값을 갖는 node 제거 
        if(cur.left == null && cur.right == null) {
            // 자식이 없는 경우 
            
            // cur가 root
            if(cur == root) {
                root = null;
                return;
            }
            if(isLeftChild) {
                parent.left = null;
            }else {
                parent.right = null;
            }
        }else if(cur.left == null && cur.right != null) {
            // right만 존재 
            
            // cur가 root 
            if(cur == root) {
                root = cur.right;
                return;
            }
            if(isLeftChild) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.left != null && cur.right == null) {
            // left만 존재 
            
            // cur가 root 
            if(cur == root) {
                root = cur.left;
                return;
            }
            if(isLeftChild) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            // left, right 모두 존재 
            Node successor = getSuccessor(cur);
            successor.left = cur.left;
            if(cur == root) {
                root = successor;
                return;
            }
            
            if(isLeftChild) {
                parent.left = successor;
            }else {
                parent.right = successor;
            }
        }
    }
    
    // deleteNode 바로 다음 큰 값 찾기 ( right subtree에서 가장 작은 값 )
    public Node getSuccessor(Node deleteNode) {
        Node successor = deleteNode.right;
        Node successorParent = deleteNode.right;
        
        while(successor.left != null) {
            successorParent = successor;
            successor = successor.left;
        }
        
        if(successor != deleteNode.right) {
            successorParent.left = successor.right;
            successor.right = deleteNode.right;
        }
        
        return successor;
    }
}