一、二叉搜索树的效率
- 平均情况下，二叉搜索树进行搜索的时间复杂度为O(lgn)。
- 最坏情况下，二叉搜索树可能非常偏斜。（如下图所示）
- 解决方法：
- 随机化插入
- AVL树
二、AVL树
- AVL树是一棵自平衡的二叉树
- AVL树具有以下性质：
- 根的左右子树的高度之差的绝对值不能超过1
- 根的左右子树都是平衡二叉树（满足上面的条件）
上图中的balance factor (平衡因子)指的是该节点左右子树的高度差。（右子树高度-左子树高度）
因为AVL树满足根的左右子树都是平衡二叉树，进行查找删除的操作时大致为一半一半的情况，因此一定不会出现极偏的情况。
三、AVL树的旋转
- 插入一个节点可能会造成破坏AVL树的平衡，可以通过旋转操作来进行修正。
- 插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K。K的两颗子树的高度差为2（2/-2，不可能超过3）。
- 不平衡的出现可能有4种情况。
1. 不平衡是由于对K的右孩子的右子树插入导致的：左旋
其中S1,S2,S3代表子树，h代表子树的高度
2. 不平衡是由于对K的左孩子的左子树插入导致的：右旋
3. 不平衡是由于对K的右孩子的左子树插入导致的：右旋 - 左旋
4. 不平衡是由于对K的左孩子的右子树插入导致的：左旋 - 右旋
示例代码如下所示：
在上节课我们写出的二叉树的节点和二叉树的类可以直接继承到AVL树中。
然后我们分别按照上面的图例写出AVL树的四种旋转
from bst import BirTreeNode,BST # 直接导入树节点和树结构
class AVLNode(BirTreeNode):
def __init__(self,data):
BirTreeNode.__init__(self, data)
self.bf = 0 # 默认平衡因子为0（新建的点为叶子节点）
class AVLtree(BST):
def __init__(self, Li = None):
BST.__init__(self, li)
def rotate_left(self, p, c): # 左旋(参考对应图示)；仅仅代表插入导致不平衡进行左旋
# 通过图发现s1和s3都没有动，只有s2发生改变
s2 = c.lchild
p.rchild = s2 # 将其旋转至p
if s2: # s2不为空
s2.parent = p
c.lchild = p
p.parent = c
p.bf = 0
c.bf = 0 # 旋转后更新每个点的平衡因子
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
def rotate_right_left(self, p, c): # 右旋后左旋；右孩子的左子树
# s1, s4 没有发生变化
g = c.lchid
# 左旋
s3 = g.rchild
c.lchid = s3
if s3:
s3.parent = c
g.rchild = c
c.parent = g
# 右旋
s2 = g.lchid
p.rchild = s2
if s2:
s2.parent = p
g.lchid = p
p.parent = g
# 更新bf ，共有3种情况
if g.bf > 0: # 此时key插在s3的位置(旋转前)
p.bf = -1 # (旋转后的p点)
c.bf = 0
elif g.bf < 0:
p.bf = 0
c.bf = 1
else: # s1,s2,s3,s4都为空，此时插入的为g
p.bf = 0
c.bf = 0
def rotate_left_right(self, p, c): #先左旋后右旋
g = c.rchild
# 左旋
s2 = g.lchid
c.rchild = s2
if s2:
s2.parent = c
g.lchid = 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
