深入解析C++中的红黑树

红黑树概述

红黑树是一种自平衡二叉查找树，每个节点都具有一个存储位来表示颜色（红色或黑色）。这种颜色标记帮助红黑树保持一种近似的平衡状态，从而保证了树的高度不会过于倾斜，提高了数据检索的效率。

红黑树和AVL树同属高效的平衡二叉树类型，两者在插入、删除、查找等操作上的时间复杂度均为O(log n)。然而，红黑树并不追求绝对的平衡，而是在一定程度上允许不平衡的存在，这减少了插入和删除操作时的旋转次数，因此在频繁进行插入和删除操作的数据结构中，红黑树的表现往往优于AVL树。

红黑树的特性

• 每个节点要么是红色，要么是黑色。


• 根节点始终是黑色。


• 如果一个节点是红色的，则它的两个子节点必须是黑色的。


• 从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点。


• 所有的叶子节点（NIL节点，空节点）都是黑色的。

红黑树节点的定义

enum Color { BLACK, RED };
template
struct RBTreeNode {
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    Color _color;
    T _value;

    RBTreeNode(const T& value)
        : _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED), _value(value) {}
};

红黑树的插入操作

在红黑树中插入一个新节点可能会导致树失去平衡。为了恢复平衡，需要执行一系列的重着色和旋转操作。具体来说，根据新节点与其父节点、祖父节点及叔父节点之间的关系，可以将插入后的情况分为三种主要类型，每种类型都有对应的调整策略。

情况一：双红问题

当新插入的红色节点的父节点也是红色时，且祖父节点存在且为黑色，同时叔父节点也存在且为红色。此时，解决方案是将父节点和叔父节点变为黑色，祖父节点变为红色，然后将祖父节点视为新的待处理节点，继续向上检查是否仍需调整。

情况二：直接旋转

当新插入的红色节点的父节点也是红色，但叔父节点不存在或为黑色，且新节点与其父节点位于祖父节点的同一侧时，可以通过一次单旋转加颜色调整来解决问题。

情况三：间接旋转

当新插入的红色节点的父节点也是红色，但叔父节点不存在或为黑色，且新节点与其父节点不在祖父节点的同一侧时，首先需要通过一次单旋转将新节点调整到与情况二相同的位置，然后再进行一次单旋转以完成最终的平衡调整。

红黑树的验证

验证一棵树是否为有效的红黑树，通常需要检查两个方面：一是确保树满足二叉搜索树的条件，即左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值；二是确认树满足上述五条红黑树的特性。

使用红黑树实现map和set

红黑树迭代器

为了使红黑树能够像标准容器一样使用，需要为其提供迭代器支持。红黑树的迭代器应能正确地遍历树中的所有节点，从最小值节点开始，直到最大值节点结束。

实现map

通过红黑树实现的map容器，可以高效地存储键值对，并支持快速查找、插入和删除操作。其实现涉及定义一个内部结构来表示键值对，并利用红黑树的插入和查找功能。

实现set

类似地，通过红黑树实现的set容器用于存储唯一元素，同样支持高效的查找、插入和删除操作。其实现原理与map类似，只是不需要处理键值对，而是直接管理单一类型的元素。