AA树在C/C++中是什么？

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

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

立即学习“C++免费学习笔记（深入）”；

平衡旋转

红黑树每个节点需要一个平衡元数据位（颜色），而AA树每个节点需要O(log(log(N)))个元数据位，以整数“level”的形式。以下不变式适用于AA树：

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

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

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

  

  云从科技AI开放平台

  云从AI开放平台

  下载

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

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

重新平衡AA树比重新平衡红黑树要简单得多。

在AA树中，只需要两个不同的操作来恢复平衡：“skew”和“split”。Skew被视为右旋，用右水平链接替换一个由左水平链接组成的子树。在Split的情况下，是左旋和级别增加，用两个或更多连续的右水平链接替换一个包含两个较少连续的右水平链接的子树。下面解释了“skew”和“split”这两个操作。

函数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

function split is

函数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

分割 -