面试题：C++ 中红黑树节点的基本结构实现

Question

请用C++ 实现红黑树节点的基本结构，节点需包含键值、颜色（可以用枚举表示）以及指向父节点、左子节点和右子节点的指针。并简单阐述红黑树节点颜色的作用。

Answer 1

// 定义红黑树节点颜色枚举
enum class Color {
    RED,
    BLACK
};

// 红黑树节点结构
template <typename Key>
struct RBNode {
    Key key;        // 键值
    Color color;    // 颜色
    RBNode* parent; // 指向父节点的指针
    RBNode* left;   // 指向左子节点的指针
    RBNode* right;  // 指向右子节点的指针

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

红黑树节点颜色的作用

1. 保持树的平衡：红黑树通过节点颜色以及一系列规则（如红色节点的子节点必须是黑色；从根到叶节点的所有路径包含相同数量的黑色节点等）来保证树的大致平衡。这样能使得插入、删除和查找操作在最坏情况下的时间复杂度仍为O(log n)。
2. 简化操作：在进行插入和删除操作时，利用节点颜色进行调整操作（如变色、旋转等），相比其他平衡树（如AVL树），红黑树的调整操作相对简单且高效，这使得红黑树在动态数据结构的应用场景中表现出色。