红黑树简析（可能会有部分转载）

一. 红黑树的特性

性质1:每个节点或者是黑色，或者是红色。
性质2:根节点是黑色。
性质3:每个叶子节点(NIL)是黑色。[注意:这里叶子节点，是指为空(NIL或NULL)的叶子节点!]
性质4:如果一个节点是红色的，则它的子节点必须是黑色的。
性质5:从一个节点到该节点下的所有叶子节点的路径上，均包含相同数目的黑节点。
对于特性(5)，确保没有一条路径会比其他路径长出两倍。因而，红黑树是相对接近平衡的二叉树。

二. 旋转

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。

为什么呢?道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

下面，我来举个栗子。。。

三. 总结

红黑树的内容与set、map和二叉查找树有关，不会的小伙伴们可以上网去搜一下。

由于本人能力有限，现只能给大家展示这么多，日后有空我还会增加的。。。

至此，感谢您的观看，我会继续加油的。ヾ(◍°∇°◍)ﾉﾞ