python常用算法(5)——树,二叉树与AVL树(三)

简介: python常用算法(5)——树,二叉树与AVL树

python常用算法(5)——树,二叉树与AVL树(二)https://developer.aliyun.com/article/1542699

5,AVL树

5.1  AVL树的定义

  在计算机科学中,AVL树(发明此树的三位科学家的名字首字母)是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度为1,因此他也被称为高度平衡树。查找,插入和删除在平均和最坏的情况下的时间复杂度都是 O(log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。

  节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1, 0或者-1的节点被认为是平衡的。带有平衡因子 -2 或 2的节点被认为是不平衡的,并需要重新平衡这个树,平衡因子可以直接存储在每个节点中,或从可能存储在节点的子树高度计算出来。

  AVL树是一颗自平衡的二叉搜索树。一般要求每个节点的左子树和右子树的高度最多差1(空树的高度定义为 -1)。在高度为 h 的AVL树中,最少的节点数 S(h) = S(h-1) + S(h-2) + 1 得到,其中 S(0) = 1, S(1) = 2。

  如下图所示,分别为高度为0, 1, 2, 3的AVL树所需要的最少节点数:

5.2  AVL树的性质
  1. AVL树本质上还是一颗二叉搜索树
  2. 根的左右子树的高度之差的绝对值(平衡因子)不能超过1
  3. 根的左右子树都是平衡二叉树(二叉排序树,二叉搜索树)
5.3  AVL树的复杂度
5.3  旋转

  旋转是AVL树最重要的操作了,理解了旋转就理解了AVL树的实现原理。

左单旋转

  下图节点上面的数字表示平衡因子

  如上图所示,插入13后,右边子树11节点的平衡因子变为了2(左右节点的高度差),整个AVL树开始不平衡,这时便要开始以12为轴心进行一次左单旋转。具体旋转操作时原来11的父节点10指向12,12的左节点指向11,而11的右节点指向原来的12的左节点(此例中,12的左节点为空)。

右单旋转

  上图中插入3后左子树不平衡了,根节点8的平衡因子变为了-2,此时应该以6为轴心向右单旋转一次,具体操作与左单旋转类似:8的左节点指向6的有节点(此时为7),6的右节点指向8,由于8原来是跟节点,没有父节点,所以根节点指向6.旋转后6和8节点都恢复0的平衡因子了。

左右双旋转

  如上图所示,10节点的平衡因子是 -2,而它的左节点的平衡因子却为1,两个节点失去平衡的方向不一样,所以要先以7位轴心对节点6左单旋转一次,再以7为轴心对节点10右旋转一次。操作细节与上面单次循环一样。注意此时操作的3个结点的平衡因子要根据不同7的平衡因子单独调整。

右左双旋转

  如上图所示,当一个节点的平衡因子为2,而它的右子节点的平衡因子为-1时,就需要先进行右旋转,再左旋转。注意中间节点13右旋转后的平衡因子变为1了。代码同左右双旋转类似。

5.4  AVL树——插入

  插入一个节点可能会破坏 AVL树的平衡,可以通过旋转操作来进行修正。

  插入一个节点后,只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点,称之为K,K的两棵子树的高度差2.

  不平衡的出现可能有四种情况:

1,对K的左儿子的左子树进行一次插入

2,对K的左儿子的左子树进行一次插入

3,对K的右儿子的左子树进行一次插入

4,对K的右儿子的右子树进行一次插入

  情况1和4是对称的,需要进行一次单旋转操作,情况2与3需要一次双旋转操作。

AVL插入——左旋

  不平衡是由于对K的右孩子的右子树插入导致的:左旋

  那代码过程如下图所示:

  代码如下:

#_*_coding:utf-8_*_
from bst import BiTreeNode, BST
class AVLNode(BiTreeNode):
    def __init__(self, data):
        BiTreeNode.__init__(self, data)
        self.bf = 0
 
class AVLTree(BST):
    def __init__(self, li=None):
        BST.__init__(self, li)
 
    def rotate_left(self, p, c):
        s2 = c.lchild
        p.rchild = s2
        if s2:
            s2.parent = p
        c.lchild = p
        p.parent = c
 
        p.bf = 0
        c.bf = 0
AVL插入——右旋

  不平衡是由于对K的左孩子的左子树插入导致的:右旋

  右旋插入的过程如下图:

  代码如下:

#_*_coding:utf-8_*_
from bst import BiTreeNode, BST
class AVLNode(BiTreeNode):
    def __init__(self, data):
        BiTreeNode.__init__(self, data)
        self.bf = 0
 
class AVLTree(BST):
    def __init__(self, li=None):
        BST.__init__(self, li)
 
    def rotate_right(self, p, c):
        s2 = c.rchild
        p.lchild = s2
        if s2:
            s2.parent = p
        c.rchild = p
        p.parent = c
 
        p.bf = 0
        c.bf = 0
AVL插入——右旋-左旋

  不平衡是由于对K的右孩子的左子树插入导致的:右旋-左旋

  右旋左旋的代码流程如图所示:

  代码如下:

#_*_coding:utf-8_*_
from bst import BiTreeNode, BST
class AVLNode(BiTreeNode):
    def __init__(self, data):
        BiTreeNode.__init__(self, data)
        self.bf = 0
 
class AVLTree(BST):
    def __init__(self, li=None):
        BST.__init__(self, li)
 
 
    def rotate_right_left(self, p, c):
        g = c.lchild
 
        s3 = g.rchild
        c.lchild = s3
        if s3:
            s3.parent = c
        g.rchild = c
        c.parent = g
 
        s2 = g.lchild
        p.rchild = s2
        if s2:
            s2.parent = p
        g.lchild = p
        p.parent = g
 
        # 更新bf
        if g.bf > 0:
            p.bf = -1
            c.bf = 0
        elif g.bf < 0:
            p.bf = 0
            c.bf = 1
        else :  # 插入的是g
            p.bf = 0
            c.bf = 0
AVL插入——左旋-右旋

  还有一种不平衡是由于对K的左孩子的右子树插入导致的:左旋-右旋

  代码的流程如下:

  代码如下:

#_*_coding:utf-8_*_
from bst import BiTreeNode, BST
class AVLNode(BiTreeNode):
    def __init__(self, data):
        BiTreeNode.__init__(self, data)
        self.bf = 0
 
class AVLTree(BST):
    def __init__(self, li=None):
        BST.__init__(self, li)
 
    def rotate_left_right(self, p, c):
        g = c.rchild
 
        s2 = g.lchild
        c.rchild = s2
        if s2:
            s2.parent = c
        g.lchild = c
        c.parent = g
 
        s3 = g.rchild
        p.lchild = s3
        if s3:
            s3.parent = p
        g.rchild = p
        p.parent = g
 
        # 更新bf
        if g.bf < 0:
            p.bf = 1
            c.bf = 0
        elif g.bf > 0:
            p.bf = 0
            c.bf = -1
        else:
            p.bf = 0
            c.bf = 0
AVL树的删除操作

  删除操作比较复杂。

  1,当前节点为要删除的节点且是树叶(无子树),直接删除,当前节点(为None)的平衡不受影响。

  2.当前节点为要删除的节点且只有一个左儿子或右儿子,用左儿子或右儿子代替当前节点,当前节点的平衡不受影响。

  3.当前节点为要删除的节点且有左子树右子树:如果右子树高度较高,则从右子树选取最小节点,将其值赋予当前节点,然后删除右子树的最小节点。如果左子树高度较高,则从左子树选取最大节点,将其值赋予当前节点,然后删除左子树的最大节点。这样操作当前节点的平衡不会被破坏。

  4.当前节点不是要删除的节点,则对其左子树或者右子树进行递归操作。当前节点的平衡条件可能会被破坏,需要进行平衡操作。

  如上图,25为当前节点,左子树删除17后平衡条件被破坏,需要根据当前节点(25)的右子树(30)的左子树(28)高度是否高于右子树(35)的高度进行判断,若高于,进行双旋转,否则进行单旋转。

二叉搜索树的扩展应用——B树

  B树(B-Tree):B 树是一颗自平衡的多路搜索树,常用语数据库的索引。

6,二叉树的图形化显示

6.1  在线生成 bst 树和 avl 树

  学习过程中难免遇到理解的问题:图形化能很好的帮助我们理解问题,下面是两个在线生成二叉树的网址,根据自己需要 看看,添加

6.2  程序自己生成二叉树

  利用PyGraphviz模块画出二叉树

  参考网址:http://pygraphviz.github.io/documentation/pygraphviz-1.5/  这里有详细的使用说明

安  装该模块失败,参考这篇博客 https://blog.csdn.net/chirebingxue/article/details/50393755

  使用了该模块以完成最后生成的二叉树显示,代码如下

import pygraphviz as pgv
    def draw(self, filename='./tree.png'):
        g = pgv.AGraph(strict=False, directed=True)
        g.node_attr['shape'] = 'circle'
 
        def traver(node):
            if node:
                if not node.parent:
                    g.add_node(node.key)
                else:
                    g.add_edge(node.parent.key, node.key)
                traver(node.left)
                traver(node.right)
        traver(self.root)
        g.layout('dot')
        g.draw(filename)

  简单的测试改模块的效果

tree = AVLTree()
tree.insert(range(0, 20, 2))  # 自己简单实现了个可以接受一个可迭代对象的数值的插入
tree.draw()
tree.delete_key(14)
tree.draw('tree2.png')

  最后生成下面的PNG图

参考文献:树:https://www.cnblogs.com/hwnzy/p/11118942.html

二叉搜索树:https://www.cnblogs.com/lliuye/p/9118591.html

AVL树:https://www.cnblogs.com/yscl/p/10077607.html

相关文章
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
4天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
13 5
|
5天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
25 4
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
4天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
1天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
3天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
16 7
|
18小时前
|
传感器 算法 数据安全/隐私保护
基于鲸鱼优化的DSN弱栅栏覆盖算法matlab仿真
```markdown 探索MATLAB2022a中WOA与DSN弱栅栏覆盖的创新融合,模拟鲸鱼捕食策略解决传感器部署问题。算法结合“搜索”、“包围”、“泡沫网”策略,优化节点位置以最大化复杂环境下的区域覆盖。目标函数涉及能量效率、网络寿命、激活节点数、通信质量及覆盖率。覆盖评估基于覆盖半径比例,旨在最小化未覆盖区域。 ```
|
5天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现