一、红黑树的概念
红黑树是一棵自平衡二叉搜索树,它的每个结点增加一个存储位来表示结点的颜色,可以是红色或者黑色。
与 AVL 树追求'严格平衡'不同,红黑树 允许一定程度的不平衡。AVL 树通过'平衡因子'维持平衡,而红黑树通过给节点 着色(红色或黑色)来确保高效性。在保证增删改查效率没有太大影响的前提下,显著减少了平衡调整(旋转)的次数,从而提升总体效率。红黑树的性质如下:
节点颜色:每个节点要么是红色,要么是黑色。根节点:根节点必须是黑色。叶子节点:所有叶子节点(即 NULL 节点/空指针)均为黑色。红色约束:如果一个节点是红色,则其子节点必须是黑色。**路径上不能有连续的红色节点。**黑色高度:从根节点到任意 NULL 节点的所有路径上,黑色节点的数量都相同。
红黑树最长路径不超过最短路径的两倍


二、红黑树节点的定义
红黑树节点定义如下,采用三叉链结构,并添加一个变量表示节点颜色。
enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
// 三叉链
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
// 存储的键值对
pair<K, V> _kv;
// 结点的颜色
int _col; // 红/黑
// 构造函数
RBTreeNode(const pair<K, V>& kv) :_left(nullptr), _right(nullptr), _parent(), _kv(kv), _col(RED) {}
};










