红黑树

    红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
    它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的”红黑树”。
    红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
    它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。



    本文相对我前面红黑树相关的3篇文章，主要有以下几点改进：
    1.图、文字叙述、代码编写，彼此对应，明朗而清晰。
    2.宏观总结，红黑树的性质与插入、删除情况的认识。
    3.代码来的更直接，结合图，给你最直观的感受，彻底明白红黑树。

    ok，首先，以下几点，你现在应该是要清楚明白了的：
    I、红黑树的五个性质：
    1）每个结点要么是红的，要么是黑的。
    2）根结点是黑的。
    3）每个叶结点，即空结点（NIL）是黑的。
    4）如果一个结点是红的，那么它的俩个儿子都是黑的。
    5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。