树总结（二）平衡二叉树
一、平衡二叉树
平衡二叉树，是一种二叉排序树，其中每一个结点的左子树和右子树的高度差最多等于 1
1. 概念
-
平衡因子（Balance Factor）
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子。
平衡二叉树上所有结点的平衡因子只可能是 -1、0、1。
平衡二叉树
2. 最小不平衡子树
距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，称为最小不平衡子树。
最小不平衡子树
如上图所示：新插入结点 37 时，距离他最近的平衡因子绝对值超过 1 的结点是 58（58 结点左子树高度是 3 右子树高度是 1），所以从 58 开始以下的子树为最小平衡子树
3. 平衡二叉树实现原理
举例：
用 [3,2,1,4,5,6,7,10,9,8] 这个数组组成一个平衡二叉树。
下图图1 中。已经插入 3 个数，此时发现根结点的平衡因子变为了 2。已经是最小不平衡子树了。所以需要右转（左子树 - 右子树 = 正数；顺势转旋转）。如下图图2。
然后插入 4 数字。如下图图3。此时的平衡因子是 -1 符合平衡二叉树。
继续插入 5 数字。如下图图4。此时平衡被打破。结点 3 是最小不平衡子树。所以需要向左转（左子树 - 右子树 = 负数：逆时针旋转）。如下图图5。
最简单的最小不平衡子树旋转
继续插入数字 6 这时候发现根结点的平衡因子变为了 -2 （左子树 1 - 右子树 3）。需要逆时针旋转（左子树 - 右子树 = 负数：逆时针旋转）。如下图图6
旋转后发现 2 结点要放到 4 结点左子树，然而 4 结点本身存在左子树。因为这个时候 4 结点的左子树肯定比 2 结点大。所以放在 2 结点的右边。如下图图 7
继续插入数字 7 在6 结点的右子树上。5 结点的平衡因子就变为了 -2 逆时针旋转（左子树 - 右子树 = 负数：逆时针旋转）。结果如下图图8
旋转后子树冲突
继续插入数字 10 。平衡没有被打破。
继续插入数字 9 。发现平衡被打破，最小平衡子树的节点是 7 结点，最小平衡因子是 -2。应该逆时针选择（左子树 - 右子树 = 负数：逆时针旋转）。但是逆时针旋转完会发现，它不符合排序树，右子树比上级结点小。如下图图9
错误旋转
如何旋转呢？
看 7 结点的平衡因子是 -2 ，而 10 结点的平衡因子是 1 。
前面的所有旋转平衡因子要不都是正数，要不都是负数，所以先要统一两个结点平衡因子的正负号。
先旋转 10 结点子树。因为平衡因子是 1 所以顺时针转，然后在旋转最小平衡子树。如下图图10 。
统一符号旋转
继续插入数字 8。如下图图11
会发现 6 结点的平衡因子是 -2，而 9 结点的平衡因子是 1。
先旋转 9 结点的子树。9 结点的平衡因子是 1 所以顺时针（左子树 - 右子树 = 正数；顺势转旋转）。如下图图11
旋转后因为 7 结点有右子树，9 结点也有右子树，所以 7 结点右子树，加入 9 结点左子树。
然后在 6 结点和 7结点符号相同，如下图图12。6 结点平衡因子是 -2 所以逆时针旋转（左子树 - 右子树 = 负数：逆时针旋转）最终如下图图13
统一符号旋转
4. 平衡二叉树 Python 算法
-
结点类
这里只是多加了一个 bf 平衡因子参数
class TreeNode(object):
def __init__(self, val, lchild=None, rchild=None):
self.val = val
self.lchild = lchild
self.rchild = rchild
# 平衡因子，平衡二叉树用。默认 0 平衡
self.bf = 0
def __repr__(self):
if self.val is None:
return "None"
return "{val: %s, l: %s, r: %s, bf: %s}" % (self.val, self.lchild, self.rchild, self.bf)
-
最简单的左旋和右旋（图 1 到 图 5）
这里只是旋转，不一定平衡
class AVLTree():
def __init__(self):
self.lh = 1 # 左高
self.eh = 0 # 平等
self.rh = -1 # 右高
# 最小不平衡子树 右旋转 -- 顺时针 --- 平衡因子正数
def right(self, tree):
temp_node = copy.deepcopy(tree)
# 取出树 tree 的左子树r
l = temp_node.lchild
# 将树 temp_node 左子树改为 l 的右子树
temp_node.lchild = l.rchild
# 在将 l 的右子树 赋值为 temp_node
l.rchild = temp_node
tree.val = l.val
tree.lchild = l.lchild
tree.rchild = l.rchild
tree.bf = l.bf
# 最小不平衡子树 左旋转 -- 逆时针 --- 平衡因子负数
def left(self, tree):
temp_node = copy.deepcopy(tree)
r = temp_node.rchild
temp_node.rchild = r.lchild
r.lchild = temp_node
tree.val = r.val
tree.lchild = r.lchild
tree.rchild = r.rchild
tree.bf = r.bf
这里有解释一下 deepcopy 深拷贝。
因为在后面的插入时候使用递归的方法，不想 return。
这里想直接修改传进来的 tree 这个树对象。
如果这里使用 tree = r 实际上是修改的旋转函数的内部变量 tree， 而不是 tree 对象。
这里修改 tree 对象里面的内容，这样 python 认为你在修改 tree 对象。而不是函数它自己的参数。
下图是右旋的一个图示。图中标记变量的变化过程，和平衡因子的变化
右旋转
-
平衡旋转
左平衡旋转和右平衡旋转
def left_balance(self, tree):
# l 指向树的左子树根结点
l = tree.lchild
if l.bf == self.lh:
# 新结点插入在树的左结点的左子树上，要右旋处理
tree.bf = l.bf = self.eh
self.right(tree)
if l.bf == self.rh:
# 新结点插入在树的左结点的右子树上，要两次旋转处理
# lr 指向树的右结点的右结点
lr = l.rchild
if lr.bf == self.lh:
tree.bf = self.rh
l.bf = self.eh
if lr.bf == self.eh:
tree.bf = l.bf = self.eh
if lr.bf == self.rh:
tree.bf = self.eh
l.bf = self.lh
lr.bf = self.eh
self.left(tree.lchild)
self.right(tree)
def right_balance(self, tree):
r = tree.rchild
if r.bf == self.rh:
tree.bf = r.bf = self.eh
self.left(tree)
if r.bf == self.eh:
tree.bf = r.bf = self.eh
if r.bf == self.lh:
rl = r.lchild
if rl.bf == self.lh:
tree.bf = self.eh
r.bf = self.rh
if rl.bf == self.eh:
tree.bf = r.bf = self.eh
if rl.bf == self.rh:
tree.bf = self.lh
r.bf = self.eh
rl.bf = self.eh
self.right(tree.rchild)
self.left(tree)
下图是左平衡旋转变量和平衡因子的变化
下图是右平衡旋转变量和平衡因子的变化
-
插入结点
这里需要说的是在插入的递归过程中。会判断最小不平衡子树。然后根据最小不平衡子树的根结点进行旋转。
def insert(self, tree, val, taller=True):
# taller 标记树是否有增高
if tree.val is None:
# 这里的 tree.lchild = TreeNode(None) 为什么是 TreeNode（None）
# 因为在下次插入数据时如果 tree 是 None。直接修改 tree = TreeNode(val)
# 这个时候的 tree 是函数内部变量。
# 在这里是需要 tree 参数是传址。修改tree 就是在修改整个 tree 对象
tree.val = val
tree.lchild = TreeNode(None)
tree.rchild = TreeNode(None)
tree.bf = self.eh
taller = True
else:
if val == tree.val:
taller = False
return False, taller
if val < tree.val:
res, taller = self.insert(tree.lchild, val, taller)
if res is False:
return False, taller
if taller:
if tree.bf == self.lh:
self.left_balance(tree)
taller = False
elif tree.bf == self.eh:
tree.bf = self.lh
taller = True
elif tree.bf == self.rh:
tree.bf = self.eh
taller = False
else:
res, taller = self.insert(tree.rchild, val, taller)
if res is False:
return False, taller
if taller:
if tree.bf == self.lh:
tree.bf = self.eh
taller = False
elif tree.bf == self.eh:
tree.bf = self.rh
taller = True
elif tree.bf == self.rh:
self.right_balance(tree)
taller = False
return True, taller
-
完整代码
#! coding=utf8
import pysnooper
import copy
# import pdb; pdb.set_trace()
class TreeNode(object):
def __init__(self, val, lchild=None, rchild=None):
self.val = val
self.lchild = lchild
self.rchild = rchild
# 平衡因子，平衡二叉树用。默认 0
self.bf = 0
def __repr__(self):
if self.val is None:
return "None"
return "{val: %s, l: %s, r: %s, bf: %s}" % (self.val, self.lchild, self.rchild, self.bf)
class AVLTree():
def __init__(self):
self.lh = 1 # 左高
self.eh = 0 # 平等
self.rh = -1 # 右高
# 最小不平衡子树 右旋转 -- 顺时针 --- 平衡因子正数
def right(self, tree):
temp_node = copy.deepcopy(tree)
# 取出树 tree 的左子树r
l = temp_node.lchild
# 将树 temp_node 左子树改为 l 的右子树
temp_node.lchild = l.rchild
# 在将 l 的右子树 赋值为 temp_node
l.rchild = temp_node
tree.val = l.val
tree.lchild = l.lchild
tree.rchild = l.rchild
tree.bf = l.bf
# 最小不平衡子树 左旋转 -- 逆时针 --- 平衡因子负数
def left(self, tree):
temp_node = copy.deepcopy(tree)
r = temp_node.rchild
temp_node.rchild = r.lchild
r.lchild = temp_node
tree.val = r.val
tree.lchild = r.lchild
tree.rchild = r.rchild
tree.bf = r.bf
def left_balance(self, tree):
# l 指向树的左子树根结点
l = tree.lchild
if l.bf == self.lh:
# 新结点插入在树的左结点的左子树上，要右旋处理
tree.bf = l.bf = self.eh
self.right(tree)
if l.bf == self.rh:
# 新结点插入在树的左结点的右子树上，要两次旋转处理
# lr 指向树的右结点的右结点
lr = l.rchild
if lr.bf == self.lh:
tree.bf = self.rh
l.bf = self.eh
if lr.bf == self.eh:
tree.bf = l.bf = self.eh
if lr.bf == self.rh:
tree.bf = self.eh
l.bf = self.lh
lr.bf = self.eh
self.left(tree.lchild)
self.right(tree)
def right_balance(self, tree):
r = tree.rchild
if r.bf == self.rh:
tree.bf = r.bf = self.eh
self.left(tree)
if r.bf == self.eh:
tree.bf = r.bf = self.eh
if r.bf == self.lh:
rl = r.lchild
if rl.bf == self.lh:
tree.bf = self.eh
r.bf = self.rh
if rl.bf == self.eh:
tree.bf = r.bf = self.eh
if rl.bf == self.rh:
tree.bf = self.lh
r.bf = self.eh
rl.bf = self.eh
self.right(tree.rchild)
self.left(tree)
# @pysnooper.snoop()
def insert(self, tree, val, taller=True):
# taller 标记树是否有增高
if tree.val is None:
# 这里的 tree.lchild = TreeNode(None) 为什么是 TreeNode（None）
# 因为在下次插入数据时如果 tree 是 None。直接修改 tree = TreeNode(val)
# 这个时候的 tree 是函数内部变量。
# 在这里是需要 tree 参数是传址。修改tree 就是在修改整个 tree 对象
tree.val = val
tree.lchild = TreeNode(None)
tree.rchild = TreeNode(None)
tree.bf = self.eh
taller = True
else:
if val == tree.val:
taller = False
return False, taller
if val < tree.val:
res, taller = self.insert(tree.lchild, val, taller)
if res is False:
return False, taller
if taller:
if tree.bf == self.lh:
self.left_balance(tree)
taller = False
elif tree.bf == self.eh:
tree.bf = self.lh
taller = True
elif tree.bf == self.rh:
tree.bf = self.eh
taller = False
else:
res, taller = self.insert(tree.rchild, val, taller)
if res is False:
return False, taller
if taller:
if tree.bf == self.lh:
tree.bf = self.eh
taller = False
elif tree.bf == self.eh:
tree.bf = self.rh
taller = True
elif tree.bf == self.rh:
self.right_balance(tree)
taller = False
return True, taller
t = AVLTree()
tree = TreeNode(3)
tree.lchild = TreeNode(None)
tree.rchild = TreeNode(None)
i = [2, 1, 4, 5, 6, 7, 10, 9, 8]
for a in i:
t.insert(tree, a)
print tree
