package com.app.main.datastructure;

/**
 * BST 树 实现
 * Created with IDEA
 * author:Dingsheng Huang
 * Date:2019/8/19
 * Time:下午7:22
 */
public class BstTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        // construct
        TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root;

    // insert
    public void  insertIntoBST(int val) {
        root = insertIntoBST(root, val);
    }

    private TreeNode insertIntoBST(TreeNode root, int val) {
        // 如果根节点为空，将新插入节点作为根节点
        if (root == null) {
            root = new TreeNode(val);
        }

        // 根节点不为空
        // 待插入值比根节点小，插入左子树. 注意理解“根节点”是一个上下文环境的相对概念
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }

    // delete
    public void deleteNode(int val) {
        root = deleteNode(root, val);
    }

    // delete 考虑不同分支情况， 删除操作也需要自顶向下遍历查找到待删除节点位置
    // 0. 待删除节点为根节点
    // 1. 待删除节点无左孩子，用右孩子替代删除节点
    // 2. 待删除节点无右孩子，用左孩子替代删除节点
    // 3. 待删除节点既有右孩子又有左孩子，找到右子树的最小值替换待删除节点，然后删除右子树最小值
    private TreeNode deleteNode(TreeNode curNode, int key) {
        if (curNode == null) {
            return null;
        }

        if (key < curNode.val) {
            curNode.left = deleteNode(curNode.left, key);
        } else if (key > curNode.val) {
            curNode.right = deleteNode(curNode.right, key);
        } else {
            if (curNode.left == null) {
                return curNode.right;
            } else if (curNode.right == null) {
                return curNode.left;
            }

            TreeNode minNode = findMin(curNode.right);
            curNode.val = minNode.val;
            curNode.right =  deleteNode(curNode.right, curNode.val);

        }
        return curNode;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // search
    public int searchBST(int val) {
        TreeNode target = searchBST(root, val);
        return target == null ? -1 : target.val;
    }

    // 思路：二分查找
    private TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val){
            return root;
        }
        if (val > root.val) {
            return searchBST(root.right, val);
        } else {
            return searchBST(root.left, val);
        }
    }




    // test
    public static void main (String[] args) {
        BstTree bstTree = new BstTree();
        bstTree.insertIntoBST(5);
        bstTree.insertIntoBST(1);
        bstTree.insertIntoBST(2);
        bstTree.insertIntoBST(3);
        System.out.println(bstTree.searchBST(3));
        System.out.println(bstTree.searchBST(9));
        bstTree.deleteNode(3);
        bstTree.insertIntoBST(9);
        System.out.println(bstTree.searchBST(3));
        System.out.println(bstTree.searchBST(9));
    }
}