自平衡二叉查找树，典型的用途是实现关联数组。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
平均统计性能要强于 AVL
•
查找时可以当成普通二叉排序树
•
每一个子树也是红黑树
性质
1.
根结点是黑色。
2.
结点是红色或黑色。
3.
所有叶子都是黑色。（叶子是NIL结点） (不存储数据的节点,可以忽略)
4.
每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
5.
从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。
是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。
评论区