C/C++ 中的 AA 树?
cc++server side programmingprogramming
计算机科学中的 AA 树被定义为一种平衡树，用于高效存储和检索有序数据。AA 树被视为红黑树的变体，红黑树是一种二叉搜索树，支持高效添加和删除条目。与红黑树相反，AA 树上的红色节点只能作为右子节点添加，不能作为左子节点添加。此操作的结果是模拟 2-3 树而不是 2-3-4 树，从而简化了维护操作。红黑树的维护算法需要假设或考虑七种不同的形状才能正确平衡树 −
与红黑树相反，AA 树只需要假设或考虑两种形状，因为严格要求只有右链接可以是红色 −
平衡旋转
红黑树每个节点需要一位平衡元数据(颜色)，而 AA 树每个节点需要 O(log(log(N))) 位元数据，以整数"级别"的形式。以下不变量适用于 AA 树 −
每个叶节点的级别都被视为 1。
每个左子节点的级别都恰好比其父节点的级别小 1。
每个右子节点的级别等于或小于其父节点的级别。
每个右孙节点的级别都严格小于其祖父母节点的级别。
每个级别高于 1 的节点都有两个子节点。
重新平衡 AA 树在程序上比重新平衡红黑树更容易或更简单。
对于 AA 树，仅需两个不同的操作即可恢复平衡:"倾斜"和"分裂"。倾斜被视为右旋转，用右水平链接组成的子树替换由左水平链接组成的子树。在拆分的情况下，它是左旋转和级别增加，用包含两个或多个连续右水平链接的子树替换由两个更少的连续右水平链接组成的子树。操作"倾斜"和"拆分"解释如下 −
函数倾斜是
输入:需要重新平衡的 AA 树由节点 t 表示。 输出:重新平衡的 AA 树由另一个节点表示。 if nil(t) then return nil else if nil(left(t)) then return t else if level(left(t)) == level(t) then 交换水平左链接的指针。 l = left(t) left(t) := right(l) right(l) := t return l else return t end if end function
function split is
输入:需要重新平衡的 AA 树由节点 t 表示。 输出:重新平衡的 AA 树由另一个节点表示。 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 我们有两个水平右链接。取中间节点，提升它，然后返回它。 r = right(t) right(t) := left(r) left(r) := t level(r) := level(r) + 1 return r else return t end if end function
