第一篇 数据结构学习之红黑树的实现
系列文章目录
第一篇 数据结构学习之红黑树的实现
前言
红黑树是一种平衡二叉搜索树，在插入和删除时可以通过调整节点的颜色和旋转操作来维持平衡。它广泛应用于各种数据结构中，比如 STL 中的 map 和 set，因为它能确保查找、插入和删除的时间复杂度为 O(logn)。本文将详细介绍红黑树的特点，并通过 C++ 实现插入、删除及测试代码。
一、红黑树的基本概念
红黑树是一种自平衡的二叉查找树，具有以下特性：
1，每个节点都是红色或黑色。
2，根节点是黑色。
3，每个叶节点（NIL节点）是黑色。
4，如果一个节点是红色的，则它的两个子节点都是黑色的（红色节点不能连续）。
5，从任一节点到其每个叶节点的所有路径都包含相同数量的黑色节点。
这些特性确保红黑树在最坏情况下仍然具有较低的高度，从而使得查找、插入和删除操作都可以在 O(logn) 时间内完成。
二、参考视频链接
三、代码实现
1. 定义节点类
在 C++ 中，我们首先定义一个节点类，包括颜色、值、左孩子、右孩子和父节点指针。
enum Colour
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
typedef RBTreeNode<K, V> Node;
Node* _left;
Node* _right;
Node* _parent;
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)//插入结点默认是红色(插入黑色必然违反规则)
{
}
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
Node* _root = nullptr;
};
2.旋转方法
包括左旋，右旋，左右双旋，右左双旋
//右旋
void RotateR(Node* parent)
{
rotal++;
Node* Lnode = parent->_left;
Node* LRnode = Lnode->_right;
Node* ppnode = parent->_parent;
parent->_left = LRnode;
if (LRnode) LRnode->_parent = parent;
Lnode->_right = parent;
parent->_parent = Lnode;
if (parent == _root)
{
_root = Lnode;
}
else if (ppnode->_left == parent)
{
ppnode->_left = Lnode;
}
else
{
ppnode->_right = Lnode;
}
Lnode->_parent = ppnode;
}
//左旋
void RotateL(Node* parent)
{
rotal++;
Node* Rnode = parent->_right;
Node* RLnode = Rnode->_left;
Node* ppnode = parent->_parent;
parent->_right = RLnode;
if (RLnode) RLnode->_parent = parent;
Rnode->_left = parent;
parent->_parent = Rnode;
if (parent == _root)
{
_root = Rnode;
}
else if (ppnode->_left == parent)
{
ppnode->_left = Rnode;
}
else
{
ppnode->_right = Rnode;
}
Rnode->_parent = ppnode;
}
//左右双旋
void RotateLR(Node* parent)
{
Node* Lnode = parent->_left;
RotateL(Lnode);
RotateR(parent);
}
//右左双旋
void RotateRL(Node* parent)
{
Node* Rnode = parent->_right;
RotateR(Rnode);
RotateL(parent);
}
3.红黑树插入操作
红黑树的插入操作需要确保树的平衡性，通过着色和旋转来维护红黑树的性质。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
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;
}
}
Node* newnode = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = newnode;
newnode->_parent = parent;
}
else
{
parent->_left = newnode;
newnode->_parent = parent;
}
//调整红黑树的颜色
//父亲为红色,出现连续的红色节点,需要调整
while (parent&&parent->_col == RED)
{
Node* grandparent = parent->_parent;
Node* uncle = nullptr;
if (parent == grandparent->_left)
uncle = grandparent->_right;
else
uncle = grandparent->_left;
//uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上处理
newnode = grandparent;
parent = newnode->_parent;
}
//uncle不存在或者存在且为黑
//旋转+变色
else if (uncle == nullptr || uncle->_col == BLACK)
{
//右旋
if (parent == grandparent->_left && newnode == parent->_left)
{
//右旋
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
//左旋
else if (parent == grandparent->_right && newnode == parent->_right)
{
//左旋
RotateL(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
//左右双旋
else if (parent == grandparent->_left && newnode == parent->_right)
{
//左右双旋
RotateLR(grandparent);
newnode->_col = BLACK;
grandparent->_col = RED;
break;//这里parent还是红,需要直接break;
}
//右左双旋
else if (parent == grandparent->_right && newnode == parent->_left)
{
//右左双旋
RotateRL(grandparent);
newnode->_col = BLACK;
grandparent->_col = RED;
break;//这里parent还是红,需要直接break;
}
else
{
assert(false);
}
break;
}
}
//父亲为黑就结束
//根必须为黑
_root->_col = BLACK;
return true;
}
4.红黑树删除操作
删除操作是红黑树中最复杂的操作之一。删除后必须确保树的平衡性，同样通过重新着色和旋转来维持红黑树的性质。
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
parent = cur;
cur = cur->_right;
}
else
{
Node* del = cur;
//找到了开始删除
//左右子树都不为空
if(cur->_left!=nullptr&&cur->_right != nullptr)
{
//替换最右子树的最左节点删除
Node* tmp = cur;
parent = cur;
cur = cur->_right;
while (cur->_left)
{
parent = cur;
cur = cur->_left;
}
tmp->_kv = cur->_kv;
del = cur;
}
//左子树为空
//代替后变黑即可
if (cur->_left == nullptr && cur->_right != nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
cur->_right->_parent = parent;
cur->_right->_col = BLACK;
break;
}
//右子树为空
//代替后变黑即可
else if (cur->_right == nullptr && cur->_left != nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
cur->_left->_parent = parent;
cur->_left->_col = BLACK;
break;
}
//左右都为空
else if (cur->_right == nullptr && cur->_left == nullptr)
{
if (cur == _root)
{
//根结点
_root = nullptr;
break;
}
//cur颜色为红色,删完就可以结束
if (cur->_col == RED)
{
if (cur == parent->_left)
{
parent->_left = nullptr;
}
else
{
parent->_right = nullptr;
}
break;
}
else
{
//cur的颜色为黑色
//看兄弟的颜色
Node* sister = nullptr;
while (true)
{
if (cur == parent->_left)
{
sister = parent->_right;
}
else if(cur == parent->_right)
{
sister = parent->_left;
}
//兄弟为黑色
if (sister->_col == BLACK)
{
if ((sister->_left == nullptr && sister->_right == nullptr) || ((sister->_left && sister->_left->_col == BLACK) && (sister->_right && sister->_right->_col == BLACK)))
{
sister->_col = RED;
if (del == parent->_left)
{
parent->_left = nullptr;
}
else if (del == parent->_right)
{
parent->_right = nullptr;
}
cur = parent;
parent = parent->_parent;
if (cur->_col == RED)
{
cur->_col = BLACK;
break;
}
else if (cur == _root)
{
cur->_col = BLACK;
break;
}
}
else if (sister == parent->_left && sister->_left && sister->_left->_col == RED)
{
//变色+右旋
if (parent->_right == del)
parent->_right = nullptr;
sister->_left->_col = sister->_col;
sister->_col = parent->_col;
parent->_col = BLACK;
RotateR(parent);
break;
}
else if (sister == parent->_left && sister->_right && sister->_right->_col == RED)
{
//变色+左右双旋
if (parent->_right == del)
parent->_right = nullptr;
sister->_right->_col = parent->_col;
parent->_col = BLACK;
RotateLR(parent);
break;
}
else if (sister == parent->_right && sister->_right && sister->_right->_col == RED)
{
//变色+左旋
if (parent->_left == del)
parent->_left = nullptr;
sister->_right->_col = sister->_col;
sister->_col = parent->_col;
parent->_col = BLACK;
RotateL(parent);
break;
}
else if (sister == parent->_right && sister->_left && sister->_left->_col == RED)
{
//变色+右左双旋
if (parent->_left == del)
parent->_left = nullptr;
sister->_left->_col = parent->_col;
parent->_col = BLACK;
RotateRL(parent);
break;
}
else
{
cout << (sister == parent->_right) << endl;
cout << (sister == parent->_left) << endl;
cout << (sister->_left == nullptr) << endl;
cout << (sister->_right == nullptr) << endl;
cout << (sister->_right->_col == RED) << endl;
cout << (sister->_right->_col == RED) << endl;
assert(false);
}
}
//兄弟为红色
else
{
//兄父变色,朝双黑旋转
//保持双黑,继续调整
sister->_col = BLACK;
parent->_col = RED;
if (cur == parent->_left)
{
if (parent->_left == del)
parent->_left = nullptr;
RotateL(parent);
sister = parent->_right;
}
else if (cur == parent->_right)
{
if (parent->_right == del)
parent->_right = nullptr;
RotateR(parent);
sister = parent->_left;
}
}
}
}
}
delete del;
return true;
}
}
return false;
}
四，总体代码
这里将自己写删除的一步一步尝试保留，让自己也能够在后面能够知道
#pragma once
#include <assert.h>
#include <vector>
//根是黑的
//没有连续的红色节点
//每条路径的黑色节点的数量相等
//首先插入的节点默认为红
//父亲是黑色就结束
//父亲是红则看uncle
//uncle为红,p/u变黑,g变红,g如果为根,g变黑,g不是根,向上继续(c = g)
//uncle不在/uncle在是黑,p在g的左,p的左边插入,右单旋,p变黑,g变红
//uncle不在/uncle在是黑,p在g的左,p的右边插入,左右双旋,c变黑,g变红
//uncle不在/uncle在是黑,p在g的右,p的右边插入,左单旋,p变黑,g变红
//uncle不在/uncle在是黑,p在g的右,p的左边插入,右左双旋,c变黑,g变红
//删除
//只有左/右子树-》代替后变黑就结束（这种情况只能一黑(根)一红(子))
//没有孩子
//如果cur是红节点-》直接删除结束
//如果cur是黑结点-》看兄弟结点
// 兄弟节点是黑色
// 至少一个红孩子->兄弟在父亲左边,兄弟左边有红色节点(兄弟右边有(两个孩子都是红色)也是这个情况) LL形 兄弟->left->col = 兄弟->col 兄弟->col =p->col p->col=黑色 右旋 删除节点 结束
// 兄弟在父亲右边,兄弟右边有红色节点(兄弟左边有(两个孩子都是红色)也是这个情况) RR形 兄弟->right->col = 兄弟->col 兄弟->col =p->col p->col=黑色 左旋 删除节点 结束
// 兄弟在父亲左边,兄弟右边有红色节点 LR形 兄弟->right->col =p->col p->col=黑色 左右双旋 删除节点 结束
// 兄弟在父亲右边,兄弟左边有红色节点 RL形 兄弟->right->col =p->col p->col=黑色 右左双旋 删除节点 结束
// 孩子都是黑的(包括孩子都是nullptr)->兄弟变红,(记得删除节点)双黑节点上移(c=p)->继续处理双黑节点,这里不能再进入到只有一个孩子的情况(如果c->col ==红色),c->col变黑就结束,如果c是根,c变黑就结束
//兄弟节点是红色->兄弟和父亲都变色,然后父亲向着双黑节点方向旋转,新的兄弟节点变成新的双黑节点的兄弟(删除双黑节点),继续处理新的兄弟节点,不能走到只有一个孩子的情况
enum Colour
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
typedef RBTreeNode<K, V> Node;
Node* _left;
Node* _right;
Node* _parent;
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)//插入结点默认是红色(插入黑色必然违反规则)
{
}
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
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;
}
}
Node* newnode = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = newnode;
newnode->_parent = parent;
}
else
{
parent->_left = newnode;
newnode->_parent = parent;
}
//调整红黑树的颜色
//父亲为红色,出现连续的红色节点,需要调整
while (parent&&parent->_col == RED)
{
Node* grandparent = parent->_parent;
Node* uncle = nullptr;
if (parent == grandparent->_left)
uncle = grandparent->_right;
else
uncle = grandparent->_left;
//uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上处理
newnode = grandparent;
parent = newnode->_parent;
}
//uncle不存在或者存在且为黑
//旋转+变色
else if (uncle == nullptr || uncle->_col == BLACK)
{
//右旋
if (parent == grandparent->_left && newnode == parent->_left)
{
//右旋
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
//左旋
else if (parent == grandparent->_right && newnode == parent->_right)
{
//左旋
RotateL(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
//左右双旋
else if (parent == grandparent->_left && newnode == parent->_right)
{
//左右双旋
RotateLR(grandparent);
newnode->_col = BLACK;
grandparent->_col = RED;
break;//这里parent还是红,需要直接break;
}
//右左双旋
else if (parent == grandparent->_right && newnode == parent->_left)
{
//右左双旋
RotateRL(grandparent);
newnode->_col = BLACK;
grandparent->_col = RED;
break;//这里parent还是红,需要直接break;
}
else
{
assert(false);
}
break;
}
}
//父亲为黑就结束
//根必须为黑
_root->_col = BLACK;
return true;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
parent = cur;
cur = cur->_right;
}
else
{
Node* del = cur;
//找到了开始删除
//左右子树都不为空
if(cur->_left!=nullptr&&cur->_right != nullptr)
{
//替换最右子树的最左节点删除
Node* tmp = cur;
parent = cur;
cur = cur->_right;
while (cur->_left)
{
parent = cur;
cur = cur->_left;
}
tmp->_kv = cur->_kv;
del = cur;
}
//左子树为空
//代替后变黑即可
if (cur->_left == nullptr && cur->_right != nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
cur->_right->_parent = parent;
cur->_right->_col = BLACK;
break;
}
//右子树为空
//代替后变黑即可
else if (cur->_right == nullptr && cur->_left != nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
cur->_left->_parent = parent;
cur->_left->_col = BLACK;
break;
}
//左右都为空
else if (cur->_right == nullptr && cur->_left == nullptr)
{
if (cur == _root)
{
//根结点
_root = nullptr;
break;
}
//cur颜色为红色,删完就可以结束
if (cur->_col == RED)
{
if (cur == parent->_left)
{
parent->_left = nullptr;
}
else
{
parent->_right = nullptr;
}
break;
}
else
{
//cur的颜色为黑色
//看兄弟的颜色
Node* sister = nullptr;
//if (cur == parent->_left)
//{
// sister = parent->_right;
//}
//else
//{
// sister = parent->_left;
//}
while (true)
{
if (cur == parent->_left)
{
sister = parent->_right;
}
else if(cur == parent->_right)
{
sister = parent->_left;
}
//兄弟为黑色
if (sister->_col == BLACK)
{
if ((sister->_left == nullptr && sister->_right == nullptr) || ((sister->_left && sister->_left->_col == BLACK) && (sister->_right && sister->_right->_col == BLACK)))
{
sister->_col = RED;
if (del == parent->_left)
{
parent->_left = nullptr;
}
else if (del == parent->_right)
{
parent->_right = nullptr;
}
cur = parent;
parent = parent->_parent;
if (cur->_col == RED)
{
cur->_col = BLACK;
break;
}
else if (cur == _root)
{
cur->_col = BLACK;
break;
}
}
else if (sister == parent->_left && sister->_left && sister->_left->_col == RED)
{
//变色+右旋
if (parent->_right == del)
parent->_right = nullptr;
sister->_left->_col = sister->_col;
sister->_col = parent->_col;
parent->_col = BLACK;
RotateR(parent);
break;
}
else if (sister == parent->_left && sister->_right && sister->_right->_col == RED)
{
//变色+左右双旋
if (parent->_right == del)
parent->_right = nullptr;
sister->_right->_col = parent->_col;
parent->_col = BLACK;
RotateLR(parent);
break;
}
else if (sister == parent->_right && sister->_right && sister->_right->_col == RED)
{
//变色+左旋
if (parent->_left == del)
parent->_left = nullptr;
sister->_right->_col = sister->_col;
sister->_col = parent->_col;
parent->_col = BLACK;
RotateL(parent);
break;
}
else if (sister == parent->_right && sister->_left && sister->_left->_col == RED)
{
//变色+右左双旋
if (parent->_left == del)
parent->_left = nullptr;
sister->_left->_col = parent->_col;
parent->_col = BLACK;
RotateRL(parent);
break;
}
else
{
cout << (sister == parent->_right) << endl;
cout << (sister == parent->_left) << endl;
cout << (sister->_left == nullptr) << endl;
cout << (sister->_right == nullptr) << endl;
cout << (sister->_right->_col == RED) << endl;
cout << (sister->_right->_col == RED) << endl;
assert(false);
}
}
//兄弟为红色
else
{
//兄父变色,朝双黑旋转
//保持双黑,继续调整
sister->_col = BLACK;
parent->_col = RED;
if (cur == parent->_left)
{
if (parent->_left == del)
parent->_left = nullptr;
RotateL(parent);
sister = parent->_right;
}
else if (cur == parent->_right)
{
if (parent->_right == del)
parent->_right = nullptr;
RotateR(parent);
sister = parent->_left;
}
//只需要前面判断逻辑设置为cur ==parent->_left//cur == parent->_right 不要写成if else,这里就能省略
//if ((sister->_left == nullptr && sister->_right == nullptr) || ((sister->_left && sister->_left->_col == BLACK) && (sister->_right && sister->_right->_col == BLACK)))
//{
// sister->_col = RED;
// cur = parent;
// parent = parent->_parent;
// if (cur->_col == RED)
// {
// cur->_col = BLACK;
// break;
// }
// else if (cur == _root)
// {
// cur->_col = BLACK;
// break;
// }
//}
//else if (sister == parent->_left && sister->_left && sister->_left->_col == RED)
//{
// //变色+右旋
// sister->_left->_col = sister->_col;
// sister->_col = parent->_col;
// parent->_col = BLACK;
// RotateR(parent);
// break;
//}
//else if (sister == parent->_left && sister->_right && sister->_right->_col == RED)
//{
// //变色+左右双旋
// sister->_right->_col = parent->_col;
// parent->_col = BLACK;
// RotateLR(parent);
// break;
//}
//else if (sister == parent->_right && sister->_right && sister->_right->_col == RED)
//{
// //变色+左旋
// sister->_right->_col = sister->_col;
// sister->_col = parent->_col;
// parent->_col = BLACK;
// RotateL(parent);
// break;
//}
//else if (sister == parent->_right && sister->_left && sister->_left->_col == RED)
//{
// //变色+右左双旋
// sister->_left->_col = parent->_col;
// parent->_col = BLACK;
// RotateRL(parent);
// break;
//}
//else
//{
// cout << (sister == parent->_right) << endl;
// cout << (sister == parent->_left) << endl;
// cout << (sister->_left == nullptr) << endl;
// cout << (sister->_right == nullptr) << endl;
// cout << (sister->_right->_col == RED) << endl;
// cout << (sister->_right->_col == RED) << endl;
// assert(false);
//}
}
}
}
}
delete del;
return true;
}
}
return false;
}
int _red = 0;
int _black = 0;
void InOrder()
{
_InOrder(_root);
}
int Height()
{
return _Height(_root);
}
int size()
{
int count = 0;
_size(_root,count);
return count;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool IsBanlance()
{
//int count = 0;
//return _IsBanlance(_root,count);
//验证根节点为黑色
if (_root && _root->_col == RED)
{
return false;
}
//获取一个标准黑色结点数量
int size = 0;
Node* tmp = _root;
while (tmp)
{
if (tmp->_col == BLACK)
{
size++;
}
tmp = tmp->_left;
}
return check(_root,0,size);
}
int rotal = 0;
private:
//验证没有连续的红节点
//验证每条路径的黑色节点数量都相同
bool check(const Node* root,int num,int&size)
{
if (root == nullptr)
{
if (num != size)
{
cout << "黑色节点数量不相同" << endl;
return false;
}
//cout << size << endl;
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << ":存在连续的红色节点" << endl;
return false;
}
if (root->_col == BLACK)
{
num++;
}
return check(root->_left, num, size) && check(root->_right, num, size);
}
bool _IsBanlance(const Node* root,int& count)
{
if (root == nullptr)
{
return true;
}
int left = 0, right = 0;
if (!_IsBanlance(root->_left, left) || !_IsBanlance(root->_right, right))
{
return false;
}
if (left != right)
{
return false;
}
if (root->_col == BLACK)
{
count = left + 1;
}
else
{
count = left;
}
return true;
}
void _size(const Node* root, int& count)
{
if (root == nullptr)
{
return;
}
_size(root->_left, count);
count++;
_size(root->_right, count);
}
int _Height(const Node* root)
{
if (root == nullptr)
{
return 0;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
return left > right ? left + 1 : right + 1;
}
void _InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
if (root->_col == RED)
_red++;
else if (root->_col == BLACK)
_black++;
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
//右旋
void RotateR(Node* parent)
{
rotal++;
Node* Lnode = parent->_left;
Node* LRnode = Lnode->_right;
Node* ppnode = parent->_parent;
parent->_left = LRnode;
if (LRnode) LRnode->_parent = parent;
Lnode->_right = parent;
parent->_parent = Lnode;
if (parent == _root)
{
_root = Lnode;
}
else if (ppnode->_left == parent)
{
ppnode->_left = Lnode;
}
else
{
ppnode->_right = Lnode;
}
Lnode->_parent = ppnode;
}
//左旋
void RotateL(Node* parent)
{
rotal++;
Node* Rnode = parent->_right;
Node* RLnode = Rnode->_left;
Node* ppnode = parent->_parent;
parent->_right = RLnode;
if (RLnode) RLnode->_parent = parent;
Rnode->_left = parent;
parent->_parent = Rnode;
if (parent == _root)
{
_root = Rnode;
}
else if (ppnode->_left == parent)
{
ppnode->_left = Rnode;
}
else
{
ppnode->_right = Rnode;
}
Rnode->_parent = ppnode;
}
//左右双旋
void RotateLR(Node* parent)
{
Node* Lnode = parent->_left;
RotateL(Lnode);
RotateR(parent);
}
//右左双旋
void RotateRL(Node* parent)
{
Node* Rnode = parent->_right;
RotateR(Rnode);
RotateL(parent);
}
Node* _root = nullptr;
};
总结
这里附带一下测试代码
void test_RBTree1()
{
//int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
RBTree<int, int> rb;
for (auto e : a)
{
rb.Insert(make_pair(e, e));
}
rb.InOrder();
}
void test_RBTree2()
{
const int N = 2500;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back((rand() + i));
}
//for (auto e : v)
//{
// cout << e << " " ;
//}
cout << endl;
size_t begin2 = clock();
RBTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
size_t end2 = clock();
//cout << t.IsBanlance() << endl;
cout << "Insert:" << end2 - begin2 << endl;
cout << "Height:" << t.Height() << endl;
cout << "size:" << t.size() << endl;
size_t begin1 = clock();
int flag = 0;
for (auto e : v)
{
t.Find(e);
t.Erase(e);
//int i = t.IsBanlance();
//if (i == 0)
//{
// flag++;
//}
}
cout << "flag:" << flag << endl;
for (size_t i = 0; i < N; i++)
{
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
cout << "IsBanlance:" << t.IsBanlance() << endl;
}
void test_RBTree3()
{
//int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 16, 3, 7, 11 };
//int a[] = { 15,9,18,6,13,17,27,10,23,34,25,37 };
//int a[] = { 1,80,32,29,15,40,93,43,63,18,57,95,32,96,48,40,87,82,0,62,96,22,26,54,91};
int a[] = { 78,34,52,59,42,73,79,45,90,86,88,95,84,51,77,71,35,55,68,69,47,91,26,3,78};
RBTree<int, int> rb;
for (auto e : a)
{
rb.Insert(make_pair(e, e));
}
//rb.InOrder();
//int b[] = { 18,25,15,6,13,37,27,17,34,9,10,23 };
for (auto e : a)
{
if (e == 95)
{
int i = 10;
}
rb.Erase(e);
}
rb.InOrder();
}
本文详细介绍了红黑树的定义、插入、删除及其在 C++ 中的实现。通过自平衡特性，红黑树确保了较低的时间复杂度，使其在许多应用中成为首选的数据结构，再次感受到发明红黑树的人简直就是天才。
标签：sister,right,cur,parent,C++,插入,红黑树,col,left From： https://blog.csdn.net/2201_75443644/article/details/143393581