前言
学习python数据结构与算法，学习常用的算法，
b站学习链接
74.AVL树的概念
首先看一下二叉搜索树的效率
平均情况下，二叉搜索树进行搜索的时间为O(logn)
最坏情况下，二叉树可能非常偏斜，这样搜索时间就会是O(n)
解决方法：
- 随机化插入
-
AVL树
随机化插入有个问题，就是可能不是同一时间插入，同一时间插入随机化的话，可以像快速排序法那样，但隔一会插一个，隔一会插一个，最终插入形成的树还是可能斜偏。
AVL树可以较好解决这个问题，AVL是三个科学家提出的，AVL是三个的首字母。
AVL树:是一颗自平衡的二叉搜索树。
具有以下性质：
- 根的左右子树的高度之差的绝对值不能超过1
-
根的左右子树都是平衡二叉树
一上面那个斜二叉树举例，50的左右子树没有，都是0，40的左子树没有，右子树是1，绝对值就是1，30的左子树没有，右子树是2，高度之差绝对值就是2，就不满足平衡。
下面这颗树是AVL树，上面的数字是左子树的高度-右子树的高度，都满足条件。
如果现在插入11，就是插到12的左子树，这样平衡就会打乱，需要树之间做一个平衡。这个平衡后面会讲。
75.AVL:旋转
插入一个节点可能会破坏AVL树的平衡，可以通过旋转来进行修正。
插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K。K的两颗子树的高度差2。
不平衡的出现可能有4种情况
1.不平衡是由于对K的右孩子的右子树插入导致的：左旋
将10左旋到20的下方。
实际情况10，20，30带着好多子树 ，如下S3本来的是h高度，插入Key之后，高度加1，导致不平衡，
把P左旋到C的下方，连接S1,S2。
2.不平衡是由于对K的左孩子的左子树插入导致的：右旋
把30右旋到下面
和左旋类似，把P右旋到C的下面
3.不平衡是由于对K的右孩子的左子树插入导致的：右旋-左旋
先把20右旋到下面，再把10左旋到下面
对P的右孩子C的左子树G插入，S2和S3本来的h-1,在S2或者S3插入一个后发生不平衡。先将C右旋到G的下方，再将P左旋到G的下方。
4.不平衡是由于对K的左孩子的右子树插入导致的：左旋-右旋
和上一个做一个镜像差不多。
四种方法挺好记的
左左 右
右右 左
左右 左右
右左 右左
76.AVL:旋转实现1
根据上面的图写出左旋和右旋。平衡因子balance factor 这里选右子树-左子树，
这里注意
插入时旋转没有问题，可是右右或者左左删除导致的不平衡，bf就不是0了，
比方说s1,s2,s3本来都是h+1的高度，删除s1中的一个key,左旋，最后p.bf=0-1=-1,c.bf=(h+2)-(h+1)=1。
77.AVL:旋转实现2
对照之前的图写出右旋-左旋
镜像写出，左旋-右旋
78.AVL:插入
主要一个点是：从父亲节点往上找
直到更新到一个节点的bf(平衡因子)是0后就不再更新
如果是+1或-1则继续下一个更新，-2或2则判断此时类型，进行响应的旋转。
总的代码如下，类继承了之前的二叉树，在此之上写的AVL树和节点
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
s2.parent = p
c.lchild = p
p.parent = c
p.bf = 0
c.bf = 0
return c
def rotate_right(self,p,c): #右旋
s2 = c.rchild
p.lchild = s2
if s2:#判断是否有s2
s2.parent = p
c.rchild = p
p.parent = c #把父节点连回来
p.bf = 0
c.bf = 0
return c
def rotate_right_left(self,p,c): #右旋-左旋
g = c.lchild
#右旋
s3 = g.rchild
c.lchild = s3
if s3:#判断是否有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: # 插到s3
p.bf = -1
c.bf = 0
elif g.bf <0: #插到s2
p.bf = 0
c.bf = 1
else: #插入的是g
p.bf = 0
c.bf = 0
return g
def rotate_left_right(self,p,c):#左旋-右旋
g = c.rchild
s2 = g.lchild
c.rchild = s2
if s2:
s2.parent = c
g.rchild = c
c.parent = g
s3 = g.lchild
p.rchild = s3
if s3:
s3.parent = p
g.rchild = p
p.parent = g
#更新bf
if g.bf <0: # 即插到s2
p.bf = 1
c.bf = 0
elif g.bf >0: #插到s3
p.bf = 0
c.bf = -1
else: #插入的是g
p.bf = 0
c.bf = 0
return g
def insert_no_rec(self,val):
#1.和BST一样，先插入
p = self.root
if not p:#如果是空树
self.root = AVLNode(val)
return
while True:
if val < p.data:
if p.lchild: #如果左子树存在，则根节点为这颗左树的根
p =p.lchild
else:#左孩子不存在,就插到这个位置上
p.lchild = AVLNode(val)
p.lchild.parent = p
node = p.lchild #node存储的是插入的节点
break
elif val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = AVLNode(val)
p.rchild.parent = p
node = p.rchild ##
break
else: # val ==p.data值就等于这个值，就相当于 插第二遍这个值，不允许插return
return
#2.更新balanc factor
while node.parent: #node.parent 不空，一直循环到根节点
if node.parent.lchild == node: #如果是左子树来的，左子树更沉了
#更新node.parent的bf -= 1 #选择左边-1 #右边+1 的平衡方法
if node.parent.bf <0: #原来的node.parent.bf == -1,现在要更新后变为-2
#做旋转
#看node哪边沉
g = node.parent.parent #为了连接旋转之后的子树
x = node.parent #旋转前子树的根
if node.bf >0: #如果是右边沉 #左孩子的右子树
n = self.rotate_left_right(node.parent,node) #具体更新函数里有
else: #如果左边沉 左左 - 右
n = self.rotate_right(node.parent,node)
#记得：把n和g连起来
elif node.parent.bf >0: #原来node.parent.bf = 1 ,现在要更新后变为0
node.parent.bf = 0
break
else: #原来node.parent.bf = 0 更新之后变为-1
node.parent.bf = -1
node = node.parent #往父一级更新
continue
else:# 传递是从右子树传来的，右子树更沉了
#更新node.parent的bf += 1
if node.parent.bf >0: #原来的node.parent.bf == 1,现在要更新后变为2
#做旋转
#看node哪边沉
g = node.parent.parent #为了连接旋转之后的子树
x = node.parent #旋转前子树的根
if node.bf <0: #如果是左边沉 #右孩子的左子树 -右左
n = self.rotate_right_left(node.parent,node) #具体更新函数里有
else: #如果右边边沉 右右 - 左
n = self.rotate_left(node.parent,node)
#记得连起来
elif node.parent.bf <0: #原来node.parent.bf = -1 ,现在要更新后变为0
node.parent.bf = 0
break
else: #原来node.parent.bf = 0.更新之后变为1
node.parent.bf = 1
node = node.parent #往父一级更新
continue
# 连接旋转后的子树
n.parent = g
if g: #g不是空 #旋转之后node.parent 已经不是原来的parent了所以用x保存一下
if x == g.lchild: #判断是根左子树连还是右子树连
g.lchild = n
else:
g.rchild = n
break #只可能是旋转后进入这里
else: #g是空 n本身是根节点
self.root = n
break
插入后如下，中序遍历依旧是升序
79.AVL树应用与数据结构总结
二叉搜索树拓展应用
B树（B-Tree）:B树是一颗自平衡的多路搜索树。常用于数据库的索引。
哈希表也可以用做数据库的索引。
还有一种在此之上的改进叫B+树（B+Tree）大同小异
这个是3叉的B树，中间存两个数据17，35。比17小的存左边，17-35存右边，比17大的存右边。分成了三个块，查找时更块。
总结
学习了AVL树，数据结构到此告一段落。