数据结构之红黑树

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

系列文章目录

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

定义

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

演示

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

红黑树性质

必须要满足的五条性质：

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

应用场景

红黑树是一种不是非常严格的平衡二叉树，没有AVLtree那么严格的平衡要求，所以它的平均查找，增添删除效率都还不错。广泛用在C++的STL中。如map和set都是用红黑树实现的。