devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构：图文详解 搜索二叉树（搜索二叉树的概念与性质，查找，插入，删除）

作者：你好赵伟 | 2024-02-18 14:16:17

赞

踩

数据结构：图文详解 搜索二叉树（搜索二叉树的概念与性质，查找，插入，删除）

 

目录

搜索二叉树的相关概念和性质

搜索二叉树的查找

搜索二叉树的插入

搜索二叉树的删除

1.删除节点只有右子树，左子树为空

2.删除节点只有左子树，右子树为空

3.删除节点左右子树都不为空

搜索二叉树的完整代码实现

 

搜索二叉树的相关概念和性质

搜索二叉树（Binary Search Tree，简称BST）是一种树形数据结构，具有以下性质：

  1. 每个节点最多有两个子节点，分别称为左子节点和右子节点
  2. 左子节点的值小于父节点的值，右子节点的值大于父节点的值
  3. 中序遍历搜索二叉树得到的序列是有序的

搜索二叉树提供了快速的插入、删除和搜索操作，因为它能够通过比较节点值来减少搜索的范围。比如，要搜索一个值为x的节点，可以从根节点开始，如果x小于当前节点的值，则继续在左子树中搜索，如果x大于当前节点的值，则继续在右子树中搜索。重复这个过程，直到找到目标节点或者搜索到叶子节点。

插入和删除操作同样也是通过比较节点值来找到合适的位置进行操作的。具体的插入和删除操作可以根据需要进行扩展，保持BST的特性。

BST的时间复杂度取决于树的高度，在最坏情况下（树被构造成链表），时间复杂度为O(n)，其中n是节点的数量。但是在平均情况下，BST的时间复杂度是O(log n)。

搜索二叉树的应用非常广泛，比如数据库索引、缓存等。它提供了高效的数据访问操作，并且能够保持数据的有序性。

如下图就是一颗搜索二叉树，如果我们对这颗搜索二叉树进行遍历的话，我们就会得到 0 1 2 3 4 5 6 7 8 9 的有序队列，也就是我们上述提到的第三条性质。

我们随便拿到其中的一部分进行说明，对于任意一个节点他的左子节点一定小于该节点，而该节点一定小于该节点的右子节点

搜索二叉树的查找

搜索二叉树一般有三种操作：查找，插入，删除

而在其中查找是最为容易的，同时其他俩个操作也都是基于查找实现的。对于一颗搜索二叉树，因为他的规则是否的明确，节点之间是存在明确的大小关系的，所以我们就利用这个大小关系来进行查找操作，具体操作起来有点像二分查找，我们首先拿要查找的值与根节点的值进行比较，如果根节点的值就是我们要查找的元素，那我们就查找成功，然后返回。如果根节点的值<查找的值，那就说明我们要查找的值在根节点的右子树，如果根节点的值>查找的值，那就说明我们要查找的值在根节点的左侧。然后我们反复的将左右子树的根节点带入进行判断。最终我们就可以得出结果。

我们给出如下的图示举例：

对于这样的搜索过程，我们可以分析他的效率，第一次查找我们排除了左边5个节点，第二次查找我们排除了右边2个节点，我们仅仅进行了3次判断就得到了我们想要的结果。这相较于我们常规的数组二分查找，提高了效率和确定性。由此可见搜索二叉树的效率还是非常高的。

对于这样的搜索过程，我们可以给出相应的代码：

  1.     //查找
  2.     public boolean search(int val) {
  3.         TreeNode cur = root;
  4.         while (cur != null) {
  5.             if (cur.val == val) {
  6.                 return true;
  7.             } else if (cur.val < val) {
  8.                 cur = cur.right;
  9.             } else {
  10.                 cur = cur.left;
  11.             }
  12.         }
  13.         return false;
  14.     }

搜索二叉树的插入

对于搜索二叉树的插入，我们需要解决俩个问题：

  1. 找到往哪个节点后插入
  2. 往这个节点后插入时选择左子节点还是右子节点

对于第一个问题，其实本质上就是对节点的查找，查找出合适的插入节点；对于第二个问题，我们需要判断插入节点和目标节点的值的大小关系，另外在代码层面实现时有一点需要注意，我们找到插入节点的位置后，在使用指针指向的时候要避免空指针的问题，我们用下图举例：

假如我们要将节点 “7” 插入到搜索二叉树中，原本节点 “6” 的左右子节点都为空，那我们在插入的时候就不能直接将新节点的值赋给这俩个空节点，不然就会出现 null = newNode 这样的空指针异常，所以我们必须要将插入节点的父节点记录下来，通过父节点的指向来进行插入

  1.     //插入
  2.     public void insert(int val) {
  3.         TreeNode newNode = new TreeNode(val);
  4.         if (root == null) {
  5.             root = newNode;
  6.             return;
  7.         }
  8.         TreeNode cur = root;//记录插入节点
  9.         TreeNode parent = null;//插入节点的父亲节点
  10.         while (cur != null) {
  11.             if (cur.val < val) {
  12.                 parent = cur;
  13.                 cur = cur.right;
  14.             } else if (cur.val > val) {
  15.                 parent = cur;
  16.                 cur = cur.left;
  17.             }else {//重复元素不予插入
  18.                 return;
  19.             }
  20.         }
  21.         //判断在父亲节点的左边还是右边进行插入
  22.         if (parent.val < val) {
  23.             parent.right = newNode;
  24.         } else {
  25.             parent.left = newNode;
  26.         }
  27.     }

搜索二叉树的删除

对于整个搜索二叉树的操作中，删除节点是最麻烦的，因为我们需要对很多种情况进行判断

因为BST中元素与元素之间是存在严谨的大小关系的，所以在我们删除元素之后也应该任然保持这样的关系，为此我们将删除节点可能出现的情况做出分类：

  1. 删除节点只有右子树，左子树为空
  2. 删除节点只有左子树，右子树为空
  3. 删除节点左右子树都不为空

尽管我们对删除节点的状态做出了分类，但这任然不能包含所有的情况，上述三种情况是对删除节点的子树情况做出的分类，事实上删除节点的位置，也就是和父节点的关系也会影响我们的删除过程。以下我们分别对上述三种情况做出进一步的分类：

1.删除节点只有右子树，左子树为空

如图，在这种情况下，我们根据删除节点的位置又可以分出三类：

情况一：当删除节点为根节点的时候，因为删除节点没有左子树，所以我们直接将删除节点的右子节点更新为新的根节点，也就是

root = cur.right;

情况二：当删除节点为父亲节点的左子节点的时候，因为删除节点没有左子树，所以我们直接让父亲节点的左指针指向删除节点的右子节点，也就是

parent.left = cur.right;

情况三：当删除节点为父亲节点的右子节点的时候，因为删除节点没有左子树，所以我们直接让父亲节点的右指针指向删除节点的右子节点，也就是

parent.right = cur.right;

以上便是删除节点左子树为空的情况 

2.删除节点只有左子树，右子树为空

如图，在这种情况下，我们根据删除节点的位置又可以分出三类：

情况一：当删除节点为根节点的时候，因为删除节点没有右子树，所以我们直接将删除节点的左子节点更新为新的根节点，也就是

root = cur.left;

情况二：当删除节点为父亲节点的左子节点的时候，因为删除节点没有右子树，所以我们直接让父亲节点的左指针指向删除节点的左子节点，也就是

parent.left = cur.left;

情况三：当删除节点为父亲节点的右子节点的时候，因为删除节点没有右子树，所以我们直接让父亲节点的右指针指向删除节点的左子节点，也就是

parent.right = cur.left;

3.删除节点左右子树都不为空

在这种情况下，我们往往需要在多个叶子节点中选取一个合适的叶子节点，并且将其替换掉删除节点，最后再将这个叶子节点删除，我们拿下图的情况一举例：

那么我们就需要解决一个问题，如何找到合适的叶子节点，在这里笔者给大家提供一个方法：

  • 找删除节点左子树中的最大值
  • 找删除节点右子树中的最小值

上述俩中方法选择一种即可，我们随便拿其中一种方法分析举例

假如我们找到了删除节点右子树中的最小值，那他就可以同时满足俩个条件， 他比删除节点中的所有右子树节点都小，又因为他在右子树，所以他也大于删除节点的左子节点，那么就同时满足了成为搜索二叉树节点的俩个条件，即该节点大于左子节点，小于右子节点。

在删除节点的时候，我们也需要使用父亲节点来避免出现空指针异常的情况，就如前文提到的那样。当我们找到删除节点后，其实我们还需要对删除节点的位置进行判断，就像上图的情况二和情况三一样，原因很简单，删除操作需要使用指针操作，如果删除节点在父亲节点的右边，那我们就需要更改父亲节点的右指针指向，反之则要更改父亲节点的左指针指向，因此我们对这种情况还得做出判断。

我们将删除节点总的代码给出如下：

  1.     //删除
  2.     public void remove(int val) {
  3.         TreeNode cur = root;
  4.         TreeNode parent = null;
  5.         //先找到要删除的节点的位置
  6.         while (cur != null) {
  7.             if (cur.val < val) {
  8.                 parent = cur;
  9.                 cur = cur.right;
  10.             } else if (cur.val > val) {
  11.                 parent = cur;
  12.                 cur = cur.left;
  13.             }else {
  14.                 //找到要删除的节点了
  15.                 removeNode(parent,cur);//调用函数删除节点
  16.                 return;
  17.             }
  18.         }
  19.     }
  20.     
  21.     private void removeNode(TreeNode parent,TreeNode cur) {
  22.         //对节点的状态进行分类
  23.         if (cur.left == null) {//要删除节点左子树为空树
  24.             if (cur == root) {
  25.                 root = cur.right;
  26.             }else if (cur == parent.left) {
  27.                 parent.left = cur.right;
  28.             }else {
  29.                 parent.right = cur.right;
  30.             }
  31.         }else if (cur.right == null) {//要删除节点右子树为空树
  32.             if (cur == root) {
  33.                 root = cur.left;
  34.             }else if (cur == parent.left) {
  35.                 parent.left = cur.left;
  36.             }else {
  37.                 parent.right = cur.left;
  38.             }
  39.         }else {//要删除节点左右都不为空
  40.             TreeNode temp = cur.right;//用来指向叶子节点
  41.             TreeNode tempParent = cur;//用来指向叶子节点的父节点
  42.             while (temp != null) {
  43.                 tempParent = temp;
  44.                 temp = temp.left;
  45.             }//找到了要替换的节点
  46.             cur.val = temp.val;
  47.             //替换完成后就删除叶子节点
  48.             if (tempParent.left == temp) {
  49.                 tempParent.left = temp.right;//删除叶子节点
  50.             }else {
  51.                 tempParent.right = temp.right;//删除叶子节点
  52.             }
  53.         }

前半部分是用来找到删除节点，后半部是根据我们的分析对删除节点的情况做出分类判断然后进行删除操作。

搜索二叉树的完整代码实现

为了方便读者使用，我们这里将整个搜索二叉树的完整代码给出：

  1. public class BinarySearchTree {
  2.     static class TreeNode {
  3.         int val;
  4.         TreeNode left;
  5.         TreeNode right;
  6.         
  7.         public TreeNode(int val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.     
  12.     public TreeNode root;
  13.     
  14.     //查找
  15.     public boolean search(int val) {
  16.         TreeNode cur = root;
  17.         while (cur != null) {
  18.             if (cur.val == val) {
  19.                 return true;
  20.             } else if (cur.val < val) {
  21.                 cur = cur.right;
  22.             } else {
  23.                 cur = cur.left;
  24.             }
  25.         }
  26.         return false;
  27.     }
  28.     
  29.     //插入
  30.     public void insert(int val) {
  31.         TreeNode newNode = new TreeNode(val);
  32.         if (root == null) {
  33.             root = newNode;
  34.             return;
  35.         }
  36.         TreeNode cur = root;//记录插入节点
  37.         TreeNode parent = null;//插入节点的父亲节点
  38.         while (cur != null) {
  39.             if (cur.val < val) {
  40.                 parent = cur;
  41.                 cur = cur.right;
  42.             } else if (cur.val > val) {
  43.                 parent = cur;
  44.                 cur = cur.left;
  45.             }else {//重复元素不予插入
  46.                 return;
  47.             }
  48.         }
  49.         //判断在父亲节点的左边还是右边进行插入
  50.         if (parent.val < val) {
  51.             parent.right = newNode;
  52.         } else {
  53.             parent.left = newNode;
  54.         }
  55.     }
  56.     
  57.     //删除
  58.     public void remove(int val) {
  59.         TreeNode cur = root;
  60.         TreeNode parent = null;
  61.         //先找到要删除的节点的位置
  62.         while (cur != null) {
  63.             if (cur.val < val) {
  64.                 parent = cur;
  65.                 cur = cur.right;
  66.             } else if (cur.val > val) {
  67.                 parent = cur;
  68.                 cur = cur.left;
  69.             }else {
  70.                 //找到要删除的节点了
  71.                 removeNode(parent,cur);//调用函数删除节点
  72.                 return;
  73.             }
  74.         }
  75.     }
  76.     
  77.     private void removeNode(TreeNode parent,TreeNode cur) {
  78.         //对节点的状态进行分类
  79.         if (cur.left == null) {//要删除节点左子树为空树
  80.             if (cur == root) {
  81.                 root = cur.right;
  82.             }else if (cur == parent.left) {
  83.                 parent.left = cur.right;
  84.             }else {
  85.                 parent.right = cur.right;
  86.             }
  87.         }else if (cur.right == null) {//要删除节点右子树为空树
  88.             if (cur == root) {
  89.                 root = cur.left;
  90.             }else if (cur == parent.left) {
  91.                 parent.left = cur.left;
  92.             }else {
  93.                 parent.right = cur.left;
  94.             }
  95.         }else {//要删除节点左右都不为空
  96.             TreeNode temp = cur.right;//用来指向叶子节点
  97.             TreeNode tempParent = cur;//用来指向叶子节点的父节点
  98.             while (temp != null) {
  99.                 tempParent = temp;
  100.                 temp = temp.left;
  101.             }//找到了要替换的节点
  102.             cur.val = temp.val;
  103.             //替换完成后就删除叶子节点
  104.             if (tempParent.left == temp) {
  105.                 tempParent.left = temp.right;//删除叶子节点
  106.             }else {
  107.                 tempParent.right = temp.right;//删除叶子节点
  108.             }
  109.         }
  110.     }
  111. }

 本次的分享就到此为止了，希望我的分享能给您带来帮助，也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号