当前位置：首页 > web >正文

红黑树：高效平衡的秘密

web 2025/7/3 16:38:52

红黑树的概念

红黑树，是一种二叉搜索树，在每个结点上增加一个存储位表示结点的颜色，可以是Red，或者Black。通过任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树保证没有一条路径的长度会是其他路径的两倍，因此它是接近平衡的。

红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个结点是红色的，那么他的两个孩子结点是黑色的
对于每个结点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的（这里的叶子节点指的是空结点）

红黑树结点的定义

enum Color
{RED,BALCK,
};template <class K, class V>
struct RBTreeNode
{RBTreeNode<K, V> *_left;RBTreeNode<K, V> *_right;RBTreeNode<K, V> *_parent;Color _col;std::pair<K, V> _kv;
};

红黑树的插入操作

红黑树在二叉搜索树的基础上加上平衡限制条件，因此红黑树插入可以分为两步

1. 按照二叉搜索树的规则插入新节点

bool Insert(const std::pair<K, V> &kv){Node *cur = _root;Node *parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);// 新增的结点统一给红色cur->_col = RED;if (parent == nullptr){_root = cur;_root->_col = BALCK;return true;}if (parent->_kv.first < kv.first){parent->_right = cur;}elseparent->_left = cur;cur->_parent = parent;return true;}

2. 检测新结点插入后，红黑树的性质是否收到破坏，并恢复。

首先需要知道插入的新的结点的默认颜色一定是红色。

如果是黑色的话，一定会破坏掉第4条规则，这条规则是难以直接处理的。相反，如果是红色的话，可能会破坏第3条规则，这个相对而言更好处理。

所以新节点的默认颜色都是红色，因此：如果双清节点的颜色是黑色，则没有违反红黑树的任何规则，不需要进行调整：如果双亲结点是红色的话，违反了第3条规则，此时需要进行分类讨论进行调整：

情况一：cur为红，p为红，g为黑，u存在并且为红

这种情况只需要进行变色即可，就像这样，把grandfather的颜色变成红色，parent和uncle的颜色变成黑色

解决方法：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑

解决方法：右旋+p变黑，g变红

情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑

解决办法：同AVL树的旋转操作，可以转换成情况二进行解决。

完整代码

#pragma once
#include <iostream>enum Color
{RED,BLACK,
};template <class K, class V>
struct RBTreeNode
{RBTreeNode<K, V> *_left;RBTreeNode<K, V> *_right;RBTreeNode<K, V> *_parent;Color _col;std::pair<K, V> _kv;RBTreeNode(const std::pair<K, V> &kv) : _left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}
};template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public:bool Insert(const std::pair<K, V> &kv){Node *cur = _root;Node *parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);// 新增的结点统一给红色cur->_col = RED;if (parent == nullptr){_root = cur;_root->_col = BLACK;return true;}if (parent->_kv.first < kv.first){parent->_right = cur;}elseparent->_left = cur;cur->_parent = parent;// parent的颜色是黑色，也就结束了while (parent && parent->_col == RED){// 这个爷爷结点必然是黑色的Node *grandfather = parent->_parent;if (parent == grandfather->_left){Node *uncle = grandfather->_right;// 如果叔叔存在并且是红色，只需要变色就可以了if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{// 叔叔不存在或者为黑色// 旋转加变色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;parent->_col = grandfather->_col = RED;}break;}}else{Node *uncle = grandfather->_left;// 如果叔叔存在并且是红色，只需要变色就可以了if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{// uncle不存在或者是黑色if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;parent->_col = grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}private:// 右旋void RotateR(Node *parent){Node *subL = parent->_left;Node *subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node *ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{subL->_parent = ppNode;if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}}}// 左旋void RotateL(Node *parent){Node *subR = parent->_right;Node *subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node *ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{subR->_parent = ppNode;if (parent == ppNode->_left)ppNode->_left = subR;elseppNode->_right = subR;}}private:Node *_root = nullptr;size_t _size = 0;
};

查看全文

http://www.xdnf.cn/news/14879.html