C++ `std::map`/`std::set`的底层红黑树（Red-Black Tree）实现：平衡与查找效率 - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

C++ `std::map`/`std::set`的底层红黑树实现：平衡与查找效率

大家好，今天我们来深入探讨C++标准库中std::map和std::set容器的底层实现，也就是红黑树。这两种容器都以红黑树作为其基础数据结构，这使得它们能够在保持键值有序的同时，实现高效的插入、删除和查找操作。我们的目标是理解红黑树的特性，了解它是如何维持平衡的，以及为什么它能够提供优秀的性能。

红黑树：自平衡二叉搜索树

红黑树是一种自平衡的二叉搜索树。所谓自平衡，指的是它能够在插入和删除节点时，通过一系列旋转和着色操作，自动调整树的结构，从而维持树的平衡，避免极端情况下退化成链表，保证了操作的时间复杂度。

红黑树需要满足以下五个性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
所有叶子节点（NIL节点，空节点）都是黑色。 NIL节点不存储数据，仅作为树结构的终点。
如果一个节点是红色，那么它的两个子节点都是黑色。 这意味着不能有两个相邻的红色节点。
从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。 这个数目被称为节点的黑高。

这五个性质是红黑树保持平衡的关键。它们确保了红黑树的最长路径不会超过最短路径的两倍，从而限制了树的高度。

红黑树的节点结构

在C++实现中，红黑树的节点通常包含以下信息：

key: 键值，用于排序和查找。
value: 值，与键值关联的数据，std::set中没有这个字段。
color: 颜色，红色或黑色。
parent: 指向父节点的指针。
left: 指向左子节点的指针。
right: 指向右子节点的指针。

以下是一个简单的C++红黑树节点结构体的示例：

enum Color { RED, BLACK };

template <typename Key, typename Value>
struct RBNode {
    Key key;
    Value value;
    Color color;
    RBNode* parent;
    RBNode* left;
    RBNode* right;

    RBNode(const Key& k, const Value& v) : key(k), value(v), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
};

template <typename Key>
struct RBNode<Key, void> { // for std::set
    Key key;
    Color color;
    RBNode* parent;
    RBNode* left;
    RBNode* right;

    RBNode(const Key& k) : key(k), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
};

注意，这里使用了模板，Value类型在std::map中使用，而在std::set中被设置为void，并通过模板特化来简化节点结构。

红黑树的旋转操作

旋转是红黑树维持平衡的核心操作。通过旋转，可以改变节点的父子关系，从而调整树的结构。红黑树有两种基本的旋转操作：左旋和右旋。

左旋 (Left Rotate)

左旋以某个节点 x 为中心进行，假设 x 的右子节点为 y。左旋的目的是将 y 提升到 x 的位置，并调整相关的子树。

步骤如下：

将 y 的左子节点 y->left 变成 x 的右子节点 x->right。
如果 y->left 非空，则更新 y->left->parent 指向 x。
将 x 的父节点 x->parent 赋值给 y 的父节点 y->parent。
如果 x 是根节点，则将 y 设置为根节点。
否则，如果 x 是其父节点的左子节点，则将 y 设置为其父节点的左子节点；如果 x 是其父节点的右子节点，则将 y 设置为其父节点的右子节点。
将 x 设置为 y 的左子节点 y->left。
将 y 设置为 x 的父节点 x->parent。

template <typename Key, typename Value>
void leftRotate(RBNode<Key, Value>* root, RBNode<Key, Value>* x) {
    RBNode<Key, Value>* y = x->right;
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        root = y; // x was root
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

template <typename Key>
void leftRotate(RBNode<Key, void>*& root, RBNode<Key, void>* x) {
    RBNode<Key, void>* y = x->right;
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        root = y; // x was root
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

右旋 (Right Rotate)

右旋与左旋对称，以某个节点 y 为中心进行，假设 y 的左子节点为 x。右旋的目的是将 x 提升到 y 的位置，并调整相关的子树。

步骤如下：

将 x 的右子节点 x->right 变成 y 的左子节点 y->left。
如果 x->right 非空，则更新 x->right->parent 指向 y。
将 y 的父节点 y->parent 赋值给 x 的父节点 x->parent。
如果 y 是根节点，则将 x 设置为根节点。
否则，如果 y 是其父节点的左子节点，则将 x 设置为其父节点的左子节点；如果 y 是其父节点的右子节点，则将 x 设置为其父节点的右子节点。
将 y 设置为 x 的右子节点 x->right。
将 x 设置为 y 的父节点 y->parent。

template <typename Key, typename Value>
void rightRotate(RBNode<Key, Value>* root, RBNode<Key, Value>* y) {
    RBNode<Key, Value>* x = y->left;
    y->left = x->right;
    if (x->right != nullptr) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == nullptr) {
        root = x; // y was root
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }
    x->right = y;
    y->parent = x;
}

template <typename Key>
void rightRotate(RBNode<Key, void>*& root, RBNode<Key, void>* y) {
    RBNode<Key, void>* x = y->left;
    y->left = x->right;
    if (x->right != nullptr) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == nullptr) {
        root = x; // y was root
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }
    x->right = y;
    y->parent = x;
}

红黑树的插入操作

红黑树的插入操作首先按照二叉搜索树的规则插入新节点，然后通过一系列的旋转和着色操作来维持红黑树的性质。

二叉搜索树插入： 找到合适的位置插入新节点，并将新节点的颜色设置为红色。
修复红黑树性质： 由于插入红色节点可能会违反红黑树的性质（特别是性质4：不能有两个相邻的红色节点），因此需要进行修复。

修复过程通常包括以下几种情况：

情况1： 新节点的父节点是黑色。此时不需要任何操作，红黑树性质仍然保持。
情况2： 新节点的父节点是红色，且新节点的叔叔节点也是红色。此时需要将父节点和叔叔节点都着色为黑色，祖父节点着色为红色，然后将祖父节点作为新的节点，递归地进行修复。
情况3： 新节点的父节点是红色，新节点的叔叔节点是黑色，且新节点是父节点的右子节点。此时需要对父节点进行左旋，然后转换成情况4。
情况4： 新节点的父节点是红色，新节点的叔叔节点是黑色，且新节点是父节点的左子节点。此时需要将父节点着色为黑色，祖父节点着色为红色，然后对祖父节点进行右旋。

以下是插入操作的C++代码示例：

template <typename Key, typename Value>
void insert(RBNode<Key, Value>*& root, const Key& key, const Value& value) {
    RBNode<Key, Value>* z = new RBNode<Key, Value>(key, value);
    RBNode<Key, Value>* y = nullptr;
    RBNode<Key, Value>* x = root;

    while (x != nullptr) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == nullptr) {
        root = z; // empty tree
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }

    insertFixup(root, z);
}

template <typename Key>
void insert(RBNode<Key, void>*& root, const Key& key) {
    RBNode<Key, void>* z = new RBNode<Key, void>(key);
    RBNode<Key, void>* y = nullptr;
    RBNode<Key, void>* x = root;

    while (x != nullptr) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == nullptr) {
        root = z; // empty tree
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }

    insertFixup(root, z);
}

template <typename Key, typename Value>
void insertFixup(RBNode<Key, Value>*& root, RBNode<Key, Value>* z) {
    while (z->parent != nullptr && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode<Key, Value>* y = z->parent->parent->right; // uncle
            if (y != nullptr && y->color == RED) { // Case 1: uncle is red
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else { // Case 2 & 3: uncle is black
                if (z == z->parent->right) { // Case 2: z is right child
                    z = z->parent;
                    leftRotate(root, z);
                }
                // Case 3: z is left child
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else { // Symmetric cases with left and right exchanged
            RBNode<Key, Value>* y = z->parent->parent->left; // uncle
            if (y != nullptr && y->color == RED) { // Case 1: uncle is red
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else { // Case 2 & 3: uncle is black
                if (z == z->parent->left) { // Case 2: z is left child
                    z = z->parent;
                    rightRotate(root, z);
                }
                // Case 3: z is right child
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    root->color = BLACK; // Root is always black
}

template <typename Key>
void insertFixup(RBNode<Key, void>*& root, RBNode<Key, void>* z) {
    while (z->parent != nullptr && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode<Key, void>* y = z->parent->parent->right; // uncle
            if (y != nullptr && y->color == RED) { // Case 1: uncle is red
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else { // Case 2 & 3: uncle is black
                if (z == z->parent->right) { // Case 2: z is right child
                    z = z->parent;
                    leftRotate(root, z);
                }
                // Case 3: z is left child
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else { // Symmetric cases with left and right exchanged
            RBNode<Key, void>* y = z->parent->parent->left; // uncle
            if (y != nullptr && y->color == RED) { // Case 1: uncle is red
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else { // Case 2 & 3: uncle is black
                if (z == z->parent->left) { // Case 2: z is left child
                    z = z->parent;
                    rightRotate(root, z);
                }
                // Case 3: z is right child
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    root->color = BLACK; // Root is always black
}

红黑树的删除操作

红黑树的删除操作也比一般的二叉搜索树复杂，因为它需要在删除节点后，通过一系列的旋转和着色操作来维持红黑树的性质。

二叉搜索树删除： 找到要删除的节点，并按照二叉搜索树的规则删除该节点。如果被删除的节点有两个子节点，通常会用它的后继节点（右子树中最小的节点）来替换它。
修复红黑树性质： 删除节点后，可能会违反红黑树的性质，因此需要进行修复。如果被删除的节点是黑色，则会影响黑高，需要修复。

修复过程比较复杂，涉及到多种情况，这里只简单描述一下思路：

如果被删除的节点是红色，且其替换节点是红色，那么直接将替换节点着色为黑色即可。
如果被删除的节点是黑色，或者其替换节点是黑色，那么需要进行一系列的旋转和着色操作，以恢复红黑树的性质。这些操作的目标是确保从任何节点到其每个叶子节点的路径都包含相同数目的黑色节点。

删除操作的实现比较复杂，这里省略具体的代码，但理解其基本思路是关键。重点在于删除后，需要根据不同的情况，进行旋转和着色，以维持红黑树的平衡。

红黑树的查找操作

红黑树的查找操作与普通的二叉搜索树的查找操作类似。从根节点开始，根据键值的大小，逐步向下搜索，直到找到目标节点或者到达叶子节点。由于红黑树是平衡的，因此查找操作的时间复杂度为 O(log n)。

以下是查找操作的C++代码示例：

template <typename Key, typename Value>
RBNode<Key, Value>* find(RBNode<Key, Value>* root, const Key& key) {
    RBNode<Key, Value>* x = root;
    while (x != nullptr) {
        if (key < x->key) {
            x = x->left;
        } else if (key > x->key) {
            x = x->right;
        } else {
            return x;
        }
    }
    return nullptr;
}

template <typename Key>
RBNode<Key, void>* find(RBNode<Key, void>* root, const Key& key) {
    RBNode<Key, void>* x = root;
    while (x != nullptr) {
        if (key < x->key) {
            x = x->left;
        } else if (key > x->key) {
            x = x->right;
        } else {
            return x;
        }
    }
    return nullptr;
}

红黑树的性能分析

红黑树的自平衡性质保证了其操作的时间复杂度。

操作	时间复杂度
插入	O(log n)
删除	O(log n)
查找	O(log n)
最小值	O(log n)
最大值	O(log n)
前驱节点	O(log n)
后继节点	O(log n)

由于红黑树的高度最多为 2 * log2(n+1)，因此所有操作的时间复杂度都为 O(log n)。这使得红黑树成为一种非常高效的数据结构，特别适合于需要频繁进行插入、删除和查找操作的场景。这也是为什么std::map和std::set选择红黑树作为底层实现的原因。

红黑树在`std::map`/`std::set`中的应用

std::map和std::set都是关联容器，它们都使用红黑树作为其底层数据结构。 std::map存储键值对，而std::set存储键的集合。

std::map: std::map使用红黑树来存储键值对，并根据键值进行排序。这使得std::map能够快速地根据键值查找对应的值。
std::set: std::set使用红黑树来存储键的集合，并保证键的唯一性。这使得std::set能够快速地判断一个键是否存在于集合中。

std::map和std::set都提供了高效的插入、删除和查找操作，这使得它们成为C++中常用的容器。

平衡树的权衡：优势与代价

使用红黑树作为底层数据结构，std::map和std::set在查找、插入和删除操作上都实现了O(log n)的时间复杂度，这是一个显著的优势。这使得这些容器在需要频繁进行这些操作的场景中表现出色。

然而，这种平衡也带来了一些代价。

空间开销： 红黑树需要在每个节点中存储颜色、父节点和子节点等额外信息，这会增加空间开销。
实现复杂性： 红黑树的插入和删除操作比普通的二叉搜索树复杂得多，需要进行旋转和着色等操作来维持平衡。这增加了实现的复杂性，也可能导致更高的代码维护成本。
常数因子： 虽然时间复杂度都是O(log n)，但红黑树的旋转和着色操作会带来一定的常数因子，在某些特定场景下，可能不如一些简单的、非平衡的数据结构。

因此，在选择数据结构时，需要根据具体的应用场景进行权衡。如果需要频繁进行插入、删除和查找操作，并且对性能要求较高，那么std::map和std::set是一个不错的选择。但如果对空间开销非常敏感，或者操作的频率不高，那么可以考虑其他的数据结构。

理解实现细节对性能的影响

深入理解红黑树的实现细节，可以帮助我们更好地理解std::map和std::set的性能特点，从而编写出更高效的代码。例如，了解旋转操作的开销，可以避免不必要的旋转操作，从而提高性能。了解着色操作的规则，可以帮助我们更好地理解红黑树的平衡机制。

此外，不同的编译器和标准库实现可能对红黑树的实现细节有所不同。因此，在进行性能优化时，需要针对具体的编译器和标准库进行测试和分析。

总而言之，深入理解红黑树的实现细节，可以帮助我们更好地利用std::map和std::set，编写出更高效、更健壮的代码。

红黑树提供平衡，`std::map`/`std::set`提供高效

红黑树作为std::map和std::set的底层实现，通过自平衡机制，保证了插入、删除和查找操作的O(log n)时间复杂度，使其成为需要高效操作的关联容器的理想选择。虽然存在空间开销和实现复杂性等代价，但在大多数情况下，其性能优势使其成为首选的数据结构。深入理解红黑树的实现细节，有助于更好地利用这些容器，编写出更高效的代码。

更多IT精英技术系列讲座，到智猿学院

C++ std::map/std::set的底层红黑树实现：平衡与查找效率