全网最详细的红黑树的基本性质详解及原因和时间复杂度解析

红黑树的基本性质

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

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

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

为什么从任意节点到叶子节点&＃xff0c;结果的黑色节点是一样多的呢&＃xff1f;

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

严格意义上讲&＃xff0c;不是平衡二叉树

节点数总数为n&＃xff0c;最大高度是2logn&＃xff0c;

增删改查级别都是Ologn。

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