阅读量:0
红黑树是一种自平衡的二叉搜索树,确保树的高度始终保持在 O(log n) 级别,保证了在最坏情况下的查找、插入和删除操作的时间复杂度为 O(log n)。
每个节点都有一个颜色属性,红色或黑色。根节点为黑色,叶节点(NIL节点)为黑色。
如果一个节点是红色的,则其子节点必须是黑色的,这确保了从根节点到叶节点的任意路径上不能有两个连续的红色节点。
从任一节点到其子树中每个叶节点的所有路径上包含相同数目的黑色节点,这被称为黑高度,保证了红黑树的平衡。
插入和删除操作会在保持上述性质的前提下进行旋转和重新着色操作,以维持红黑树的特性。
红黑树可以用于实现有序映射和集合等数据结构,广泛应用于平衡树、数据库索引等领域。