二叉排序树 为什么要引入二叉排序树 我们前面已经介绍了很多数据结构，比如数组、链表、散列表等，数组查找性能高，但是插入、删除性能差，链表插入、删除性能高，但查找性能差，在不考虑散列冲突的话，散列表的插入、删除、查找性能都很高，但是前提是没有散列冲突，此外，散列表存储的数据是无序的，散列表的扩容非常麻烦，涉及到散列冲突时，性能不稳定，另外，散列表用起来爽，构造起来可不简单，要考虑散列函数的设计、哈希冲突的解决、扩容缩容等一系列问题，有没有一种插入、删除、查找性能都不错，构建起来也不是很复杂，性能还很稳定的数据结构呢？这就是我们今天要介绍的数据结构 —— 二叉排序树。 什么是二叉排序树 二叉排序树是一种特殊的二叉树，我们重点「排序」二字，二叉排序树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值，所以这么看来，二叉排序树是天然有序的，如果按照昨天讲的中序遍历，得到将是一个从小到大的有序数据集。但是构造二叉排序树的目的，并不是为了排序，而是为了提高查找、插入和删除的速度。不管怎么说，在一个有序数据集上查找数据肯定比无序数据集要快，同时二叉排序树这种非线性结构，也非常有利于插入和删除的实现。 注：二叉排序树也叫做二叉查找树，二叉搜索树，你如果看到类似概念，它们是一个意思。 下面我们就来看看如何实现二叉排序树的插入、查找和删除以及它们对应的时间复杂度。 二叉排序树的插入 首先我们先定义好基本的类结构，还是通过二叉链表来存储二叉排序树，对应的节点类如下： 然后，我们定义下二叉排序树对应类的基本结构： 然后我们按照二叉排序树的定义，实现对应二叉排序树节点的插入方法： 如果是空树，则将其作为根节点，否则判断插入节点数据与当前节点数据的大小，如果小于当前节点，则递归遍历左子树，找到对应的位置插入，如果大于当前节点，则递归遍历右子树找到对应的位置插入。 我们可以写一段简单的测试代码测试节点插入： 
二叉排序树的查找 二叉排序树的删除比较复杂，我们先来看查找实现，查找实现非常简单，和插入类似，依次递归比较就好了，直到直到对应节点，或者返回空，表示没有找到： 还是借助前面的测试代码，我们可以通过 打印找到节点的对象信息。 二叉排序树的删除 二叉排序树的删除相对而言要复杂一些，需要分三种情况来处理： 第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。（同理，也可以通过待删除节点的左子树中的最大节点思路来实现） 
下面我们给出删除逻辑实现代码： 二叉排序树的时间复杂度 不论是插入、删除、还是查找，二叉排序树的时间复杂度都等于二叉树的高度，最好的情况当然是满二叉树或完全二叉树，此时根据完全二叉树的特性，时间复杂度是 O(logn)，性能相当好，最差的情况是二叉排序树退化为线性表（斜树），此时的时间复杂度是 O(n)，所以二叉排序树的形状也很重要，不同的形状会影响最终的操作性能，所以下一篇我们将讨论如何实现平衡的二叉排序树 —— 平衡二叉树。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/60675.html
