AA树的平衡与再平衡
介绍
AA 树在计算机科学一种形式的自平衡二叉查找树用于高效存储和检索序数据。 AA 树的名称是由它的发明者 Arne Andersson 而来。 AA 树是红黑树的一种变种，是 Arne Andersson 教授在1993年年在他的论文*“Balanced search trees made simple”*中介绍，设计的目的是减少红黑树考虑的不同情况，区别于红黑树的是， AA 树的红节点只能作为右叶子。换句话说，没有红节点可以是一个左子儿。这导致代替2-3-4树，从而大大简化了维护2-3树的模拟。维护红黑树的平衡需要考虑7种不同的情况:
因为 AA 树有严格的条件(红节点只能为右节点)，故只需考虑2种情形:
AA 树是2-3树的模拟，2-3树和 AA 树是等距同构的。其节点类型如下
平衡条件
树是用与高效的存储和检索数据的，为了维持其效率，必须维持其平衡结构。 平衡一颗红黑树需记录其颜色，而 AA 树是在每个节点记录其 level 这相当于红黑树节点的黑高度
- 所有叶节点的 level 都是1
- 每个左孩子的 level 恰好为其父亲的 level 减一
- 每个右孩子的 level 等于其父亲的 level 或为其父亲的 level 减一
- 每个右孙子的 level 严格小于其祖父节点的 level
- 每一个 level 大于1的节点有两个子节点
Skew & Split
对于 AA 树，维持其平衡的基本操作如下：
偏斜 Skew：使得子树中向左的水平边变成向右的。
不满足平衡条件：2
def skew(node): if node is None or node.left is None: return node if node.left.level != node.level: return node lft = node.left node.left = lft.right # B => C change to D => C lft.right = node # D => B change to B => D return lft # top => D change to top => B- 判断是否是偏斜 i. 是否为空节点，是则不执行 ii. 是否存在左节点，不存在则不执行 iii. 是否不满足平衡条件 2，满足则不执行
- 右旋转操作
- 返回新的节点
分割 Split：对溢出子节点进行分割，将三个值中的中间值向上移到父节点，如果让父节点溢出了，就继续分割下去。
不满足平衡条件：4
def split(node): if node is None or node.right is None or node.right.right is None: return node if node.right.right.level != node.level: return node rgt = node.right node.right = rgt.left # C => E change to C => D rgt.left = node # E => D change to E => C rgt.level += 1 # let E's level == A's level return rgt # A => C change to A => E- 判断是否要执行分割 i. 是否为空节点，是则不执行 ii. 是否存在右子节点，右孙节点，不存在则不执行 iii. 是否满足平衡条件 4，满足则不执行
- 分割（左旋转）操作
- 返回新的节点
尽管各种树结构及其再平衡方法都不尽相同，但他们通常是由以上两类基本操作发展来的。
Insert & Remove
作为一种数据结构，必须拥有 Insert 与 Remove 等基本操作吧。那么，如何在操作中保持树的平衡？
Insert 插入操作
在一棵已平衡的 AA 树插入一个新的节点，如果他是个左子节点，那么可采用偏斜 Skew 操作；如果他是个右子节点，那啥事情都不用干；但它是右孙节点的话，就成为了一个溢出的节点（四节点型结构），那样就要执行分割 Split 操作。
算法步骤
def insert(node, key, val):
if node is None:
return Node(key, val)
if node.key == key:
node.val = val
elif key < node.key:
node.left = insert(node.left, key, val)
else:
node.right = insert(node.right, key, val)
node = skew(node)
node = split(node)
return node- 判断节点是否是空，空则返回新建一个节点
- 判断节点的键与待插入的键
- 相等则更新值
- 大于则执行左子树的插入操作
- 小于则执行右子树的插入操作
- 执行翻转 Skew 操作
- 执行分割 Split 操作
示例
current tree:
/-?
-A(Lv.1)
| /-?
\C(Lv.1)
\-?
insert B
before skew:
/-?
/B(Lv.1)
| \-?
-C(Lv.1)
|
\-?
after skew:
/-?
-B(Lv.1)
| /-?
\C(Lv.1)
\-?
before split:
/-?
-A(Lv.1)
| /-?
\B(Lv.1)
| /-?
\C(Lv.1)
\-?
after split:
/-?
/A(Lv.1)
| \-?
-B(Lv.2)
|
| /-?
\C(Lv.1)
\-?Remove 删除操作
在一棵平衡的树删除一个叶节点的过程十分简单，可删除处于结构内部的节点的过程就没那么简单了。所以接下来没讲清楚请见谅。结合代码和示例能更好的明白这个过程。
为了在这个过程中平衡树结构，删除一个内部节点可以转换成交换内部节点与其后继节点,删除后第一件事就要降低其 level （如果可以的话），然后再对整个level执行 Skew 和 Split 操作。这个方法是最受欢迎的，因为这个方法容易理解。
算法步骤
def decrease_level(node):
should_be = min(node.left.level if node.left else 0,
node.right.level if node.right else 0) + 1
if should_be < node.level:
node.level = should_be
if node.right and should_be < node.right.level:
node.right.level = should_be
return node
def remove(node, key):
if node is None:
return node
if key > node.key:
node.right = remove(node.right, key)
elif key < node.key:
node.left = remove(node.left, key)
else:
if node.left is None and node.right is None:
return None
elif node.left is None:
heir = node.right
node.right = remove(heir, heir.key)
node.key = heir.key
node.val = heir.val
else:
heir = node.left
node.left = remove(heir, heir.key)
node.key = heir.key
node.val = heir.val
node = decrease_level(node)
node = skew(node)
node.right = skew(node.right)
if node.right is not None:
node.right.right = skew(node.right.right)
node = split(node)
node.right = split(node.right)
return node- 删除节点 i. 判断节点是否为空节点，是则返回自身 ii. 判断目标键与当前节点的键，执行对应操作 大于，对右子树执行删除操作； 小于，对左子树执行删除操作； 等于，判断是否为叶节点，是则返回空节点，完成删除操作，否则与后继节点交换
- 降低节点的 level
- 对同 level 的后继与其本身执行 Skew 操作，再执行 Split 操作
示例
current tree:
/-?
/A(Lv.1)
| \-?
|
-B(Lv.2)
| /-?
| /C(Lv.1)
| | \-?
\D(Lv.2)
|
| /-?
\E(Lv.1)
| /-?
\F(Lv.1)
\-?
remove B
before skew:
/-?
/C(Lv.1)
| \-?
-D(Lv.1)
|
| /-?
\E(Lv.1)
| /-?
\F(Lv.1)
\-?
after skew:
/-?
-C(Lv.1)
| /-?
\D(Lv.1)
| /-?
\E(Lv.1)
| /-?
\F(Lv.1)
\-?
before split:
/-?
-A(Lv.1)
| /-?
\C(Lv.1)
| /-?
\D(Lv.1)
| /-?
\E(Lv.1)
| /-?
\F(Lv.1)
\-?
after split:
/-?
/A(Lv.1)
| \-?
-C(Lv.2)
|
| /-?
\D(Lv.1)
| /-?
\E(Lv.1)
| /-?
\F(Lv.1)
\-?
before split:
/-?
-D(Lv.1)
| /-?
\E(Lv.1)
| /-?
\F(Lv.1)
\-?
after split:
/-?
/D(Lv.1)
| \-?
-E(Lv.2)
|
| /-?
\F(Lv.1)
\-?
current tree:
/-?
/A(Lv.1)
| \-?
|
-C(Lv.2)
| /-?
| /D(Lv.1)
| | \-?
\E(Lv.2)
|
| /-?
\F(Lv.1)
\-?由于 Skew 和 Split 操作都是在递归性回溯部分中执行的。这样一来，错误的节点型结构就会在其回溯路径上被修复。
结论
由于 AA 树与其他二分搜索树来说同数量节点形成的树结构较浅，故搜索速度较快。但其插入删除节点效率较低，因为需要执行多次 Skew 和 Split 操作。
剩余代码
class Node:
__slots__ = ('left', 'right', 'level', 'key', 'val')
def __init__(self, key, val):
self.left = None
self.right = None
self.level = 1
self.key = key
self.val = val
def __repr__(self):
return 'Node(key={k!r}, val={v!r}, lvl={l!r})'.format(
k=self.key, v=self.val, l=self.level
)参考
- Magnus Lie Hetland.(2014).Tree Balance … and Balancing.In Python Algorithms: Mastering Basic Algorithms in the Python Language,Second Edition,pages 143-149.
- Magnus Lie Hetland.(2015).树的平衡与再平衡.In Python算法教程,pages 145-152.
- Andersson, A.(1993).Balanced search trees made simple.In Proceedings of the Workshop on Algorithms and Data Structures(WADS),pages 60-71.
