C/C++ 中的 AA 树？

在计算机科学中，AA 树被定义为一种平衡树，用于高效地存储和检索有序数据。AA 树被认为是红黑树的一种变体，红黑树是一种支持高效添加和删除条目的二叉搜索树。与红黑树不同的是，AA 树上的红色节点只能作为右子节点添加，不能作为左子节点添加。此操作的结果是模拟 2-3 树而不是 2-3-4 树，这简化了维护操作。红黑树的维护算法需要假设或考虑七种不同的形状才能正确地平衡树。


与红黑树相反，AA 树只需要假设或考虑两种形状，因为只有右链接可以是红色的。


平衡旋转

红黑树每个节点需要一位平衡元数据（颜色），而 AA 树每个节点需要 O(log(log(N))) 位元数据，以整数“级别”的形式表示。AA 树具有以下不变性：

  • 每个叶子节点的级别都被视为 1。

  • 每个左子节点的级别正好比其父节点的级别小 1。

  • 每个右子节点的级别等于或比其父节点的级别小 1。

  • 每个右孙子节点的级别严格小于其祖父节点的级别。

  • 每个级别高于 1 的节点都有两个子节点。

重新平衡 AA 树在程序上比重新平衡红黑树容易得多。

对于 AA 树，只需要两种不同的操作来恢复平衡：“倾斜”和“分裂”。“倾斜”被视为右旋转，以用由右水平链接组成的子树替换由左水平链接组成的子树。对于“分裂”，它是一个左旋转和级别增加，以用包含少两个连续右水平链接的子树替换包含两个或多个连续右水平链接的子树。“倾斜”和“分裂”操作解释如下：

skew 函数是

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(left(t)) then
return t
else if level(left(t)) == level(t) then
   Exchange the pointers of horizontal left links.
   l = left(t)
left(t) := right(l)
right(l) := t
return l
else
return t
end if
end function


split 函数是

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(right(t)) or nil(right(right(t))) then
return t
else if level(t) == level(right(right(t))) then
We have two horizontal right links. The middle node is taken, elevate it, and return it.
      r = right(t)
right(t) := left(r)
left(r) := t
level(r) := level(r) + 1
return r
else
return t
end if
end function

分裂 -

更新于：2020年1月29日

1K+ 浏览量

开启您的职业生涯

完成课程获得认证

开始学习
广告