红黑树概述和原理

红黑树概述

     红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。这一点在我们了解了红黑树的实现原理后,就会有更加深切的体会。
     红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。学过数据结构的人应该都已经领教过AVL树的复杂,但AVL树的复杂比起红黑树来说简直是小巫见大巫,红黑树才是真正的变态级数据结构。
     由于STL中的关联式容器默认的底层实现都是红黑树,因此红黑树对于后续学习STL源码还是很重要的,有必要掌握红黑树的实现原理和源码实现。
     红黑树是AVL树的变种,红黑树通过一些着色法则确保没有一条路径会比其它路径长出两倍,因而达到接*衡的目的。所谓红黑树,不仅是一个二叉搜索树,而且必须满足一下规则:
     1、每个节点不是红色就是黑色。
     2、根节点为黑色。
     3、如果节点为红色,其子节点必须为黑色。
     4、任意一个节点到到NULL(树尾端)的任何路径,所含之黑色节点数必须相同。

上一篇:整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构


下一篇:AVL树