概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树
在这里插入图片描述

操作

操作—查找

在这里插入图片描述

操作—插入

如果树为空树，即根 == null，直接插入
如果树不是空树，按照查找逻辑确定插入位置，插入新结点

操作—删除

设待删除结点为 cur, 待删除结点的双亲结点为 parent

1. cur.left == null

cur 是 root，则 root = cur.right
cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

1. cur.right == null

cur 是 root，则 root = cur.left
cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

1. cur.left != null && cur.right != null

需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节比特科技点中，再来处理该结点的删除问题

代码实现

//构造节点
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "bstree.Node{" +
                "val=" + val +
                '}';
    }
}

//实现自己的搜索树的各个代码
public class BSTree {
    public Node root;

    public BSTree() {
        root = null;
    }

    /*
    在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
     */
    public boolean find(int key) {
        Node cur = root;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            } else if (cur.val > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return false;
    }

    /*
    插入
    return true 表示插入成功, false 表示插入失败
     */
    public void insert(int key) {
        if (root == null) {
            root = new Node(key);
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (cur.val == key) {
                throw new RuntimeException("BSTree中不允许重复的key出现");
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }

        Node node = new Node(key);
        if (key > parent.val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
    }

    /*
     删除成功返回 true，失败返回 false
     */
    public boolean remove(int key) {
        Node parent = null;
        Node cur = root;
        while (cur != null) {
            if (cur.val == key) {
                removeKey(parent, cur);//要删除的节点就是cur
                return true;
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        return false;
    }
    /*
    根据cur的孩子是否存在分四种情况
    1. cur左右孩子均不存在
    2. cur只有左孩子
    3. cur只有右孩子
    4. cur左右孩子均存在
    
    看起来有四种情况，实际情况1可以与情况2或者3进行合并，只需要处理是那种情况即可
    除了情况4之外，其他情况可以直接删除
    情况4不能直接删除，需要在其子树中找一个替代节点goat进行删除
     */

    private void removeKey(Node parent, Node cur) {
        //要删除节点cur没有左孩子的前提下
        //分三种情况讨论：1，cur没有双亲节点  2.cur是其双亲节点的右孩子   3.cur是其双亲节点的左孩子
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.right) {
                parent.right = cur.right;
            } else {
                parent.left = cur.right;
            }
        }
        //要删除节点cur没有左孩子的前提下
        //分三种情况讨论：1，cur没有双亲节点  2.cur是其双亲节点的右孩子   3.cur是其双亲节点的左孩子
        else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.right) {
                parent.right = cur.left;
            } else {
                parent.left = cur.left;
            }
        }
        //要删除节点cur左右孩子均存在的前提下
        //找到比cur.val大的节点里最小的一个节点，让他成为替代节点goat
        else {
            Node goat = cur.right;
            Node goatParent = cur;
            while (goat.left != null) {
                goatParent = goat;
                goat = goatParent.left;
            }//goat一定没有左孩子
            //找到了goat节点，交换cur和goat节点。交换后要删除的cur.val到了goat位置
            cur.val = goat.val;
            //下面就是要删除goat位置
            if (goatParent == cur) {//这种情况下，说明cur为根节点且goat为cur的右孩子
                goatParent.right = goat.right;
            } else {
                goatParent.left = goat.right;
            }
        }
    }
}