本文主要是介绍hello树先生——红黑树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
红黑树
- 一.什么是红黑树
- 二.红黑树的实现
- 1.创建树节点结构
- 2.插入功能的实现
- 三.提供一些常见二叉树接口
- 四.进行平衡测试
一.什么是红黑树
红黑树是一种自平衡的二叉搜索树,具有以下特性:
- 节点颜色:每个节点要么是红色,要么是黑色。
- 根节点:根节点始终是黑色。
- 红色节点:红色节点的子节点不能是红色(即没有两个连续的红色节点)。
- 黑色节点:从任何节点到其每个叶子节点的路径上,必须包含相同数量的黑色节点。
- 叶子节点:所有叶子节点(空节点)都是黑色。
红黑树的这些特性确保了树的高度是对数级别,从而保证了基本操作(如插入、删除和查找)的时间复杂度为O(log n)。这种结构常用于实现关联数组和集合等数据结构。
相较于AVL树,他的高度可能会更高,但由于没有那么多严格旋转操作,所以插入效率会略高
二.红黑树的实现
1.创建树节点结构
由于我们通过树节点的颜色来区分,是否平衡,所以提前定义一下红黑颜色,这里我们使用枚举法定义颜色。
enum color
{RED,BLACK
};
节点结构类似于AVL树,三个指针链接和pair类型数据,唯一加了一个颜色特征,插入节点默认红色。
template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;color _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}};
2.插入功能的实现
bool Insert(const pair<K, V>& kv)
插入分为两种大情况,父亲为黑色或红色,如果黑色那么我们插入新节点就不存在破坏规则,如果是红色,则需要进行调整。
- 如果当前树无节点则,插入根节点
if (_root == nullptr){node* cur = new node(kv);_root = cur;_root->_col = BLACK;return true;}
- 寻找插入位置,并记录父节点位置
//寻找节点node* parent = nullptr;node* cur = _root;while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}
- 构造节点并判断是插在左边还是右边,然后进行链接
cur = new node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;
- 如果父节点存在且为红,则需要调整
while(parent && parent->_col == RED)
{//调整逻辑
}
若插入节点的叔叔节点存在且为红色,那么仅需变色操作,找到parent的parent将其反色,将parent与uncle反色,之后将cur交给祖父,重复操作判断
如图为,父亲是左子树的情况,右子树类似
代码先判断父亲是左还是右子树,从而找到叔叔节点
node* grandparent = parent->_parent;if (grandparent->_left == parent){node* uncle = grandparent->_right;//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续更新判断cur = grandparent;parent = cur->_parent;}//叔叔不存在或者为黑else{//下方继续讲解} }
若叔叔不存在或存在且为黑,则分为两种子情况,类似与AVL树的左左高和左右高形状
1.左左高,即插入节点在左侧
首先将其进行祖父为旋转点旋转,之后将父亲和祖父颜色反转
if (parent->_left == cur){//左插// g// p u// curRotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}
2.左右高,将其旋转两次,parent左旋,grandparent右旋
然后将祖父和cur进行变色
//右插// g// p u// curRotateL(parent);RotateR(grandparent);grandparent->_col = RED;cur->_col = BLACK;
叔叔是黑色或不存在的情况,进行调整后直接跳出break就好
父亲是右子树完全类似,下面不在讲解,提供代码供参考
else{node* uncle = grandparent->_left;//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续更新判断cur = grandparent;parent = cur->_parent;}//叔叔不存在或者为黑else{if (parent->_right == cur){//右插// g// u p// curRotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{//右插// g// u p// curRotateR(parent);RotateL(grandparent);grandparent->_col = RED;cur->_col = BLACK;}break;}}
最后将根节点统一变为黑色,并返回true
_root->_col = BLACK;return true;
如何旋转在AVL树中详细讲解过
三.提供一些常见二叉树接口
求高度,数量,和中序遍历
int height(){return _height(_root);}int size(){return _size(_root);}void InOrder(){_InOrder(_root);cout << endl;}
void _InOrder(node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " " << root->_kv.second << endl;_InOrder(root->_right);}int _height(node* root){if (root == nullptr){return 0;}return max(_height(root->_left), _height(root->_right)) + 1;}int _size(node* root){if (root == nullptr){return 0;}return root == nullptr ? 0 : _size(root->_left) + _size(root->_right) + 1;}
四.进行平衡测试
主要测试这颗红黑树是否符合
- 根节点为黑色
- 每条路径黑色节点数量相同
- 不能连续两个红色节点出现
这里我们采取从根节点向下递归,加入两个参数,记录任意一条路径下的黑色节点数量,和一个count统计当前路径下黑色节点的数目
bool IsBalance(){if (_root->_col == RED){return false;}int refNum = 0;node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}bool Check(node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}
然后我们随机产生一些随机数测试一番,顺便记录各功能效率
void test2()
{RBTree<int, int> a;srand((unsigned int)time(0));int N = 1000000;size_t ret1 = clock();for (int i = 0; i < N; i++){int num = rand() + i;a.Insert({ num,num });}size_t ret2 = clock();cout << "insert->time : " << ret2 - ret1 << endl;size_t ret3 = clock();for (int i = 0; i < N; i++){int num = rand() + i;a.find(num);}size_t ret4 = clock();cout << "insert->time : " << ret2 - ret1 << endl;cout << "find->time : " << ret4 - ret3 << endl;cout << "size-> " << a.size() << endl;cout << "height-> " << a.height() << endl;cout << a.IsBalance() << endl;
}
这篇关于hello树先生——红黑树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!