小探红黑树

本文对红黑树的特点和性质进行说明，不对红黑树的操作等问题进行代码方面的探究。

1、上帝视角看红黑树

红黑树的本质是一个相对平衡的二叉搜索树。 之所以称之为相对平衡，是因为平衡二叉树要求每个节点的左子树和右子树的高度差至多为1，而红黑树要求其高度差可以至多为1倍；所以说红黑树是一个广义的平衡二叉树，并且也是一个二叉搜索树。

2、红黑树的五条性质

1） 每个节点要么是红色的，要么是黑色的；
2）根结点时黑色的；
3）每个叶子节点必须是黑色的；
4）如果一个节点是红的，那它的两个儿子都是黑的；
5）对于任一节点而言，其到叶结点的每一条路径都包含了相同数目的黑节点；

有了以上性质的约束，一棵n个节点的红黑树高度始终保持为lgn，从而，红黑树的查找、插入、删除的时间复杂度最坏都是O(lgn)；

3、红黑树与AVL树的比较

红黑树的查找比AVL树慢，因为红黑树的深度可能更深；
红黑树的插入和删除相对于AVL树更快，因为其减少了插入和删除之后维护树严格平衡条件的自旋操作。

4、红黑树示例

红黑树示意图

【参考】
本文参考了教你透彻了解红黑树一文，如果想更深入的了解红黑树，也可以去读这篇文章。

欢迎转载，转载请注明出处wenmingxing 小探红黑树