他一口气写出了这7k字的红黑树总结！

种很经典的数据结构，它可以在O(log n)时间内做查找，插入和删除。所以倍受关注。但是一直以来很多Java程序员对他都不是很重视，直到在JDK 1.8中，HashMap会将其链表转换成红黑树，此后，很多人就开始重新学习红黑树的有关知识。

作者在学习红黑树时，查阅了很多资料都没有找到解释的特别清楚的，于是自己总结了这一篇文章，总字数近7k，而且绘制了很多图，希望可以让大家更容易理解。

1. 定义

红黑树是Avl树的一个变种，它也是在二叉查找树的基础上添加平衡条件，只是它对平衡条件的描述不像AVl树那样直接，而是转化成对节点颜色规则的描述。

颜色规则：

1. 对于任意节点，要么是红色，要么是黑色;
2. 根节点是黑色的;
3. 如果一个节点是红色的，那么它的子节点必须是黑色的(即不能有两个连续的红色节点);
4. 任意节点到其下面各个空结点(后面称为nil节点，并约定其颜色为黑色)的路径上都包含相同数目的黑色节点(称为黑高);

通过对任何一条从根到空节点的路径上各个结点的颜色进行约束，红黑树可以确保没有一条路径会比其他路径长出2倍，因而红黑树是近似平衡的。
 

 分析实现

为了便于处理红黑树代码中的边界条件，使用两个标记节点header和nil来充当哨兵，它们与树中的普通节点有相同的属性，颜色设为黑色。将header的值设为负无穷，因此它的右子节点就是真正的根，在对树进行遍历时我们可以用header作为起点。nil的值可以为任意值，将它作为所有空节点的统一引用， 即让所有树叶的左右子节点都指向nil，那么在遍历时就可以将nil视为结束的标志。

（编辑：常州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!