二叉排序树是用来排序的吗为什么不一样_二叉排序树是用来排序的吗为什么不一样

Python 树表查找_千树万树梨花开，忽如一夜春风来（二叉排序树、平衡二叉排序树）
　　什么是树表查询？

　　借助具有性质的进行关键字查找。

　　本文所涉及到的特殊结构性质的树包括：。。

　　使用上述存储数据时，对其本身对结点之间的关系以及顺序有特殊要求，也得益于这种限制，在查询某一个结点时会带来性能上的优势和操作上的方便。

　　树表查询属于算法。

　　所谓，不仅仅能很方便查询到目标结点。而且可以根据需要添加、删除结点，而不影响树的整体结构，也不会影响数据的查询。 本文并不会深入讲解的基本的概念，仅是站在使用的角度说清楚动态查询。阅读此文之前，请预备一些树的基础知识。

　　1. 二叉排序树

　　是树结构中具有艳明特点的子类。

　　要求树的每一个结点（除叶结点）的子结点最多只能有 个。在的基础上，继续对其进行有序限制则变成。

　　二叉排序树特点：

　　基于结构，从根结点开始，从上向下，每一个父结点的值大于左子结点（如果存在左子结点）的值，而小于右子结点（如果存在右子结点）的值。则把符合这种特征要求的树称为。

　　1.1 构建一棵

　　如有数列 。通过下面流程，把每一个数字映射到的结点上。如果树为空，把第一个数字作为根结点。如下图，数字 作为根结点。 如果已经存在根结点，则把数字和根结点比较，小于根结点则作为根结点的左子结点，大于根结点的作为根结点的右子结点。如数字 插入到左边，数字 插入到右边。 数列中后面的数字依据相同法则，分别插入到不同子的位置。

　　原始数列中的数字是无序的，根据的插入算法，最终可得到一棵有排序性质的树结构。对此棵树进行就可得到从小到大的一个递增有序数列。 综观，进行关键字查找时，也应该是接近于二分查找算法的时间度。 这里有一个要注意的地方。 原始数列中的数字顺序不一样时，生成的二叉排序树的结构也会有差异性。对于查找算法的性能会产生影响。

　　1.2 二叉排序树的数据结构

　　现在使用设计方案描述二叉排序树的数据结构。

　　首先，设计一个结点类，用来描述结点本身的信息。

　　结点类中有 个属性：：结点上附加的数据信息。：左子结点，初始值为 。：右子结点，初始值为 。

　　二叉排序树类： 用来实现树的增、删、改、查。

　　二叉排序树中可以有更多方法，本文只与查找主题有关的方法。

　　1.3 实现二叉排序树类中的方法：

　　初始化方法：

　　在初始化树对象时，如果指定了数据信息，则创建有唯一结点的树，否则创建一个空树。

　　关键字查询方法：查询给定的关键字在二叉排序树结构中是否存在。

　　查询流程：把给定的关键字和根结点相比较。如果相等，则返回查找成功，结束查询.如果根结点的值大于关键字，则继续进入根结点的左子树中开始查找。如果根结点的值小于关键字，则进入根结点的右子树中开始查找。如果没有查询到关键字，则返回最后访问过的结点和查询不成功信息。

　　关键字查询的本质是二分思想，以当前结点为分界线，然后向左或向右进行分枝查找。

　　非递归实现查询方法：

　　注意：当没有查询到时，返回的值有 个，最后访问的结点和没有查询到的信息。 为什么要返回最后一次访问过的结点？ 反过来想想，本来应该在这个地方找到，但是没有，如果改成插入操作，就应该插入到此位置。

　　基于递归实现的查找：

　　再看看如何把数字插入到二叉排序树中，利用二叉排序树进行查找的前提条件就是要把数字映射到二叉排序树的结点上。

　　插入结点的流程：当需要插入某一个结点时，先搜索是否已经存在于树结构中。如果没有，则到查询时访问过的最一个结点，并和此结点比较大小。如果比此结点大，则插入最后访问过结点的右子树位置。如果比此结点小，则插入最后访问过结点的左子树位置。

　　方法的实现：

　　再看一下前面根据插入原则手工绘制的插入演示图：

　　上图有 个子结点，写几行代码测试一下，看从根结点到叶子结点的顺序是否正确。

　　测试插入方法：

　　查看结果，可以初步判断插入的数据是符合二叉排序树特征的。当然，更科学的方式是写一个遍历方法。树的遍历方式有 种：前序：根，左，右。中序：左，根，右。后序。左，右，根。

　　对进行中序遍历，理论上输出的数字应该是有序的。这里写一个中序遍历，查看输出的结点是不是有序的，从而验证查询和插入方法的正确性。

　　使用递归实现中序遍历：

　　测试插入的顺序：

　　二叉排序树很有特色的数据结构，利用其存储特性，可以很方便地进行查找、排序。并且随时可添加、删除结点，而不会影响排序和查找操作。基于树表的查询操作称为动态查找。

　　二叉排序树中如何删除结点

　　从二叉树中删除结点，需要保证整棵二叉排序树的有序性依然存在。删除操作比插入操作要复杂，下面分别讨论。如果要删除的结点是叶子结点。

　　只需要把要删除结点的父结点的左结点或右结点的引用值设置为空就可以了。删除的结点只有一个右子结点。如下图删除结点 。

　　因为结点没有左子树，在删除之后，只需要把它的右子结点替换删除结点就可以了。删除的结点即存在左子结点，如下图删除值为 的结点。

　　一种方案是：找到结点 的左子树中的最大值，即结点 （该结点的特点是可能会存在左子结点，但一定不会有右子结点）。用此结点替换结点 便可。 为什么要这么做？ 道理很简单，既然是左子树中的最大值，替换删除结点后，整个二叉排序树的特性可以继续保持。

　　如果结点 存在左子结点，则把它的左子结点作为结点的右子结点。

　　另一种方案：同样找到结点中左子树中的最大值结点 ，然后把结点 的右子树作为结点 的右子树。

　　再把结点 的左子树移到 位置。

　　这种方案会让树增加树的深度。所以，建议使用第一种方案。

　　删除方法的实现：

　　测试删除后的二叉树是否依然操持其有序性。

　　无论删除哪一个结点，其二叉排序树的中序遍历结果都是有序的，很好的印证了删除算法的正确性。

　　3. 平衡二叉排序树

　　中进行查找时，其理论上接近的时间复杂度，其查找时间与树的深度有关。但是，这里有一个问题，前面讨论过，如果数列中的数字顺序不一样时，所构建出来的二叉排序树的深度会有差异性，对最后评估时间性能也会有影响。

　　如有数列 构建的二叉排序树如下图：

　　基于上面的树结构，查询任何一个结点的次数不会超过 次。

　　稍调整一下数列中数字的顺序 ，由此构建出来的树结构会出现一边倒的现象，也增加了树的深度。

　　此棵树的深度为，最多查询次数是 次。在二叉排序树中，减少查找次数的最好办法，就是尽可能维护树左右子树之间的对称性，也就让其有平衡性。

　　所谓平衡二叉排序树，顾名思义，基于二叉排序树的基础之上，维护任一结点的左子树和右子树之间的深度之差不超过 。把二叉树上任一结点的左子树深度减去右子树深度的值称为该结点的平衡因子。

　　平衡因子只可能是: ：左、右子树深度一样。：左子树深度大于右子树。：左子树深度小于右子树。

　　如下图，就是，根结点的 个子树深度相差为 ， 结点 的左、右子树深度为 1，结点 的左右子树深度相差为 。

　　平衡二叉排序树相比较于二叉排序树，其 多了保持平衡的算法。

　　3.1 二叉平衡排序树的数据结构

　　结点类：

　　结点类中有 个属性：：结点上附加的值。：左子结点。：右子结点。：平衡因子，默认平衡因子为 。

　　二叉平衡排序树类：

　　在插入或删除结点时，如果导致树结构发生了不平衡性，则需要调整让其达到平衡。这里的方案可以有 种。

　　：左边不平衡时，向右边旋转。

　　如上图，现在根结点 的平衡因子为 。如果现插入值为 结点，显然要作为结点 的左子结点，才符合二叉排序树的有序性。但是破坏了根结点的平衡性。根结点的左子树深度变成 ，右子树深度为，平衡被打破，结点 的平衡因子变成了。

　　这里可以使用旋转方式，让其继续保持平衡，旋转流程：让结点 成为新根结点，结点成为结点的左子结点。结点成为结点的新左子结点。

　　旋转后，树结构即满足了有序性，也满足了平衡性。

　　旋转算法具体实现：

　　：旋转和 旋转的算法差不多，只是当右边不平衡时，向左边旋转。

　　如下图所示，结点 插入后，树的平衡性被打破。

　　这里使用左旋转（逆时针）方案。结点 成为结点 的左子结点，结点 原来的左子结点成为结点的右子结点。

　　向逆时针旋转后，结点的平衡因子为 ，结点的平衡因子为，结点 的平衡因子为 。树的有序性和平衡性得到保持。

　　旋转算法具体实现：

　　：如下图当插入结点 后，结点 的平衡因子变成 ，则时可以使用 旋转算法。

　　以结点 作为新的根结点，结点以结点为旋转中心，逆时针旋转。

　　结点以结点这旋转中心向顺时针旋转。

　　最后得到的树还是一棵。

　　旋转算法实现：

　　型调整： 如下图插入结点 后，整棵树的平衡打破，这时可以使用 旋转算法进行调整。

　　把结点设置为新的根结点，结点以结点 为中心点顺时针旋转，结点逆时针旋转。

　　算法具体实现：

　　编写完上述算法后，就可以编写插入算法。在插入新结点时，检查是否破坏二叉平衡排序树的的平衡性，否则调用平衡算法。 当插入一个结点后，为了保持平衡，需要找到最小不平衡子树。 什么是最小不平衡子树？ 指离插入结点最近，且平衡因子绝对值大于 的结点为根结点构成的子树。

　　中序遍历： 此方法为了验证树结构还是排序的。

　　二叉平衡排序树本质还是二树排序树。如果使用中序遍历输出的数字是有序的。测试代码。

　　4. 总结

　　利用的特性，可以实现。在添加、删除结点之后，理论上查找到某一个结点的时间复杂度与树的结点在树中的深度是相同的。但是，在构建二叉排序树时，因原始数列中数字顺序的不同，则会影响二叉排序树的深度。这里引用二叉平衡排序树，用来保持树的整体结构是平衡，方能保证查询的时间复杂度为 ( 为结点的数量)。