2.10、说一说红黑树？

红黑树概述

红黑树是一种自平衡的二叉查找树（BST），其核心特点是在普通二叉查找树的基础上，每个节点额外带有颜色属性（红色或黑色），通过对节点颜色的约束来保证树的平衡性，从而使得插入、删除和查找操作在最坏情况下都能保持 (O(\log n)) 的时间复杂度。

红黑树的性质

一棵合法的红黑树必须满足以下性质：

1. 1. 节点颜色：每个节点是红色或黑色。
2. 2. 根节点为黑色：根节点必须是黑色（部分资料中此条可放宽，插入后若根为红色会立即染黑，保证分析的简洁性）。
3. 3. 叶子节点为黑色：所有叶子节点（NIL节点，即空节点）都是黑色的。
4. 4. 红色节点的子节点必须是黑色：即不存在两个连续的红色节点（红色节点的父节点和子节点均为黑色）。
5. 5. 黑色节点数相等：从任一节点到其所有叶子节点的路径上，包含相同数量的黑色节点。

这些性质保证了红黑树的关键特性：从根节点到任一叶子的最长路径不会超过最短路径的两倍长度，从而保证了树的高度是对数级别，确保了操作的高效性。

红黑树的设计意义与优势

1. 自平衡能力

通过颜色和旋转操作，红黑树在插入和删除节点时动态维护平衡，避免了普通二叉查找树在极端情况下退化成链表，导致操作效率下降到 (O(n))。

2. 性能折中

相比于AVL树，红黑树牺牲了部分平衡性（允许高度差更大），但减少了旋转次数，插入和删除操作更高效，整体性能更适合动态插入和删除频繁的场景。

3. 最坏情况保证

红黑树保证了查找、插入、删除操作的最坏时间复杂度均为 (O(\log n))，这使其在实际系统中被广泛采用，如STL中的 std::map 和 std::set，以及Linux内核管理内存区间的实现。

红黑树的操作关键点

1. 节点结构

每个节点包含关键字、颜色、指向父节点、左子节点和右子节点的指针。

enum Color { RED, BLACK };

template<typename T>
struct RBTreeNode {
    T key;
    Color color;
    RBTreeNode *left;
    RBTreeNode *right;
    RBTreeNode *parent;
    RBTreeNode(T k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

2. 插入操作

• • 按二叉查找树规则插入新节点，初始颜色为红色。
• • 通过旋转（左旋、右旋）和重新着色来修正红黑树性质，避免出现连续红色节点和不平衡。

3. 删除操作

• • 删除节点后，可能破坏红黑性质。
• • 通过复杂的颜色调整和旋转操作恢复红黑性质。

4. 旋转操作

• • 左旋：将某节点的右子节点提升为该节点的父节点，调整指针关系。
• • 右旋：与左旋相反，将某节点的左子节点提升为该节点的父节点。
• • 旋转操作不会破坏二叉查找树的有序性，但能有效调整树的结构以恢复红黑树的平衡。

红黑树与其他数据结构的比较

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）