柚子快报激活码778899分享：【C++ RB树】
文章目录
红黑树红黑树的概念红黑树的性质红黑树节点的定义红黑树的插入代码实现总结
红黑树
AVL树是一颗绝对平衡的二叉搜索树，要求每个节点的左右高度差的绝对值不超过1，这样保证查询时的高效时间复杂度O(
l
o
g
2
N
)
log_2 N)
log2N)，但是要维护其绝对平衡，旋转的次数比较多。因此，如果一颗树的结构经常修改，那么AVL树就不太合适，所以就有了红黑树。
红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
红黑树的性质
每个节点不是红色就是黑色根节点是黑色的不存在连续的红色节点任意一条从根到叶子的路径上的黑色节点的数量相同 根据上面的性质，红黑树就可以确保没有一条路径会比其他路径长出两倍，因为每条路径上的黑色节点的数量相同，所以理论上最短边一定都是黑色节点，最长边一定是一黑一红的不断重复的路径。
红黑树节点的定义
enum Color
{
RED,
BLACK
};
template
struct RBTreeNode
{
RBTreeNode
RBTreeNode
RBTreeNode
Color _col;
pair
RBTreeNode(const pair
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_kv(kv)
{}
};
插入新节点的颜色一定是红色，因为如果新节点的颜色是黑色，那么每条路径上的黑色节点的数量就不相同了，处理起来就比较麻烦，所以宁愿出现连续的红色节点，也不能让某一条路径上多出一个黑色节点。
红黑树的插入
1.根据二叉搜索树的规则插入新节点
bool Insert(const pair
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* curr = _root;
Node* parent = nullptr;
while (curr)
{
if (curr->_kv.first < kv.first)
{
parent = curr;
curr = curr->_right;
}
else if (curr->_kv.first > kv.first)
{
parent = curr;
curr = curr->_left;
}
else
{
return false;
}
}
curr = new Node(kv);
if (parent->_kv.first < kv.first)
parent->_right = curr;
else
parent->_left = curr;
curr->_parent = parent;
........
2.测新节点插入后，红黑树的性质是否造到破坏
bool Insert(const pair
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* curr = _root;
Node* parent = nullptr;
while (curr)
{
if (curr->_kv.first < kv.first)
{
parent = curr;
curr = curr->_right;
}
else if (curr->_kv.first > kv.first)
{
parent = curr;
curr = curr->_left;
}
else
{
return false;
}
}
curr = new Node(kv);
if (parent->_kv.first < kv.first)
parent->_right = curr;
else
parent->_left = curr;
curr->_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;
curr = grandfather;
parent = curr->_parent;
}
else
{
if (curr == parent->_left)
{
// g
// p u
//c
RotatoR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
RotatoL(parent);
RotatoR(grandfather);
curr->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
curr = grandfather;
parent = curr->_parent;
}
else
{
if (curr == parent->_right)
{
// g
// u p
// c
RotatoL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotatoR(parent);
RotatoL(grandfather);
curr->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void RotatoL(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;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
ppnode->_left = subR;
else
ppnode->_right = subR;
subR->_parent = ppnode;
}
}
void RotatoR(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;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
ppnode->_left = subL;
else
ppnode->_right = subL;
subL->_parent = ppnode;
}
}
代码实现
#pragma once
#include
namespace lw
{
enum Color
{
RED,
BLACK
};
template
struct RBTreeNode
{
RBTreeNode
RBTreeNode
RBTreeNode
Color _col;
pair
RBTreeNode(const pair
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_kv(kv)
{}
};
template
class RBTree
{
typedef RBTreeNode
public:
bool Insert(const pair
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* curr = _root;
Node* parent = nullptr;
while (curr)
{
if (curr->_kv.first < kv.first)
{
parent = curr;
curr = curr->_right;
}
else if (curr->_kv.first > kv.first)
{
parent = curr;
curr = curr->_left;
}
else
{
return false;
}
}
curr = new Node(kv);
if (parent->_kv.first < kv.first)
parent->_right = curr;
else
parent->_left = curr;
curr->_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;
curr = grandfather;
parent = curr->_parent;
}
else
{
if (curr == parent->_left)
{
// g
// p u
//c
RotatoR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
RotatoL(parent);
RotatoR(grandfather);
curr->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
curr = grandfather;
parent = curr->_parent;
}
else
{
if (curr == parent->_right)
{
// g
// u p
// c
RotatoL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotatoR(parent);
RotatoL(grandfather);
curr->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void RotatoL(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;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
ppnode->_left = subR;
else
ppnode->_right = subR;
subR->_parent = ppnode;
}
}
void RotatoR(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;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
ppnode->_left = subL;
else
ppnode->_right = subL;
subL->_parent = ppnode;
}
}
void InOrder()
{
_InOrder(_root);
}
bool IsBalance()
{
if (_root && _root->_col == RED)
return false;
Node* left = _root;
int count = 0;
while (left)
{
if (left->_col == BLACK)
count++;
left = left->_left;
}
return check(_root, 0, count);
}
private:
bool check(Node* root, int count, int refBlackNumber)
{
if (root == nullptr)
{
if (count == refBlackNumber)
return true;
else
return false;
}
if (root->_col == RED && root->_parent->_col == RED)
return false;
if (root->_col == BLACK)
count++;
return check(root->_left, count, refBlackNumber)
&& check(root->_right, count, refBlackNumber);
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " : " << root->_kv.second << endl;
_InOrder(root->_right);
}
Node* _root = nullptr;
};
}
总结
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(
l
o
g
2
N
log_2 N
log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
柚子快报激活码778899分享：【C++ RB树】
文章来源
发表评论