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树缺点
多次旋转导致性能不及红黑树，旋转次数较多