24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？
王争
该思维导图由 AI 生成，仅供参考
上一节我们学习了树、二叉树以及二叉树的遍历，今天我们再来学习一种特殊的二叉树，二叉查找树。二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。
我们之前说过，散列表也是支持这些操作的，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 O(1)。既然有了这么高效的散列表，使用二叉树的地方是不是都可以替换成散列表呢？有没有哪些地方是散列表做不了，必须要用二叉树来做的呢？
带着这些问题，我们就来学习今天的内容，二叉查找树！
二叉查找树（Binary Search Tree）
二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？
这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。 我画了几个二叉查找树的例子，你一看应该就清楚了。
前面我们讲到，二叉查找树支持快速查找、插入、删除操作，现在我们就依次来看下，这三个操作是如何实现的。
1. 二叉查找树的查找操作
首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
二叉查找树是一种常用的数据结构，通过特殊的结构实现了快速的插入、删除和查找操作。文章详细介绍了二叉查找树的操作方法，包括查找、插入、删除，以及支持重复数据的处理方式。此外，还介绍了二叉查找树的其他操作，如查找最大节点和最小节点、前驱节点和后继节点，以及中序遍历输出有序的数据序列。文章深入浅出地解释了二叉查找树的实现原理和操作方法，适合读者快速了解和掌握二叉查找树的基本知识。 在时间复杂度分析部分，文章对二叉查找树的插入、删除、查找操作的时间复杂度进行了分析，探讨了不同情况下的执行效率。此外，文章还对比了二叉查找树和散列表的优劣，指出了二叉查找树在有序输出、稳定性和复杂性方面的优势。 总结部分强调了二叉查找树的时间复杂度与树的高度成正比，介绍了极端情况下的时间复杂度，并提出了为避免时间复杂度退化而设计的平衡二叉查找树。最后，作者提出了课后思考问题，引发读者思考并留言交流。 整体而言，本文通过深入浅出的方式介绍了二叉查找树的基本知识和相关操作，同时对比了其与散列表的优劣，适合读者快速了解和掌握相关内容。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(241)
- 最新
- 精选
失火的夏天确定二叉树高度有两种思路：第一种是深度优先思想的递归，分别求左右子树的高度。当前节点的高度就是左右子树中较大的那个+1；第二种可以采用层次遍历的方式，每一层记录都记录下当前队列的长度，这个是队尾，每一层队头从0开始。然后每遍历一个元素，队头下标+1。直到队头下标等于队尾下标。这个时候表示当前层遍历完成。每一层刚开始遍历的时候，树的高度+1。最后队列为空，就能得到树的高度。作者回复: 👍 大家可以看看这条留言
2018-11-1437603
拉欧递归法，根节点高度=max(左子树高度，右子树高度)+1作者回复: 👍 精髓
2018-11-14287
Smallfly老师我有一个疑问，二叉树删除时，如果待删除节点有两个子节点，能否用左子树中的最大值来替换待删除节点呢？作者回复: 好像也可以 👍
2018-11-1516149
Monday1、思考题：leetcode 104 题，可以使用递归法。 递归公式： depth =Math.max(maxDepth(node.left), maxDepth(node.right) )+ 1; 递归出口： depth = 0 (node == null) 2、二叉查找树的删除操作（无重复的数据）leetcode 450。 根据老师的思路，先不看代码，自己写了好长段时间，写出来都跑过leetcode的所有案例。回过头来再看老师的删除的代码，感觉到了巧妙之处就是：当删除节点有两个子节点的情况，很巧得一起套用了删除结点子节点个数小于1的两种场景。作者回复: 是的 钻研精神值得称赞👍
2018-11-1710138
Geek_41d472p.data = minP.data; // 将 minP 的数据替换到 p 中 p = minP; // 下面就变成了删除 minP 了 pp = minPP; 总于看明白这段代码了……各位老铁，单纯看这3行代码是看不出是删除后继节点的，是要结合后面的代码来看的……不过说实话这种代码是不好看的懂……作者回复: 😄 是不好看懂
2018-11-15832
陆老师有一种更容易理解复杂度的思路，二叉查找树类似二分法搜索，每次缩小一半的区间，而二分查找法时间复杂度就是logN作者回复: 是的，👍
2019-03-13324
一个慢慢爬行的普通人p = minP; // 下面就变成了删除 minP 了... pp = minPP; 老师，对这里不太搞懂，似乎也有些人对这里感到困惑，老师可以对这两句集中解释下嘛作者回复: 好的。我们用后继节点替换到要删除节点的位置。 然后就变成删除后继节点的问题了。为了逻辑统一 代码书写简洁。我们把后继节点赋给了p
2018-11-14317
莫弹弹在sf的微信公众号上刚好看到二叉树相关的文章，二叉树常规操作都有了，基本思路是： - 只有一个根结点时，二叉树深度为 1 - 只有左子树时，二叉树深度为左子树深度加 1 - 只有右子树时，二叉树深度为右子树深度加 1 - 同时存在左右子树时，二叉树深度为左右子树中深度最大者加 1 https://mp.weixin.qq.com/s/ONKJyusGCIE2ctwT9uLv9g作者回复: 👍
2018-11-14312
PhilZhang对于二叉搜索树各种操作的复杂度，有更容易理解的解释方法:每次操作后数据量都减少了一半，所以复杂度自然是logN。作者回复: 👍
2018-11-18211
TryTs老师我想请教一下你，就你而言，编程最大的乐趣在什么地方？你用编程做过最有创意的项目是什么？作者回复: 编程能带来成就感 而且这种成就感很容易获得 最有创意的我一时半会还真想不起来 感觉做的项目都一般
2018-11-1839
收起评论
