
public class BinarySearchTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
 
        public TreeNode(int val) {
            this.val = val;
        }
    }
 
    public TreeNode root;
 
    //查找结点
    public TreeNode search(int val) {
        
    }
 
    //插入结点
    public boolean insert(int val) {
        
    }
 
    //删除结点
    public boolean remove(int val) {
        
    }
 
    //中序遍历二叉搜索树
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

成员变量root为根节点。

根据前面二叉搜索树的特点，我们能够实现二叉树的三大操作。其中查找和插入比较简单，删除操作作为难点，分为多种情况。

1. 查找

若根节点(root)不为空：

1.如果root的值==查找值，返回root。

2.如果root的值 > 查找值，往左子树找。

3.如果root的值 < 查找值，往右子树找。

若根节点(root)为空或遍历到null还没找到：

返回null

代码如下：


    //查找结点
    public TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

2. 插入

如果树为空树，即根(root) == null，直接插入。

如果树不是空树：

按照查找逻辑确定插入位置(相等不插入，返回)，插入新结点。

需同时记录当前遍历到结点的父节点(初始为null)，最后根据父节点进行插入。

注意点：二叉搜索树的插入操作只会插入到当前为null的孩子结点。

代码如下：


    //插入结点
    public boolean insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            parent = cur;
            if (val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            } else {
                return false;//相等不插入
            }
        }
        //循环走完，cur为null，cur的位置就是要插入的位置
        //判断cur在parent左边还是右边
        if (val < parent.val) {
            parent.left = new TreeNode(val);
        } else {
            parent.right = new TreeNode(val);
        }
        return true;
    }

3. 删除（重点）

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

三种情况，每个情况又对应三种子情况

1.cur.left == null

2.cur.right == null

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

1.cur.left == null

1.1 cur 是 root，则 root = cur.right

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

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

下面这三种情况和前面三种非常相似，就不再画图了，自己画图更容易理解。

2.cur.right == null

2.1. cur 是 root，则 root = cur.left

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

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

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

需要使用替换法进行删除。要想使以cur为根的子树删除cur后还满足二叉搜索树，需要找到一个结点值是比cur的左子树所有结点都大，比cur的右子树所有结点都小的值。有两个方案：

3.1.在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题 —— 右子树找最小结点

3.2.在它的左子树中寻找中序下的第一个结点(关键码最大)，用它的值填补到被删除节点中，再来处理该结点的删除问题 —— 左子树找最大结点。

代码如下：


    //删除结点
    public boolean remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (val < cur.val) {
                parent = cur;
                cur = cur.left;
            } else if (val > cur.val) {
                parent = cur;
                cur = cur.right;
            } else {
                removeNode(parent, cur);//删除结点
                return true;
            }
        }
        //找不到该结点
        return false;
    }
 
    private void removeNode(TreeNode parent, TreeNode cur) {
        //三种情况：1.待删除结点cur.left为空
        //       ：2.cur.right为空
        //       ：3.cur的左右都不为空
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            //cur左右都不为空  找cur的 左树最大值 或 右树最小值 与cur进行替换
 
            //找左树最大值
            //findMaxOfLeftTree(cur);
            //找右树最小值
            findMinOfRightTree(cur);
        }
    }
 
    //找右树最小值
    private void findMinOfRightTree(TreeNode cur) {
        TreeNode node = cur.right;
        TreeNode p = cur;
        while (node.left != null) {
            p = node;
            node = node.left;
        }
        cur.val = node.val;
        //删除node 此时判断node是p的左树还是右树
        if (node == p.left) {
            p.left = node.right;
        } else {
            p.right = node.right;
        }
    }
 
    //找左树最大值
    private void findMaxOfLeftTree(TreeNode cur) {
        TreeNode node = cur.left;
        TreeNode p = cur;
        //找左树最大值(左树最右结点)
        while (node.right != null) {
            p = node;
            node = node.right;
        }
        cur.val = node.val;//替换
        //删除node 此时判断node是p的左结点还是右结点
        if (node == p.right) {
            p.right = node.left;
        } else {//没有结点
            p.left = node.left;
        }
    }

二、性能分析及与Java类集的关系

前面说过，二叉搜索树查找、插入和删除操作的平均时间复杂度都为 O(log n)。

1. 分析：

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：可能是完全二叉树，也有可能是单分支的一棵树。

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2N

最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

如果退化成单支树，二叉搜索树的性能就失去了，其操作的时间复杂度可能会退化为 O(n)。因此为了保持平衡和高效性能，就有了基于二叉搜索树的变体：AVL 树、红黑树等。

2. 与Java类集的关系：

TreeMap 和 TreeSet 即 Java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证。因此，二叉搜索树是一种重要且用途广泛的数据结构。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/783349

【二叉搜索（排序）树】——一种高效查找的数据结构（清晰图解）_树查找算法 图解

二叉搜索树的概念及特点

一、二叉搜索树的构建及操作

1. 查找

2. 插入

3. 删除（重点）

二、性能分析及与Java类集的关系

【二叉搜索（排序）树】——一种高效查找的数据结构（清晰图解）_树查找算法图解