Binary search tree Java 코드

Binary Search Tree

-왼쪽 자식은 자기보다 작은 값들이고 오른쪽 자식은 자기보다 큰값들인 이진 트리

-이진 탐색을 하는데 최적화

Java 코드

public class BinarySearchTree {
    BTNode root;
    
    public BinarySearchTree(){
        root = null;
    }
    
    //자기보다 작으면 왼쪽, 크면 오른쪽으로 이동
    //이동 하려는 곳이 null인 경우 값을 넣고 종료
    public void add(int data){
        BTNode item = new BTNode(data);
        if(root == null){
            root = item;
            return;
        }
        BTNode current = root;
        while(current != null){
            if(data <= current.data){
                if(current.leftChild == null){
                    current.leftChild = item;
                    return;
                }
                current = current.leftChild;
            }
            else{
                if(current.rightChild == null){
                    current.rightChild = item;
                    return;
                }
                current = current.rightChild;
            }
        }
    }
    
    //지울려는 노드 찾은 후 그 노드 자리에 오른쪽 최소 노드를 이동
    public boolean delete(int data){
        if(root == null) return false;
        BTNode current = root;
        BTNode parent = null;
        while(current != null){
            if(current.data == data){
                //자식 없을 경우 부모에게 null 연결
                if(current.leftChild == null && current.rightChild == null) connectParent(current, parent, null);
                //한쪽만 있을 경우 부모에게 바로 연결
                else if(current.rightChild == null) connectParent(current, parent, current.leftChild);                        
                else if(current.leftChild == null) connectParent(current, parent, current.rightChild);
                //자식이 양쪽다 있을 경우 오른쪽 최소 값 찾은 후 부모와 연결
                else{ 
                    BTNode temp = shift(current);
                    temp.leftChild = current.leftChild;
                    temp.rightChild = current.rightChild;
                    if(current == root) root = temp;                    
                    else if(current == parent.leftChild) parent.leftChild = temp;
                    else parent.rightChild = temp;
                }
                return true;
            }
            if(data <= current.data){
                parent = current;
                current = current.leftChild;
            }
            else{
                parent = current;
                current = current.rightChild;
            }
        }
        return false; //삭제하려는 값이 없음
    }
    
    //삭제하고 빈 노드를 오른쪽 자식중 가장 작은 값으로 교체
    public BTNode shift(BTNode root){
        BTNode parent = root;
        BTNode current = root.rightChild;
        while(current.leftChild != null){
            parent =current;
            current = current.leftChild;
        }
        if(parent.leftChild == current){
            if(current.rightChild == null) parent.leftChild = null;
            else parent.leftChild = current.rightChild;            
        } else{
            if(current.rightChild == null) parent.rightChild = null;
            else parent.rightChild = current.rightChild;                        
        }
        return current;
    }
    
    //원래 자식 자리에 부모와 새로운 자식 연결
    public void connectParent(BTNode child, BTNode parent, BTNode newChild){
        if(child == root) root = newChild;
        else if(child == parent.leftChild) parent.leftChild = newChild;
        else parent.rightChild = newChild;        
    }
    
    //전위 탐색으로 트리 출력
    public void printTree(BTNode root){
        if(root == null) return;
        System.out.println(root.data);
        printTree(root.leftChild);
        printTree(root.rightChild);
    }
}