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树的性质
- AVL树本质上还是一颗二叉搜索树
- 根的左右子树的高度之差的绝对值（平衡因子）不能超过1
- 根的左右子树都是平衡二叉树（二叉排序树，二叉搜索树）
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
