红黑树模拟实现

文章目录

• 前言
• 红黑树的性质
• 红黑树节点的定义
• 红黑树的旋转
• • 单旋
  • 双旋
• 红黑树的插入
• 红黑树的验证
• 红黑树的性能
• RBTree与AVLTree的比较
• 红黑树的模拟实现

前言

红黑树是一种自平衡的二叉查找树，它在1972年由鲁道夫·贝尔发明，被称为“对称二叉B树”。它通过为每个节点增加一个存储位表示节点的颜色（红色或黑色），并通过对任何一条从根到叶子的路径上各节点的颜色约束，确保树的高度近似平衡（最长路径不超过最短路径的两倍），从而保证查找、插入、删除操作的时间复杂度为 O(log n)。

红黑树的性质

一棵合法的红黑树必须满足以下几个条件

这些性质保证了红黑树的关键特性：从根到叶子的最长路径不会超过最短路径的两倍。 原因是最短路径全是黑色节点，最长路径是红黑相间，由于红色不能连续，且黑色节点数相同，所以最长路径最多比最短路径多一倍红色节点。

红黑树节点的定义

enum Color //节点的颜色种类
{
RED,
BLACK
};
template <class K, class V>
struct RBTreeNode
{
std::pair<K,V> _kv;// 键值对
Color _col; // 节点颜色
RBTreeNode<K, V>* _left;// 左孩子
RBTreeNode<K, V>* _right;// 右孩子
RBTreeNode<K, V>* _parent;// 父节点

RBTreeNode(const pair<K, V>& kv, Color col = RED) // 节点颜色默认为红色
{
_kv = kv;
_col = col;
_left = _right = _parent = nullptr;
}
};

_parent 指针使得我们可以在插入或删除节点后，从当前节点向上回溯，依次更新祖先节点的颜色，直到根节点或节点颜色不违反规则为止

红黑树的旋转

红黑树的旋转与AVL树相比较为容易

单旋

右单旋为例：

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* grandfather = parent->_parent;

subL->_right = parent;
subL->_parent = grandfather;
if (grandfather == nullptr)
{
_root = subL;
}
else if (grandfather != nullptr)
{
if (parent == grandfather->_left)
grandfather->_left = subL;
else
grandfather->_right = subL;
}
parent->_left = subLR;
parent->_parent = subL;
if (subLR)
subLR->_parent = parent;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* grandfather = parent->_parent;

subR->_left = parent;
subR->_parent = grandfather;
parent->_right = subRL;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (grandfather == nullptr)
_root = subR;
else
{
if (parent == grandfather->_left)
grandfather->_left = subR;
else
grandfather->_right = subR;
}
}

双旋

左右双旋为例：

void RotateRL(Node* parent)
{
Node* subR = parent->_right;
RotateR(subR);
RotateL(parent);
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
RotateL(subL);
RotateR(parent);
}

红黑树的插入

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

• 树为空，则直接新增节点，赋值给root指针
• 树不为空，按照二叉搜索的树规则插入新节点
• 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其父节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的父节点颜色为红色时，就违反了性质：不能有连续的红色节点，此时需要对红黑树分情况来讨论：

bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv, BLACK);
return true;
}
//找到插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
//与父亲连接
if (cur->_kv.first > parent->_kv.first)
{
cur->_parent = parent;
parent->_right = cur;
}
else if(cur->_kv.first < parent->_kv.first)
{
cur->_parent = parent;
parent->_left = cur;
}
//向上更新颜色
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
Node* uncle = nullptr;
if (grandfather == nullptr)
break;
if (parent == grandfather->_left)
{
uncle = grandfather->_right;
//情况一：uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

cur = grandfather;
parent = cur->_parent;
}

else if (uncle == nullptr || (uncle && uncle->_col == BLACK))
{
//情况二：uncle不存在或uncle存在且为黑–单旋 旋转+变色
if (cur == parent->_left)
{
RotateR(grandfather);

parent->_col = BLACK;
grandfather->_col = RED;
}
//情况三：uncle不存在或uncle存在且为黑–双旋 旋转+变色
else if (cur == parent->_right)
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else if (parent == grandfather->_right)
{
uncle = grandfather->_left;
//情况一：uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
//情况二、三：uncle不存在或uncle存在且为黑
else if (!uncle || (uncle && uncle->_col == BLACK))
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else if (cur == parent->_left)
{
RotateRL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}

红黑树的验证

void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}

bool IsRBTree()
{
if (_root && _root->_col == RED)
return false;
//先找到一条路径，将其中黑色节点的数量作为基准值
int BasicNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
BasicNum++;
cur = cur->_left;
}
return Check(_root, 0, BasicNum);
}
bool Check(Node* root, int blackNum, int BasicNum)
{
if (root == nullptr)
{
//cout << "该路径黑色节点数量：" << blackNum << endl;
if (blackNum != BasicNum)
{
cout << "该路径黑色节点数量与基准值不符，blackNum: " << blackNum << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
return false;
}
if (root->_col == BLACK)
blackNum++;
bool leftbool = Check(root->_left, blackNum, BasicNum);
bool rightbool = Check(root->_right, blackNum, BasicNum);
return leftbool && rightbool;
}

红黑树的性能

红黑树是一种弱平衡的二叉查找树，通过颜色约束实现近似平衡，在动态操作频繁的场景下具有很好的性能表现。其实现虽然复杂，但因其良好的实际性能，成为许多编程语言标准库中关联容器的首选底层数据结构。

RBTree与AVLTree的比较

红黑树的模拟实现

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

enum Color
{
RED,
BLACK
};
template <class K, class V>
struct RBTreeNode
{
std::pair<K,V> _kv;
Color _col; //节点颜色

RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;

RBTreeNode(const pair<K, V>& kv, Color col = RED)
{
_kv = kv;
_col = col;
_left = _right = _parent = nullptr;
}
};

template <class K, class V>
class RBTree
{
using Node = RBTreeNode<K, V>;
private:
Node* Copy(Node* root, Node* parent = nullptr)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->_kv);
newnode->_parent = parent;
newnode->_left = Copy(root->_left, newnode);
newnode->_right = Copy(root->_right, newnode);
return newnode;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
public:
RBTree() = default;
RBTree(const RBTree<K, V>& tree)
{
_root = Copy(tree._root);
}
~RBTree()
{
Destroy(_root);
}
RBTree<K, V>& operator=(RBTree<K, V> tree)
{
swap(_root, tree._root);
return *this;
}
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv, BLACK);
return true;
}
//找到插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
//与父亲连接
if (cur->_kv.first > parent->_kv.first)
{
cur->_parent = parent;
parent->_right = cur;
}
else if(cur->_kv.first < parent->_kv.first)
{
cur->_parent = parent;
parent->_left = cur;
}
//判断颜色
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
Node* uncle = nullptr;
if (grandfather == nullptr)
break;
if (parent == grandfather->_left)
{
uncle = grandfather->_right;
//情况一：uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

cur = grandfather;
parent = cur->_parent;
}
//情况二：uncle不存在或uncle存在且为黑 旋转+变色
else if (uncle == nullptr || (uncle && uncle->_col == BLACK))
{
//单旋
if (cur == parent->_left)
{
RotateR(grandfather);

parent->_col = BLACK;
grandfather->_col = RED;
}
//双旋
else if (cur == parent->_right)
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else if (parent == grandfather->_right)
{
uncle = grandfather->_left;
//情况一：uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
//情况二：uncle不存在或uncle存在且为黑
else if (!uncle || (uncle && uncle->_col == BLACK))
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else if (cur == parent->_left)
{
RotateRL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}

Node* find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (val > cur->_kv.first)
{
cur = cur->_right;
}
else if (val < cur->_kv.first)
{
cur = cur->_left;
}
else if (val == cur->_kv.first)
{
return cur;
}
}
return nullptr;
}
int height()
{
return _height(_root);
}
int size()
{
return _size(_root);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsRBTree()
{
if (_root && _root->_col == RED)
return false;
//先找到一条路径，将其中黑色节点的数量作为基准值
int BasicNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
BasicNum++;
cur = cur->_left;
}
return Check(_root, 0, BasicNum);
}
private:
bool Check(Node* root, int blackNum, int BasicNum)
{
if (root == nullptr)
{
//cout << "该路径黑色节点数量：" << blackNum << endl;
if (blackNum != BasicNum)
{
cout << "该路径黑色节点数量与基准值不符，blackNum: " << blackNum << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
return false;
}
if (root->_col == BLACK)
blackNum++;
bool leftbool = Check(root->_left, blackNum, BasicNum);
bool rightbool = Check(root->_right, blackNum, BasicNum);
return leftbool && rightbool;
}
int _height(Node* root)
{
if (root == nullptr)
return 0;
int left_height = _height(root->_left);
int right_height = _height(root->_right);

return max(left_height, right_height) + 1;
}
int _size(Node* root)
{
if (root == nullptr)
return 0;

int left_size = _size(root->_left);
int right_size = _size(root->_right);

return left_size + right_size + 1;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* grandfather = parent->_parent;

subL->_right = parent;
subL->_parent = grandfather;
if (grandfather == nullptr)
{
_root = subL;
}
else if (grandfather != nullptr)
{
if (parent == grandfather->_left)
grandfather->_left = subL;
else
grandfather->_right = subL;
}
parent->_left = subLR;
parent->_parent = subL;
if (subLR)
subLR->_parent = parent;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* grandfather = parent->_parent;

subR->_left = parent;
subR->_parent = grandfather;
parent->_right = subRL;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (grandfather == nullptr)
_root = subR;
else
{
if (parent == grandfather->_left)
grandfather->_left = subR;
else
grandfather->_right = subR;
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
RotateR(subR);
RotateL(parent);
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
RotateL(subL);
RotateR(parent);
}
private:
Node* _root = nullptr;
};
void testRBTree1()
{
RBTree<int, int> t;
int a[] = { 16,3,7,11,9,26,18,14,15 }; //测试双旋
int b[] = { 4,2,6,1,3,5,15,7,16,14 }; //测试单旋
for (auto e : b)
{
t.insert({ e,e });
if (e == 9)
int i = 0;
}
t.InOrder();
cout << "size: " << t.size() << " height: " << t.height() << endl;
cout << t.IsRBTree() << endl;
RBTree<int, int> t2(t);
t2.insert({ 20,20 });
t2.insert({ 13,13 });
t2.insert({ 21,21 });
t2.insert({ 8,8 });
t2.InOrder();

}
void testRBTree2()
{
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand(time(0));
size_t begin2 = clock();
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
size_t end1 = clock();
RBTree<int, int> t;
for (auto e : v)
{
t.insert(make_pair(e, e));
}
size_t end2 = clock();

cout << "插入时间：" << end2 – end1 << "ms" << endl;
cout << "Height:" << t.height() << endl;
cout << "Size:" << t.size() << endl;
}