二叉查找树

港控/mmm° 2022-08-28 03:51 250阅读 0赞

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？

这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

**1、二叉查找树的查找操作**

根据二叉查找树的性质，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。所以查找操作就相对比较简单，当到达一个结点时，如果值等于待查找的值，则直接返回，如果大于，则去右子树查找，如果小于，则去左子树中查找。可以基于递归或者迭代两种方式进行实现，如下图所示的二叉树。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16][]

当要查找节点 5 时的查找路径如下图所示

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

首先定义二叉树的节点

package com.Ycb.leetcode.tree;
    
    public class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public int data;
    
        public TreeNode() {
    
        }
    
        public TreeNode(int data) {
            this.data = data;
        }
    
        @Override
        public String toString() {
            return "TreeNode{" +
                    "data=" + data +
                    '}';
        }
    }

经上面分析，基于递归的实现逻辑如下：

定义如下如下递归函数。

//定义递归函数
    //参数说明：value表示待查找的值，node表示node节点开始的树
    //返回值：查找到则返回具体节点，否则返回null
    TreeNode findInternal(int value,TreeNode node);

递归终止条件

1、传入的node为空
    2、传入的节点值等于给定的value

递推公式

if(node.data<value){
        //去右子树中查找
        return  findInternal(value,node.right);
    }
    else{
        return  findInternale(value,node.right);
    }

完整的代码如下：

public TreeNode find(int value) {
            return findInternal(value, root);
        }
    
        private TreeNode findInternal(int value, TreeNode node) {
            //递归终止条件
            if (node == null) return null;
            if (node.data == value) return node;
            if (node.data > value) {
                return findInternal(value, node.left);
            } else {
                return findInternal(value, node.right);
            }
        }

其实基于非递归的实现和基于递归实现是差不多的，此处直接给出代码

public TreeNode find1(int value) {
            TreeNode node = root;
            //终止条件
            while (node != null && node.data != value) {
                if (node.data > value) {
                    node = node.left;
                } else {
                    node = node.right;
                }
            }
            return node;
        }

**2、二叉查找树的插入操作**

二叉查找树的插入过程有点类似查找操作。新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

（1）如果树中找到节点的值等于待插入的节点，则直接返回

（2）如果插入的值比节点的值大：  
（2.1）如果右子树为空，则直接设置为右子树，比如如下的树，当要插入元素 9

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

（2.2）如果右子树不为空，则继续查找，知道找到合适的位置

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16][]

（3）如果插入的值比节点的值小：

（3.1）如果左子树为空，则直接设置为左子树

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

（3.2）如果左子树不为空，则继续查找，知道找到合适的插入位置

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1][]

经上面分析，代码如下：

public void insert(int value) {
            //树还没有初始化
            if (root == null) {
                root = new TreeNode(value);
                return;
            }
            TreeNode p = root;
            while (p != null) {
                //存在，不需要插入
                if (p.data == value) return;
                //往 p 的右子树查找
                if (value > p.data) {
                    //p 的 右子树为空
                    if (p.right == null) {
                        p.right = new TreeNode(value);
                        return;
                    }
                    p = p.right;
                }
    
                //往p的左子树查找
                if (value < p.data) {
                    //p的左子树为空
                    if (p.left == null) {
                        p.left = new TreeNode(value);
                        return;
                    }
                    //否则继续在p的左子树中查找
                    p = p.left;
                }
            }
        }

**3、二叉查找树的删除操作**

二叉查找树的删除操作稍微复杂一些，主要问题就是删除一个结点时如何从剩下的节点中找一个结点来填补上当前节点。

一个结点在树中有如下几种状态

（1）如下节点，要删除的节点没有子节点

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

这种情况的删除比较简单，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 5 。删除后变为如下图所示（用阴影表示已删除）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16][]

（2）如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 6。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

删除后变为如下（node4.right = node5）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

（3）如果要删除的节点有两个子节点，这就比较复杂了。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 4。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

删除后变为如下所示

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 8][]

public void delete(int value) {
            //p 表示指向要删除的节点，初始化指向跟结点
            TreeNode p = root;
            //pp 表示指向p的父节点
            TreeNode pp = null;
            while (p != null && p.data != value) {
                pp = p;
                if (value > p.data) p = p.right;
                else p = p.left;
            }
    
            //没有找到节点p
            if (p == null) {
                return;
            }
    
            //要删除的节点有两个子节点
            if (p.left != null && p.right != null) {
                TreeNode minP = p.right;
                TreeNode minPP = p;
                while (minP.left != null) {
                    minPP = minP;
                    minP = minP.left;
                }
                //值替换
                p.data = minP.data;
                //下面变为删除minP了
                p = minP;
                pp = minPP;
            }
    
            //删除结点是叶子节点或者仅有一个子节点
            TreeNode child;
            if (p.left != null) {
                child = p.left;
            } else if (p.right != null) {
                child = p.right;
            } else child = null;
    
            //删除跟结点
            if (pp == null) root = child;
            else if (pp.left == p) pp.left = child;
            else pp.right = child;
        }

结合图和代码注释比较好理解，主要关注pp指针和p指针，以及待删除节点有两个孩子时，通过值替换转换为叶子节点或者是只有一个孩子节点的删除。

通过上面的分析，发现其实删除操作时比较复杂的，删除节点时，需要通过一定的逻辑从后面的节点中选择一个节点到当前位置。

其实还可以用一种比较简单的思路，删除节点并不是真正的删除，节点不是真的删除，而是打一个标记。但是这样有一个缺陷，如果删除的节点过多，会占用过多的内存空间，而且查找，和插入等的需要遍历的元素也会相应的增多。

public boolean deleted;

当然删除的元素只是被打一个标记，再插入时如果元素相同，可以重复使用该位置，比如插入元素 3 ，此时打一个标记，deleted = true，过段时间后再插入元素 3 ，则可简单的把标记deleted = false即可。

**4、快速查找最小节点。**

根据二叉查找树的性质，对于任何一个节点，其左子树的节点都比其小，右子树的节点都比其大，所以需要寻找最小的节点，只需要不断的往左子树查找，直到某一个节点的左子树为空，或者是到达叶子节点。代码比较简单，如下：

public TreeNode findMin() {
            if (root == null) {
                return null;
            }
            TreeNode node = root;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

**5、快速查找最大节点**

快速查找最大节点与最小节点是类似的，快速查找最大节点就是不断的往右进行查找，直到每一个节点的左子树为空，或者是到达叶子节点

public TreeNode findMax() {
            if (root == null) {
                return null;
            }
            //一直往右找左节点
            TreeNode node = root;
            while (node.right != null) {
                node = node.right;
            }
            return node;
        }

**6、前驱节点**

这里所说的前驱节点并不是指引用关系，不要与链表中的概念混淆，前驱结点：节点data值小于该节点data值并且值最大的节点

**方案一、**判断规则如下：  
（1）若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点  
（2）若一个节点没有左子树，那么判断该节点和其父节点的关系  
（2.1） 若该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。  
（2.2） 若该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到 找到一个节点P，P节点是其父节点Q的右边孩子，那么Q就是该节点的后继节点

方案一需要对树进行改造，需要增加parent节点指向父亲，为了向上寻找parent时方便，此处采用如下方案。

**方案二、**根据二叉搜索树的性质，其实二叉搜索树的**中序遍历**就是一个升序的序列，既然是升序的序列，那要寻找前驱和后继就比较简单了

二叉树的遍历参见博文

[二叉树的遍历/images/20220828/95307f29980a408dafecb6831b4f7bd6.png![icon-default.png?t=L9C2][icon-default.png_t_L9C2]/images/20220828/95307f29980a408dafecb6831b4f7bd6.png][https_blog.csdn.net_ycb1914845451_article_details_112583303_icon-default.png_t_L9C2_icon-default.png_t_L9C2_https_blog.csdn.net_ycb1914845451_article_details_112583303]

此处就不上代码了，后继节点也是类似的。

**7、后继节点**

节点data值大于该节点data值并且值最小的节点

判断规则如下：  
（1）若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点  
（2）若一个节点没有右子树，那么判断该节点和其父节点的关系  
（2.1）若该节点是其父节点的左边孩子，那么该节点的后继结点即为其父节点  
（2.2）若该节点是其父节点的右边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直 到找到一个节点P，P节点是其父节点Q的左边孩子，那么Q就是该节点的后继节点

**支持重复数据的二叉查找树**

前面讲二叉查找树的时候，都是默认树中节点存储的都是数字。很多时候，在实际的软件开发中，在二叉查找树中存储的，是一个包含很多字段的对象。我们利用对象的某个字段作为键值（key）来构建二叉查找树。我们把对象中的其他字段叫作卫星数据。

前面我们讲的二叉查找树的操作，针对的都是不存在键值相同的情况。那如果存储的两个对象键值相同，这种情况该怎么处理呢？

这里有两种解决方法：

第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。有点类似与散列表的拉链冲突解决办法。

第二种方法比较不好理解，不过更加优雅。每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

支持重复数据的完整代码如下：

package com.Ycb.tree;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class BinarySearchTree {
        private TreeNode root;
    
        /**
         * @param value
         * @return
         */
        public List<TreeNode> find(int value) {
            List<TreeNode> listTreeNode = new ArrayList<>();
            TreeNode p = root;
            while (p != null) {
                //如果找到相等的，则加入到返回结果，同时继续去右子树查找
                if (p.data == value) {
                    listTreeNode.add(p);
                    p = p.right;
                } else if (p.data < value) {
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return listTreeNode;
        }
    
        public void insert(int value) {
            //树没有初始化
            if (root == null) {
                root = new TreeNode(value);
                return;
            }
            TreeNode p = root;
            while (p != null) {
                if (p.data <= value) {
                    if (p.right == null) {
                        TreeNode newNode = new TreeNode(value);
                        p.right = newNode;
                        return;
                    }
                    p = p.right;
                } else {
                    if (p.left == null) {
                        TreeNode newNode = new TreeNode(value);
                        p.left = newNode;
                        return;
                    }
                    p = p.left;
                }
            }
        }
    
        /**
         * 删除所有符合的节点
         *
         * @param data
         */
        public void deleteNode(int data) {
            TreeNode p = this.root;
            TreeNode pParent = null;    // p 的父节点
    
            while (p != null) {
                if (p.data == data) {
                    TreeNode pRe = delete(pParent, p);
                    p = pRe;
                } else if (p.data < data) {
                    pParent = p;
                    p = p.right;
                } else {
                    pParent = p;
                    p = p.left;
                }
            }
        }
    
        /**
         * 删除指定节点
         *
         * @param pParent
         * @param p
         */
        public TreeNode delete(TreeNode pParent, TreeNode p) {
            int flag = 0;
            TreeNode pBak = p;
    
            // 要删除的节点有左右子节点
            if (p.left != null && p.right != null) {
                TreeNode minP = p.right;
                TreeNode minPP = p; // minP 的父节点
    
    
                while (minP.left != null) {
                    minPP = minP;
                    minP = minP.left;
                }
    
                p.data = minP.data; // 将 minP 的数据替换到 p 中
    
                /* 技巧：对右子树中最小的节点进行删除，
                   这种情况跟要删除的节点只有一颗子树或者没有子树情况一样，
                   所以这边将 minPP 赋值给 pParent，minP 赋值给 p，那么重复使用一段代码 */
                pParent = minPP;
                p = minP;
    
                flag = 1;
            }
    
            TreeNode child = null;
            // 要删除的节点只有左节点的情况
            if (p.left != null) {
                child = p.left;
            } else if (p.right != null) {   // 要删除的节点只有右子节点的情况
                child = p.right;
            } else {    // 要删除的节点左右子节点都无的情况
                child = null;
            }
    
            // 删除的是根节点的情况
            if (pParent == null) {
                this.root = child;
            }
    
            // 将 p 父节点的左/右子树重新指向
            if (pParent.left == p) {
                pParent.left = child;
            } else if (pParent.right == p) {
                pParent.right = child;
            }
            return flag == 1 ? pBak : child;
        }
    
        public TreeNode findMin() {
            if (root == null) {
                return null;
            }
            //一直往左找左节点
            TreeNode node = root;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
    
        public TreeNode findMax() {
            if (root == null) {
                return null;
            }
            //一直往右找左节点
            TreeNode node = root;
            while (node.right != null) {
                node = node.right;
            }
            return node;
        }
    }

解释下delete代码中的一段逻辑

return flag == 1 ? pBak : child;

（1）如果待删除的节点只有一个子节点或者没有子节点，则会直接把 p （待删除节点设置为）child节点，所以返回child，继续执行删除，如下图所示

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 9][]

（2）如果待删除的节点有两个子节点，即左孩子和右孩子均存在。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 10][]

此时需要返回位置p，还要继续删除，这里有一个隐藏的点，如果删除元素x，插入时大于等于x的元素都会插入到x节点的右侧，所以可以得知，x节点的右子树，最小的节点也一定是>=x的，所以获取右侧最小的节点时，如果存在重复元素，替换 p 节点的节点一定时 x。

巨人的肩膀：

[24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？-极客时间我们今天来学习二叉查找树。![apple-touch-icon.jpg][]https://time.geekbang.org/column/article/68334][24 _ _-_apple-touch-icon.jpg_https_time.geekbang.org_column_article_68334]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d8e8aa82dc6949daac82c32731491aaa.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8f00d3a7fec547049737f10de0f2f191.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/ceed519129bf411e9f167be47f1220da.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5679cf76691140c8a5bbe736ee471c79.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/8aff448a31b148208852a57f0f98f41d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/9680a308e28c4da2baf5bd5037dd6648.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/3d628f465115423398290e396aa8377e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/4b2a811a16d9436d9ab162246b01576b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/adfdbc9ed32a4d328fdc6d071eb33725.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/16a3ca8e6395412582abc88f170a0772.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/ee30f35146a54cf1a7b44662f1acbccb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/85525dc0f43247a0a5813e317019fb77.png
[icon-default.png_t_L9C2]: https://csdnimg.cn/release/blog_editor_html/release1.9.2/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=L9C2
[https_blog.csdn.net_ycb1914845451_article_details_112583303_icon-default.png_t_L9C2_icon-default.png_t_L9C2_https_blog.csdn.net_ycb1914845451_article_details_112583303]: /images/20220828/95307f29980a408dafecb6831b4f7bd6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/5237f6e1f323437f9c0e2eb08dc36c63.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/432ecdfee4744559a0a1ac8efe4c509d.png
[apple-touch-icon.jpg]: /images/20220828/c5d9153e1c8b48b2a1896385c5b3984b.png
[24 _ _-_apple-touch-icon.jpg_https_time.geekbang.org_column_article_68334]: https://time.geekbang.org/column/article/68334