红黑树

自平衡二叉搜索树实现 更多...

类
struct	rb_tree_node_base
	红黑树节点基类 更多...
struct	rb_tree_node< T >
	红黑树数据节点 更多...
struct	rb_tree_base_iterator
	红黑树迭代器基类 更多...
struct	rb_tree_iterator< IsConst, RbTree >
	红黑树迭代器 更多...
class	rb_tree< Key, Value, KeyOfValue, Compare, Alloc >
	红黑树容器 更多...

函数
NEFORCE_ALWAYS_INLINE_INLINE void	rb_tree_rotate_left (rb_tree_node_base *axis, rb_tree_node_base *&root) noexcept
	红黑树左旋转
NEFORCE_ALWAYS_INLINE_INLINE void	rb_tree_rotate_right (rb_tree_node_base *axis, rb_tree_node_base *&root) noexcept
	红黑树右旋转
NEFORCE_ALWAYS_INLINE_INLINE void	rb_tree_insert_rebalance (rb_tree_node_base *insert, rb_tree_node_base *&root) noexcept
	插入节点后重新平衡红黑树
NEFORCE_ALWAYS_INLINE_INLINE rb_tree_node_base *	rb_tree_erase_rebalance (rb_tree_node_base *erase, rb_tree_node_base *&root, rb_tree_node_base *&leftmost, rb_tree_node_base *&rightmost) noexcept
	删除节点后重新平衡红黑树

变量
NEFORCE_INLINE17 constexpr bool	RB_TREE_RED = false
	红黑树节点颜色常量：红色
NEFORCE_INLINE17 constexpr bool	RB_TREE_BLACK = true
	红黑树节点颜色常量：黑色

详细描述

自平衡二叉搜索树实现

遵循的国际标准

本实现严格遵循以下计算机科学文献：

• **Rudolf Bayer (1972)**："Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms" Acta Informatica, Vol. 1, pp. 290–306. https://doi.org/10.1007/BF00289509
• **Leo J. Guibas & Robert Sedgewick (1978)**："A Dichromatic Framework for Balanced Trees" Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pp. 8–21. https://doi.org/10.1109/SFCS.1978.3

红黑树性质

根据 Guibas & Sedgewick (1978) 的定义，红黑树满足以下五条性质：

1. **节点颜色**：每个节点要么是红色，要么是黑色。
2. **根节点颜色**：根节点是黑色的。
3. **叶子节点颜色**：每个叶子节点（NIL）是黑色的。
4. **红色节点限制**：如果一个节点是红色的，则它的两个子节点都是黑色的。
5. **黑色高度**：对于每个节点，从该节点到其所有后代叶子节点的简单路径上， 包含相同数量的黑色节点。

复杂度保证

根据红黑树性质，最坏情况下的时间复杂度保证：

操作	时间复杂度	说明
插入	O(log n)	最多 2 次旋转
删除	O(log n)	最多 3 次旋转
查找	O(log n)	二叉搜索树查找
最小/最大	O(log n)	沿最左/最右路径查找
前驱/后继	O(log n)	中序遍历相邻节点
范围迭代	O(k)	k 为范围内元素数量

树的高度上界：h ≤ 2 log₂(n + 1)。

注解

本实现提供了两个插入策略：

• insert_unique：键必须唯一，重复键插入失败并返回已存在元素迭代器
• insert_equal：允许重复键，按插入顺序存储

警告

根据 ISO/IEC 14882:2020 §22.2.6：

• 对关联容器的修改操作不会使任何迭代器失效，除非删除该迭代器指向的元素
• 比较函数对象（Compare）必须提供严格的弱序关系
• 键的不可变性：修改已插入元素的键会导致未定义行为

参见

https://en.cppreference.com/w/cpp/container/map

https://en.cppreference.com/w/cpp/container/set

https://doi.org/10.1109/SFCS.1978.3 (Guibas & Sedgewick)

函数说明

rb_tree_erase_rebalance()

NEFORCE_ALWAYS_INLINE_INLINE rb_tree_node_base * rb_tree_erase_rebalance ( rb_tree_node_base * erase, rb_tree_node_base *& root, rb_tree_node_base *& leftmost, rb_tree_node_base *& rightmost )

noexcept

删除节点后重新平衡红黑树

参数

erase	要删除的节点
root	树根节点引用
leftmost	最左节点引用
rightmost	最右节点引用

返回

实际被删除的节点

执行节点删除后的重新平衡操作，并更新最左最右节点。

在文件 rb_tree.hpp 第 239 行定义.

引用了 rb_tree_node_base::color_, erase(), rb_tree_node_base::left_, rb_tree_node_base::maximum(), rb_tree_node_base::minimum(), NEFORCE_DEBUG_VERIFY, rb_tree_node_base::parent_, RB_TREE_BLACK, RB_TREE_RED, rb_tree_rotate_left(), rb_tree_rotate_right(), rb_tree_node_base::right_ , 以及 swap().

被这些函数引用 rb_tree< Key, pair< const Key, T >, select1st< pair< const Key, T > >, Compare, Alloc >::erase().

rb_tree_insert_rebalance()

NEFORCE_ALWAYS_INLINE_INLINE void rb_tree_insert_rebalance ( rb_tree_node_base * insert, rb_tree_node_base *& root )

noexcept

插入节点后重新平衡红黑树

参数

insert	新插入的节点
root	树根节点引用

通过旋转和重新着色恢复红黑树的平衡性质。

在文件 rb_tree.hpp 第 186 行定义.

引用了 rb_tree_node_base::color_, rb_tree_node_base::left_, rb_tree_node_base::parent_, RB_TREE_BLACK, RB_TREE_RED, rb_tree_rotate_left(), rb_tree_rotate_right() , 以及 rb_tree_node_base::right_.

rb_tree_rotate_left()

NEFORCE_ALWAYS_INLINE_INLINE void rb_tree_rotate_left ( rb_tree_node_base * axis, rb_tree_node_base *& root )

noexcept

红黑树左旋转

参数

axis	旋转轴节点
root	树根节点引用

执行左旋转操作，保持红黑树性质。

在文件 rb_tree.hpp 第 131 行定义.

引用了 rb_tree_node_base::left_, rb_tree_node_base::parent_ , 以及 rb_tree_node_base::right_.

被这些函数引用 rb_tree_erase_rebalance() , 以及 rb_tree_insert_rebalance().

rb_tree_rotate_right()

NEFORCE_ALWAYS_INLINE_INLINE void rb_tree_rotate_right ( rb_tree_node_base * axis, rb_tree_node_base *& root )

noexcept

红黑树右旋转

参数

axis	旋转轴节点
root	树根节点引用

执行右旋转操作，保持红黑树性质。

在文件 rb_tree.hpp 第 159 行定义.

引用了 rb_tree_node_base::left_, rb_tree_node_base::parent_ , 以及 rb_tree_node_base::right_.

被这些函数引用 rb_tree_erase_rebalance() , 以及 rb_tree_insert_rebalance().