[数据结构与算法]全网最详细的红黑树的基本性质详解及原因和时间复杂度解析

红黑树的基本性质

1. 节点要么是红色，要么是黑色。
2. 根节点是黑色
3. 每一个叶子节点(最后的空节点) 是黑色的
4. 每个红节点的两个孩子节点都是黑的
5. 从任意节点到叶子节点 ，结果的黑色节点是一样多的
   

根节点为什么是黑色？
根据前个文章，红黑树是由2-3树衍生而来的，根据图示，根节点只能是黑色。

为什么每一个叶子节点(最后的空节点) 是黑色的？
这个相当于一个定义

为什么从任意节点到叶子节点，结果的黑色节点是一样多的呢？

因为2-3树是完全平衡的二叉树，所以深度是一样的，红黑树是由2-3树演变而来，每经过一个黑色节点，都相当于结果一个2-3树的节点，经过红节点的时候，不经过2-3树的节点，所以成立
红黑树是一个保持黑平衡的二叉树。

严格意义上讲，不是平衡二叉树

节点数总数为n，最大高度是2logn，

增删改查级别都是Ologn。

相对于AVL树，查询会慢一点，但是增删改会快很多。