动画 | 什么是二分搜索树（附伪代码）

灰太狼 2023-06-22 04:28 9阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

来源 | 算法无遗策

二分搜索树属性

![format_png 1][]

![format_png 2][]

二分搜索树的又名比较多，有的叫二叉排序树，也有的叫二叉查找树，或者有序二叉查找树。是指一棵空树或者具有下列性质的二叉树：

1.若任意节点的左子树不空，则左子树所有节点的值均小于它根节点的值；

2.若任意节点的右子树不空，则右子树所有节点的值均大于它根节点的值；

3.任意节点的左、右子树也分别为二叉查找树；

4.没有键值相等的节点。

它的查找、插入和删除的时间复杂度都等于树高，期望值是O(logn)，最坏时间复杂度是O(n)，比如树退化成线性表。

![format_png 3][]

查找元素

二分搜索树是为了实现快速查找而生的，也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较，如果相等的话就返回；如果待查元素要比根节点小，就进行左子树递归查找；如果待查元素要比根节点大，就进行右子树的递归查找；如果查找到最后还没有一个符合的元素，就返回null。

递归查找

递归查找的方式有很多，有层序遍历、前序遍历、中序遍历和后序遍历。我这里就举后面三个遍历方式。

Code

如果代码是下面这样写的，那它遍历过程是怎么样的？看下面动画。

![format_png 4][]

动画：前序遍历

（响应读者的建议，动画不放BGM了![format_png 5][]![format_png 5][]![format_png 5][]![format_png 5][]![format_png 5][]）

动画：前中后遍历

从上面动画就发现，通过中序遍历得到的正好是一个升序序列。如果不考虑升序，后序遍历也能够为二分搜索树早点释放内存，早点减少栈的使用空间。

**Code**

![format_png 6][]

添加元素

对于二叉树的添加和删除元素，使用链表存储形式比较好操作的，如果使用数组形式存储，删除某一个有子树的元素会引发一系列的位置改变，涉及到交换元素的位置，性能也比链表的小。所以待会后面出现的伪代码都以链表存储形式去操作。

Code

![format_png 7][]

删除元素：删除最小和最大的元素

删除最小和最大的元素很简单，如果是删除最小的元素，从二叉树的顶点出发，一直递归它的左孩子，直到某节点的左孩子为空，这时候这个节点就是最小的元素。删除最大的元素也是一样的，一直递归它的右孩子，直到某节点的右孩子为空。

删除任意元素

如果删除任意元素，而这元素正好有左右子树的，那该是怎么般呢？

1962年，Hibbard提出了HibbardDeletion的解决方法。

看到Hibbard名字就想起来，我在[希尔排序介绍过Hibbard增量序列][Hibbard]，也把它相应的公式通过代码体现出来，代替希尔增量序列去进行希尔排序，最坏时间复杂度也比希尔增量序列的要小。

回到删除有左右子树的元素，想想它的左右子树也属于二叉排序树（也是二分搜索树），它左子树的最大值比它小，它右子树的最小值比它大。所以不管选择左子树的最大值还是选择右子树的最小值，替换掉要删除的元素，整个二叉树都是符合二分搜索树的规则。

动画：删除元素

Code：删除任意元素

![format_png 8][]

支持重复元素的二分搜索树

二分搜索树有一个规则是：没有键值相等的节点。那么就不建议把待添加的元素跳过值相等的节点，到下一步继续比较直到插入新的节点。比如我想插入23，插完之后上有23，下有23，那查找就没有意义了，也破坏了时间复杂度上的O(logn)。

建议就是在节点上加一个属性：count。当插入23的时候，count就可以自算++。这不仅满足了没有键值相等的规则，也满足时间复杂度的期望值。

![format_png 9][]

Code

![format_png 10][]

![音符][format_png 11]

**有热门推荐????**

1.【程序员】[我们就必须承认：这个世界上，有很多问题，就是无解的][Link 1]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了！][Link 2]

![format_png 12][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9VUzEwR2NkMHRRRWZjZmZ1ZVkwcmVEYVQ4YWdIaWJNYmtsNlZQSmljSWFTTEJPTVQ0NmhLc3Q1d2pUenRpYmVkMmRKc3JrZTZCMG5ScFJQdkpYbkMybWxTZy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXJoUlRrS2twNUFMRjRGNmliRExJenE4M0poYTVuZnFpY3VEemdKYUhJcUlxbTh0VTdJZDNGZjRZdy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXJNRFJWS0NQdUFUR3hDbEdzd3lYMUtxQ2pMNU1QdkNLaWNVMG16Z0M2cVRqMkg1bURjOFptWVR3LzY0MD93eF9mbXQ9Z2lm?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXJEVmNkVHlxUnhUZlRKdVZpY21OdmNDNldmeENURzUzVG5wUVBHTWE5UEI1eUk4OUxuYndqc1JnLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yZXMud3gucXEuY29tL21wcmVzL2h0bWxlZGl0aW9uL2ltYWdlcy9pY29uL2NvbW1vbi9lbW90aW9uX3BhbmVsL2Vtb2ppX3d4LzJfMDQucG5n?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXJhVklvemljOHVCcXltNE5JRFRDVjBnMlFrS3BnSGV1ZHc5eEU1QThuMTRWV3E3czBSd1d4S0NBLzY0MD93eF9mbXQ9cG5n?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXI0STlucjVuRnRBUkFadlhWdUpoRExlZExLeTFpY2J4c2huZjYxYXJ2OWFpY1VkU1JEZ3puVWNEZy82NDA?x-oss-process=image/format,png
[Hibbard]: http://mp.weixin.qq.com/s?__biz=MzU3MDkxMDg2OA%3D%3D&chksm=fce97360cb9efa761b99a0d29296e167e325762482ce7fbf89f2a675164f315cc4f5dc102974&idx=1&mid=2247484059&scene=21&sn=aa4d8c0e5a6afce9b442480369a225c4#wechat_redirect
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXJGTW5ZbW4yakdGd0ZGc2phTFgwaEdpYlJKNXI3QlJ5MFA5bXVBWk9Oa01ESnJOSFVCcU9PYkdRLzY0MA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXJDTFdHTURpY2lhaDVpYVppYVM3MEJDNnJNWWRwZzBNT2JYUnFNdG80NGtUOE5JZzVSNnBoVEVScHdRLzY0MA?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbXVUeGpOQUtPMzlpYXlnZVdjUnRjNXJiaWJlZDNFdXFzblNsdTh4NElNc1B4TmZpYmlhRnNDYVRNUGJva3hzeGwxeWt3UzMwa1h5bGpNZ1EvNjQw?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6L2NaVjJoUnB1QVBpYUpRWFdHeUM5d3JVeklpY2liZ1hheXJnaWJUWWFyVDNBMXl6dHRidGFPMEpsVjIxd01xcm9HWVQzUXRQcTJDN0hNWXN2aWNTQjJwN2RUQmcvNjQwPw?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/100978627
[GitHub]: https://blog.csdn.net/kexuanxiu1163/article/details/100137152
[KMP]: https://blog.csdn.net/kexuanxiu1163/article/details/97071390
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/103051357
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVR1U2ljRUtJcWdpYU9FdG9KaWEwTGcxYTJkWkVLcXlwYzlFcDUzVkpsb0Vobzg4VkdYeVpFSHB2d1paVXR6VnR2RTVJRWliQU5kbFdwUVJRLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png