数据结构之红黑树-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之红黑树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构可视化演示链接，也就是图片演示的网址

系列文章目录

数据结构之AVL Tree
数据结构之B树和B+树
数据结构之Radix和Trie
数据结构之二叉搜索树

定义

红黑树是一种二叉查找树，但在每个结点上增加了一个存储位表示结点的颜色，可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。当二叉查找树的高度较低时，这些操作执行的比较快，但是当树的高度较高时，这些操作的性能可能不比用链表好。红黑树（red-black tree）是一种平衡的二叉查找树，它能保证在最坏情况下，基本的动态操作集合运行时间为O(lgn)。

演示

可以结合性质看更容易理解

红黑树

红黑树性质

必须要满足的五条性质：

节点是红色或者是黑色；在树里面的节点不是红色的就是黑色的，没有其他颜色。
根节点是黑色，它不能为红。
每个叶节点（NIL或空节点）是黑色；
每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点），就是连续的两个节点不能是连续的红色，连续的两个节点的意思就是父节点与子节点不能是连续的红色。
从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。从根节点到每一个NIL节点的路径中，都包含了相同数量的黑色节点。