C++ 构建自己的 `std::map`：理解红黑树的内部结构

好的，咱们今天来聊聊C++里一个很重要的家伙：std::map。别看它用起来简单，背后可藏着不少秘密呢！咱们今天就来扒一扒它的底裤，看看它是怎么用红黑树来实现的，并且尝试着自己动手撸一个简化版的 my_map。

开场白：std::map 是个啥？

简单来说，std::map 就是一个键值对（key-value pair）的容器。它能让你通过一个键快速地找到对应的值。就像字典一样，你知道一个单词（key），就能查到它的解释（value）。

std::map 的特点：

键是唯一的： 同一个键只能对应一个值。
自动排序： 键会按照某种规则自动排序（默认是 < 运算符）。
高效查找： 查找、插入、删除操作的时间复杂度都是 O(log n)。

为啥 std::map 这么快？红黑树是幕后英雄！

std::map 能这么高效，主要归功于它的底层实现：红黑树。红黑树是一种自平衡的二叉搜索树。啥意思呢？

二叉搜索树（Binary Search Tree）： 每个节点最多有两个子节点，左子节点的值小于父节点，右子节点的值大于父节点。这样查找起来就像二分查找一样，很快。
自平衡： 二叉搜索树有个缺点，如果数据是顺序插入的，就会变成一个链表，查找效率退化成 O(n)。红黑树通过一些规则来保持树的平衡，避免变成链表。

红黑树的五大纪律（性质）

红黑树要维持平衡，就必须遵守以下五条纪律：

节点是红色或黑色： 每个节点要么是红色，要么是黑色。
根节点是黑色： 树的根节点必须是黑色。
叶子节点是黑色： 所有叶子节点（NIL 节点，空节点）都是黑色。
红色节点的子节点是黑色： 如果一个节点是红色，那么它的两个子节点必须是黑色。不能有两个相邻的红色节点。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点： 这个性质保证了树的平衡性。

这五条纪律听起来有点枯燥，但它们是红黑树能够保持平衡的关键。

红黑树的旋转大法

为了维持红黑树的平衡，在插入和删除节点时，可能需要进行旋转操作。旋转分为左旋和右旋。

左旋（Left Rotate）： 以某个节点为轴，将该节点向左旋转，将该节点的右子节点变成父节点。
右旋（Right Rotate）： 以某个节点为轴，将该节点向右旋转，将该节点的左子节点变成父节点。

旋转的目的是调整节点的结构，使得树更加平衡。

自己动手撸一个 my_map (简化版)

理论说了这么多，咱们来点实际的。现在咱们来自己动手写一个简化版的 my_map，让你更深入地理解红黑树的实现。

#include <iostream>
#include <utility> // std::pair

template <typename Key, typename Value>
class my_map {
private:
  // 节点颜色
  enum Color { RED, BLACK };

  // 节点结构体
  struct Node {
    Key key;
    Value value;
    Node *left;
    Node *right;
    Node *parent;
    Color color;

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

  Node *root;
  size_t size;

public:
  my_map() : root(nullptr), size(0) {}

  ~my_map() {
    // 释放内存，避免内存泄漏
    destroy_tree(root);
  }

  // 插入键值对
  void insert(const Key& key, const Value& value) {
    Node *newNode = new Node(key, value);
    if (!root) {
      root = newNode;
      root->color = BLACK; // 根节点必须是黑色
    } else {
      Node *current = root;
      Node *parent = nullptr;

      // 找到插入位置
      while (current) {
        parent = current;
        if (key < current->key) {
          current = current->left;
        } else if (key > current->key) {
          current = current->right;
        } else {
            // 如果键已经存在，更新值
            current->value = value;
            delete newNode; // 避免内存泄漏
            return;
        }
      }

      newNode->parent = parent;
      if (key < parent->key) {
        parent->left = newNode;
      } else {
        parent->right = newNode;
      }

      // 调整红黑树
      fix_insert(newNode);
    }
    size++;
  }

  // 查找键对应的值
  Value& operator[](const Key& key) {
    Node *current = root;
    while (current) {
      if (key < current->key) {
        current = current->left;
      } else if (key > current->key) {
        current = current->right;
      } else {
        return current->value;
      }
    }
    // 如果键不存在，插入一个新的键值对，并返回新值的引用
    insert(key, Value()); // 使用默认构造函数创建Value对象
    return operator[](key); // 递归调用，返回新插入的值的引用
  }

  // 获取map的大小
  size_t getSize() const {
    return size;
  }

private:
  // 左旋
  void left_rotate(Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left) {
      y->left->parent = x;
    }
    y->parent = x->parent;
    if (!x->parent) {
      root = y;
    } else if (x == x->parent->left) {
      x->parent->left = y;
    } else {
      x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
  }

  // 右旋
  void right_rotate(Node *x) {
    Node *y = x->left;
    x->left = y->right;
    if (y->right) {
      y->right->parent = x;
    }
    y->parent = x->parent;
    if (!x->parent) {
      root = y;
    } else if (x == x->parent->left) {
      x->parent->left = y;
    } else {
      x->parent->right = y;
    }
    y->right = x;
    x->parent = y;
  }

  // 插入后调整红黑树
  void fix_insert(Node *z) {
    while (z->parent && z->parent->color == RED) {
      if (z->parent == z->parent->parent->left) {
        Node *y = z->parent->parent->right; // uncle
        if (y && 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: uncle is black and z is right child
          if (z == z->parent->right) {
            z = z->parent;
            left_rotate(z);
          }
          // case 3: uncle is black and z is left child
          z->parent->color = BLACK;
          z->parent->parent->color = RED;
          right_rotate(z->parent->parent);
        }
      } else {
        // mirror image of above
        Node *y = z->parent->parent->left;
        if (y && y->color == RED) {
          z->parent->color = BLACK;
          y->color = BLACK;
          z->parent->parent->color = RED;
          z = z->parent->parent;
        } else {
          if (z == z->parent->left) {
            z = z->parent;
            right_rotate(z);
          }
          z->parent->color = BLACK;
          z->parent->parent->color = RED;
          left_rotate(z->parent->parent);
        }
      }
    }
    root->color = BLACK; // 根节点必须是黑色
  }

  // 销毁树，释放内存
  void destroy_tree(Node *node) {
    if (node) {
      destroy_tree(node->left);
      destroy_tree(node->right);
      delete node;
    }
  }
};

int main() {
  my_map<int, std::string> myMap;
  myMap.insert(3, "Alice");
  myMap.insert(1, "Bob");
  myMap.insert(2, "Charlie");

  std::cout << "Size: " << myMap.getSize() << std::endl;
  std::cout << "Key 1: " << myMap[1] << std::endl;
  std::cout << "Key 2: " << myMap[2] << std::endl;
  std::cout << "Key 3: " << myMap[3] << std::endl;
  std::cout << "Key 4: " << myMap[4] << std::endl; // 插入新的键值对

  return 0;
}

代码讲解

Node 结构体： 定义了红黑树的节点，包含了键、值、左右子节点、父节点和颜色。
insert() 函数： 插入一个新的键值对。首先找到合适的插入位置，然后创建一个新的节点，并将其插入到树中。插入后，需要调用 fix_insert() 函数来调整红黑树，保持平衡。
left_rotate() 和 right_rotate() 函数： 实现左旋和右旋操作。
fix_insert() 函数： 插入节点后，调整红黑树，保持平衡。这个函数比较复杂，需要考虑多种情况。
operator[] 函数： 实现 [] 运算符，用于查找键对应的值。如果键不存在，则插入一个新的键值对，并返回新值的引用。
destroy_tree() 函数： 用于释放内存，避免内存泄漏。

重点：fix_insert() 函数

fix_insert() 函数是红黑树插入操作中最复杂的部分。它需要根据插入节点的颜色和其叔叔节点的颜色来决定如何调整树的结构。主要有以下几种情况：

情况	叔叔节点颜色	调整方式
1	红色	将父节点和叔叔节点都设为黑色，祖父节点设为红色，然后将当前节点指向祖父节点，继续向上调整。
2	黑色	如果当前节点是父节点的右子节点，先对父节点进行左旋，然后将当前节点指向父节点。
3	黑色	将父节点设为黑色，祖父节点设为红色，然后对祖父节点进行右旋。

性能分析

插入： O(log n)
查找： O(log n)
删除： O(log n)

红黑树的平衡性保证了这些操作的时间复杂度都是 O(log n)，这使得 std::map 在大量数据的情况下也能保持高效。

std::map 的高级用法

std::map 除了基本的插入、查找功能，还有一些高级用法：

自定义比较函数： 你可以自定义比较函数，改变键的排序规则。
lower_bound() 和 upper_bound()： 这两个函数可以查找键的范围。
equal_range()： 这个函数可以返回一个包含所有与给定键相等的元素的范围。

总结

今天咱们一起深入了解了 std::map 的底层实现：红黑树。咱们学习了红黑树的五大纪律、旋转操作，并且自己动手撸了一个简化版的 my_map。希望通过今天的学习，你对 std::map 有了更深入的理解，以后在使用它的时候也能更加得心应手。

当然，咱们实现的 my_map 只是一个简化版，还有很多功能没有实现，比如删除操作、迭代器等等。如果你有兴趣，可以继续完善它，让它更接近 std::map 的功能。

希望这篇文章对你有所帮助！下次再见！

发表回复 取消回复

发表回复取消回复