视频字幕
红黑树是一种特殊的自平衡二叉搜索树。它在每个节点上增加了颜色属性，可以是红色或黑色。通过维护特定的颜色性质，红黑树能够保证树的高度始终保持在对数级别，从而确保查找、插入和删除操作在最坏情况下的时间复杂度都是O(log n)。这使得红黑树成为许多标准库中关联容器的理想实现选择。
红黑树必须满足五条重要性质。性质一规定每个节点要么是红色要么是黑色。性质二要求根节点必须是黑色。性质三规定所有叶子节点，也就是NIL节点，都是黑色的。性质四是关键约束：如果一个节点是红色，那么它的两个子节点都必须是黑色，这确保不会有连续的红色节点。性质五保证从任一节点到其所有叶子节点的路径上，黑色节点的数量相同，这被称为黑高，是维持平衡的核心。
为了维持红黑树的性质，我们需要两种基本操作：变色和旋转。变色操作很简单，就是改变节点的颜色属性。旋转操作则更复杂一些。左旋是以某个节点X为轴，将其右子节点Y提升，X成为Y的左子节点，同时Y原来的左子树B成为X的右子树。右旋则相反，是将左子节点提升。这些操作在保持二叉搜索树性质的同时，调整树的结构来维持红黑树的平衡性质。
让我们通过一个具体例子来看插入操作。假设我们要向红黑树中插入节点15。首先，按照二叉搜索树的规则找到插入位置，将新节点标记为红色。插入后发现违反了性质4，因为出现了连续的红色节点。由于叔叔节点是黑色，我们需要进行旋转和变色操作来修复。最终将父节点20变为黑色，这样就恢复了红黑树的所有性质。插入操作的时间复杂度是O(log n)。
红黑树的所有基本操作——查找、插入和删除——的时间复杂度都是O(log n)，这得益于其自平衡的特性。红黑树在实际应用中非常广泛，包括C++标准库的map和set容器、Java的TreeMap和TreeSet、操作系统的调度器以及数据库索引等。与AVL树相比，红黑树的平衡条件相对宽松，虽然查找性能略逊，但在插入和删除操作上更加高效，因此在需要频繁修改的场景中更受青睐。红黑树的高度最多是2log(n+1)，保证了良好的性能表现。