红黑树的简单理解

红黑树是STL中map，set底层的数据结构。是一棵二叉平衡树，这使得数据的插入，删除和查找效率都是O（lgn）。

很多资料：

介绍红黑树的定义，和证明在此：定义

红黑树的插入删除，旋转操作的详细解释在此：插入删除，旋转

定义

  1、每个结点或是红色的，或是黑色的

  2、根节点是黑色的

  3、每个叶结点（NIL）是黑色的

  4、如果一个节点是红色的，则它的两个儿子都是黑色的。

  5、对于每个结点，从该结点到其子孙结点（`叶子`节点NIL！！！）的所有路径上包含相同数目的黑色结点。

简单的理解

红黑树的定义决定了红黑树的最深深度不会大于最浅深度的两倍，在插入或删除时，破坏了红黑树的性质，程序自动对相应部分进行左旋或右旋，来恢复红黑树的性质。
而具体在插入和删除的时候是怎么旋转的，这分成很多情况，具体情况看上面的链接，理解到这就行了。 总之，旋转就只是为了恢复红黑树的性质。成为红黑树时，就能使得这个平衡的树在插入，删除和查找效率都是O(lgn)。

粗略证明

下面就来大致的证明为什么红黑树是平衡的，他的最深深度（max_depth）不会大于最浅（min_depth）深度的两倍。 (max_depth <= 2 * min_depth)

根据性质5，一棵完全的二叉树，全部标成黑色，这当然是一个红黑树，此时，是max_depth = min_depth。

现在我们在确保红黑树的定义的情况下插入红色的结点，使得max_depth和min_depth的差异越来越大。 根据性质4，插入的红色最多的情况当然是使得深度由小到大，黑色红色交替的情况。

性质5确保了从根节点到每个叶子节点的路径上，黑色节点的数量是相同的。而在黑色节点之间插入红色节点，最多也只能插入和路径上黑色节点相同的数量。 所以最大max_depth可以达到min_depth的两倍。

这样就证完了。