红黑树设计思想之我见

具体算法可见红黑树 - 维基百科，自由的百科全书

最总完成代码见algorithm/RBTree.h at master · liu946/algorithm

前言

说实话，我一星期前就开始着手写这次的数据结构作业了，AVL倒是容易，这个以前是理解的，在写这个的时候我还参考了一些面向对象的数据结构设计模式，类似C++原始库那样写了一个更面向对象的平衡树类。相比之下，之前的很多使用类写的数据结构更像是刻意的套用形式或是只是为了做封装了。之后，大概在数据结构结课的时候我再专门写一个东西来讨论一下这方面的内容吧。可能会涉及，继承、拷贝构造、重载等等设计方法我的见解和一些编程时的trick。

AVL很快搞定后，开始写红黑树，红黑树的插入也很快就写好了，可是删除就遇到了麻烦，说实话，我开始就没看懂删除操作到底在干什么，只看着wiki上（其实算法导论上面写的也差不多）各种case和各种调整的方法，说实话情况非常多，由于数据结构定义的时候我没有去专门设计最下面一层的黑空节点，而是直接写的NULL，我照着书写下来并不能跑动。这也迫使我做了如下思考。

目的出发

红黑树在插入删除的时候到底在调整什么，如果我直接照抄算法可能我现在就还不知道，其实就是调整树的平衡，准确的说，弱平衡。但是，怎么能保证它弱平衡呢？怎么让操作控制在logN呢？保证红黑树性质即可。那怎么保证性质？如果想到这里我还是自己思考而没有着急去看攻略的话可能我很快也能想到办法了。

好了终于说到核心了，怎么调整，其实就分两种情况，删除了一个节点，一条腿短了，要么想办法从另一条腿上调整一下，让这条腿恢复原来的长度，要么把另一条腿也弄短，让上面的父节点再处理这两个一起短的问题。OK，就这么一句话，可能不是计算机专业的要觉得我说胡话了。但是就是这样，如果想到了这一步，再看wiki上的介绍就觉得很合理了，而且自己也能设计出来调整方法了。

问题划归

记得有个数学家的笑话，如果遇到房子没着火怎么办？把问题化为一个已解决的问题，可以说是一个科学通用的处理方法。最终分情况比较多，又得分左右，而且还涉及递归，最后就形成了十几个方法互相调用，形成最后的调整方法。问题大致分为10类情况，但是并不是分10类每类下面调用一个方法的总分结构，我看很多人都这么设计程序，我有时候欠考虑也爱这样写。但是这次在这10小类里面的某些情况就是转一下再调用其他情况的。并不一定非要解决问题，转化问题，转化情况也是很重要的技巧。

还有就是不要怕分情况，很多时候在代码写出来之前人的抽象能力是有限的，很难做到很多情况一起考虑，如果抓身后的猫很难做出坐标变换和抓取，那就转身，再代入抓身前猫的函数吧。

使用封装操作

我们知道，树的左旋右旋不会改变树节点的大小顺序，这就是一种封装操作。这里我想说的封装，不是只指的程序意义上的，而是一种有意义（可能当时并不能看出来）、高聚合、前后保持什么一致性的一连串操作。这里看来，旋转只要传入一个指针即可，耦合性很低，又很好地保持了性质，更可贵的是这是一个局部操作，很难说如果没有旋转还能不能设计出这些树结构。

再举一个更明显的例子，就是魔方公式，看似复杂的一系列操作之后，会得到人类可以理解的少量变化，并保持原有的不变。这样的东西，用途放在其次，都是有必要尝试总结的。

后记

当然还有很多很重要的内容我没有写出来，比如这种红黑模式的构造。不写并不是不重要，而是我不会，数学老师说构造是最难的。如果没有红黑原则，这些都无从谈起。所以还有很多更加深入的内容需要我们继续学习体会。