【LSP】排序二叉树和平衡二叉树

3366255622   ·   发表于 1个月前   ·   编程代码

概述
对于一组元素 [7, 3, 10, 12, 5, 1, 9] 可以有很多种存储方式,但无论使用哪种数据结构,都或多或少有缺陷。比如使用线性结构存储,排序方便,但查找效率低。二叉排序树的特点就是能在保证元素有序的同时,提高查找的效率。

2|0二叉排序树的定义
二叉排序树,也叫二叉查找树,二叉搜索树,英文名 Binary Sort Tree(BST)。它或者是一颗空树,或者是一颗具有以下性质的二叉树

若左子树不为空,则左子树上所有结点的值均小于它的根结点的值
若右子树不为空,则右子树上所有结点的值均大于它的根结点的值
左、右子树也分别为二叉排序树
序列 [7, 3, 10, 12, 5, 1, 9] 以二叉排序树存储的结构如图:


3|0创建二叉排序树 & 添加 & 查找 & 遍历
值得注意的是,对二叉排序树作中序遍历,结果正好是一个有序序列。

删除结点
二叉排序树的删除操作相对麻烦些,我们不能像以前那样直接删除结点对应的整个子树,而是要把子结点保留下来,并重新拼接成新的排序二叉树。针对不同的情况,也有不同的应对策略:

删除叶子结点。直接砍掉就好了,不会对其他结点有影响。
删除只有一个子结点的结点。子结点代替原结点的位置。
删除有两个子结点的结点。被删除结点同时也是对应二叉排序子树的根结点,根据二叉排序树的性质,根结点就是序列的中间值,所以要补上中间值的位置,要用中间值的后一位的元素(对应右子树的最小结点)或前一位元素(对应左子树的最大结点)

平衡二叉树
上述的排序二叉树,如果结构良好,那么检索数据时的时间开销为 O(logn),其中 n 为结点个数。但如果排序二叉树的结构畸形,那么最坏时间开销可能为 O(n),如下图所示:


这样也满足二叉排序树的定义,但和单链表无异,如果是这样的话,那使用排序二叉树还有什么意义呢?所以我们下一步要思考的是如何保证一颗排序二叉树结构良好

平衡二叉树,也叫 AVL 树,除了具有二叉排序树的性质以外,它要求每一个结点的左右子树的高度之差的绝对值不超过一

每一次插入新元素后,树的平衡都有可能被破坏,因此每次插入时都要通过旋转来维持平衡二叉树的结构。假设需平衡的结点为 8,那么破坏平衡的情况有四种:

左左:对 8 的左儿子的左子树进行一次插入
左右:对 8 的左儿子的右子树进行一次插入
右左:对 8 的右儿子的左子树进行一次插入
右右:对 8 的右儿子的右子树进行一次插入

要解决上述的问题,找到距离新插入结点最近的不平衡子树进行旋转,对于左左情况使用右旋转,右右情况使用左旋转,可以统称为单旋转。左右和右左情况则使用双旋转。左旋转和右旋的旋转方式是互为镜像的,掌握其中一个,另一个自然也会了。左右、右左也是如此

以左左为例讲解单旋转:

找到最近的不平衡子树 8

创建一个新结点,值等于当前结点的值,即是 8

把新结点的右子树设置为当前结点的右子树,即是 9

把新结点的左子树设置为当前结点的左子树的右子树,即是 7,到这里得出下面结果



再接下来目的就很明确了,将 6 当作根结点,新结点作为 6 的右儿子,这样就完成了一次右旋转,可以想象成 8 向右转了一个角度


双旋转其实就是做两次旋转,对于左右情况,先对 6 做一次左旋转,然后才是 8 做一次右旋转;对于右左情况,先对 8 做一次右旋转,然后才是 5 做一次左旋转

0 Reply   |  Until 29天前 | 4442 View
LoginCan Publish Content