首页   快速返回

红黑树要点整理     所属分类 architecture
红黑树是每个节点都带有颜色属性的二叉查找树且满足以下特征

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
5. 叶子节点为黑色

红黑树引入了 颜色 ,简化树的平衡 
Being Partly balanced can be good enough
红黑树并不追求 完全平衡 ,  只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。  

时间复杂度和AVL相同,但统计性能比AVL更高。
AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树

AVL树名字源于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis

红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。任何不平衡都会在3次旋转之内解决。

AVL是严格平衡树,增加或者删除节点时,旋转的次数比红黑树要多,所以红黑树的插入效率更高

由于AVL高度平衡,因此AVL的search效率更高

上一篇     下一篇
spring xml bean 配置读取

为何要定投指数基金

spring5事件机制

BeanFactory和ApplicationContext的区别

jvm在线诊断工具greys

.profile 与 .bash_profile