이진탐색트리(BST, Binary Search Tree)

이진탐색트리(BST, Binary Search Tree)

참고: https://www.youtube.com/watch?v=xxADG17SveY

package BST;

public class Main {
    public static void main(String[] args){

        BST tree= new BST();

        tree.insert(4);
        tree.insert(2);
        tree.insert(1);
        tree.insert(3);
        tree.insert(6);
        tree.insert(5);
        tree.insert(7);

        tree.inorder();

        tree.delete(7);
        tree.inorder();


    }



}



class BST{

    class Node{
        Node left;
        Node right;
        int data;

        Node(int data){
            this.data = data;
        }
    }



    Node root;

    private Node search(Node root, int key){
        if(root==null || root.data==key) return root;

        if(root.right.data < key) return search(root.right, key);
        else return search(root.left, key);
    }


    void insert(int data){
        root = insert(root, data);
    }


    private Node insert(Node root, int data){
        if(root==null){
            root= new Node(data);
            return root;
        }

        if(data < root.data){
            root.left = insert(root.left, data);
        }
        else if(root.data < data){
            root.right = insert(root.right, data);
        }

        return root;
    }

    /**
     * [삭제 경우의 수]
     * 1. 자식이 없을 때
     * 2. 자식이 하나일 때
     * 3. 자식이 두개일 때
     */
    void delete(int data){
        root = delete(root, data);
    }

    private Node delete(Node root, int data){
        if(root == null) return root;

        if(data < root.data){
            root.left = delete(root.left, data);
        }else if(root.data < data){
            root.right = delete(root.right, data);
        }

        //목표를 찾음. 3가지 경우에 따라 처리.
        else{
            if(root.left==null && root.right==null) return null;        //자손0
            else if(root.left == null) return root.right;               //자손1
            else if(root.right == null) return root.left;               //자손1


            //자손2
            root.data = findMin(root.right); //오른쪽에서 가장 작은 것을 복사해온다.
            root.right = delete(root.right, root.data); //복사해왔던 값을 찾아서 삭제한다.
        }

        return root;
    }


    private int findMin(Node root){
        int min= root.data;

        while (root.left != null){
            root = root.left;
            min = root.data;
        }
        System.out.printf("min:%d\n", min);
        return min;
    }


    void inorder(){
        inorder(root);
        System.out.println();
    }


    private void inorder(Node root){
        if(root == null) return;

        inorder(root.left);
        System.out.printf("%d ", root.data);
        inorder(root.right);
    }
}