AA Tree

AA树真的很棒,虽然他没有普通红黑树那么厉害,但是AA树挺容易实现的,AA树是一棵右倾红黑树23树,注意! 这里是23树,不是234树。

AA树的由来

Arne Andersson教授在论文Balanced search trees made simple中提到,红黑树有7种特殊情况(图片源于wiki)

为了改进,他提出了使用23树并强行要求3节点(2key-3son-node)向右倾斜,于是,我们只剩下两种情况(图片源于wiki)

为了更加容易编码,他提出不再使用红黑来标识节点,而是选择高度,这里的高度指的是黑高度,即黑色节点的高度,学习过左偏树(左翼堆)或斜堆的读者应该对这里不太陌生,这里的高度其实和左偏树或斜堆中的右距离是同一个东西。

AA树的特性

所有叶节点的level都是1
每个左孩子的level恰好为其父亲的level减一
每个右孩子的level等于其父亲的level或为其父亲的level减一
每个右孙子的level严格小于其祖父节点的level
每一个level大于1的节点有两个子节点

AA树的skew

skew 是一个辅助函数,他的本质是zig,即如果发现一个节点的左儿子与自己黑高相同,则将左儿子选择至根。这将保证右倾。

AA树中的split

split同样是一个辅助函数,他的本质是zag,即如果发现一个节点的右孙子与自己黑高相同,则将右儿子选择至根,并将黑高+1,这将保证不会出现4节点(3key-4son-node)

AA树中的insert

递归向下,找到插入位置,然后插入,最后调整,调整的时候,树会变高,对每一层递归而言,左儿子变高我们就先让其skew,这可能导致出现4节点,我们再split,对于右儿子变高的情况,这时候可能右儿子本身是一个3节点,当他变高,导致根成为了4节点,我们调用skew即可,全部统一一下,就是先skew后split

AA树中的erase

很多时候删除都是一件困难的事情,但是我们可以通过寻找前驱后继,可以保证删除的节点一定是叶子,对于删除叶子,可能树高下降,同样的,先删除后对每一层进行调整。我们前面说过,AA树只有两种结构。我们来分析一下树高下降产生的影响。

情况1

右儿子与自己同黑高

情况1.1

右儿子下降

这种情况是合法的,不需要调整

情况1.2

左儿子下降

我们观察到这里是一种较为复杂的情况,可以这样处理,让节点a和c同时黑下降,得到了

然后我们考虑到c节点的左右儿子,注意到c和a以前黑同高,所以c的右儿子cr,一定比c矮,当c下降以后,cl、c、cr同高

根据定义,这里最多还能拖出两个同黑高的,cl的右儿子clr,cr的右儿子crr

这时候我们对c执行skew,然后clr成了c的左儿子,我们再次对c执行skew,最终a-cl-clr-c-cr-crr同黑高,

接下来的一步是让我最吃惊的,非常漂亮,我们先对a进行split,然后对根的右儿子再次split,就结束了。对a进行split后我们得到,注意到这里根的高度提高了

对根对右儿子split,就结束了

情况2

右儿子与自己不同黑高

情况2.1

右儿子下降

让a节点高度降低

让a进行skew,最后因为b的右儿子高度,分两种情况


对于b的右儿子太高的时候,对a进行skew

然后对b进行split即可

情况2.2

左儿子下降

让a下降

这里可能发生c的右儿子与c同高,split(a)即可

AA树erase总结

至此我们的删除已经讨论完了,实际细分只有4种情况,这要比普通红黑树简单多了,

AA树缺点

多次旋转导致性能不及红黑树,旋转次数较多

AA树代码

AA树代码