在计算机科学中，aa树被定义为一种用于高效存储和检索有序数据的平衡树实现。aa树被视为红黑树的一种变体，红黑树是一种支持高效添加和删除条目的二叉搜索树。与红黑树不同，aa树上的红色节点只能作为右子节点添加，不能作为左子节点添加。这个操作的结果是模拟2-3树而不是2-3-4树，从而简化了维护操作。红黑树的维护算法需要假设或考虑七种不同的形状来正确平衡树。
与红黑树相反，AA树只需要假设或考虑两种形状，因为只有右链接可以是红色。
立即学习“C++免费学习笔记（深入）”；
平衡旋转
红黑树每个节点需要一个平衡元数据位（颜色），而AA树每个节点需要O(log(log(N)))个元数据位，以整数“level”的形式。以下不变式适用于AA树：
每个叶节点的级别被视为1。
每个左子节点的级别比其父节点小1。
每个右子节点的级别等于或比其父节点小1。
每个右孙子节点的级别严格小于其祖父节点。
级别大于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) thenreturn nilelse if nil(left(t)) thenreturn telse if level(left(t)) == level(t) then Exchange the pointers of horizontal left links. l = left(t)left(t) := right(l)right(l) := treturn lelsereturn tend ifend 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) thenreturn nilelse if nil(right(t)) or nil(right(right(t))) thenreturn telse if level(t) == level(right(right(t))) thenWe have two horizontal right links. The middle node is taken, elevate it, and return it. r = right(t)right(t) := left(r)left(r) := tlevel(r) := level(r) + 1return relsereturn tend ifend function
登录后复制
分割 –
以上就是AA树在C/C++中是什么？的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583743.html
