本章继AVL树后继续讲解学习C++中另一个二叉搜索树–红黑树
注:AVL树是严格平衡的二叉搜索树,左右子树高度不超过1;红黑树是近似平衡,最长路径不超过最短路径的二倍
红黑树第三条性质说明红黑树不能存在连续(父子相连)的红结点,可以存在连续的黑结点,又由于第四条性质每个路径上的黑结点个数都相同 ,所以对于最短路径来说一定是都是黑色结点,对于最长路径来说一定是黑色红色相间的路径,所以最长路径不超过最短路径长度的二倍
对于红黑树来说以颜色来代替AVL树的平衡因子的作用,除此之外在定义上没有什么区别
enum Colour//颜色
{
RED,
BLACK,
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
注:此处采用枚举来表示,当然也可以使用其他方式
红黑树是在二叉搜索树的基础上加上其平衡限制条件,当违反限制条件时就需要做出相应的调整
注:约定cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
情况一: cur为红,p为红,g为黑,u存在且为红
将p,u改为黑,g改为红,然后把g当成cur,继续向上调整
情况二: cur为红,p为红,g为黑,u不存在**/u**为黑
情况三: cur为红,p为红,g为黑,u不存在**/u**为黑
这里显然一次旋转也无法让达到红黑树平衡,由此就需要进行两次旋转
插入主体实现:
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
//空树的情况
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return make_pair(_root, true);
}
//查找位置插入节点
Node* cur = _root, * parent = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
//创建链接节点
cur = new Node(kv);
Node* newnode = cur;
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//父节点存在且为红,则需要调整(不能存在连续的红色节点)
while (parent && parent->_col == RED)
{
//此时当前节点一定有祖父节点
Node* granparent = parent->_parent;
//具体调整情况主要看叔叔节点
//分左右讨论
if (parent == granparent->_left)
{
Node* uncle = granparent->_right;
//情况1:叔叔节点存在且为红
if (uncle && uncle->_col == RED)
{
//修改颜色,继续向上检查
granparent->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = granparent;
parent = cur->_parent;
}
else//情况2和3:叔叔节点不存在 或者存在且为黑
{
//单旋(三代节点为斜线)+变色
if (cur == parent->_left)
{
RotateR(granparent);
granparent->_col = RED;
parent->_col = BLACK;
}
else//双旋(三代节点为折线)+变色
{
RotateL(parent);
RotateR(granparent);
cur->_col = BLACK;
granparent->_col = RED;
}
//旋转后不需再向上调整了
break;
}
}
else//parent=grandparent->right
{
Node* uncle = granparent->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
granparent->_col = RED;
cur = granparent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(granparent);
parent->_col = BLACK;
granparent->_col = RED;
}
else
{
RotateR(parent);
RotateL(granparent);
cur->_col = BLACK;
granparent->_col = RED;
}
break;
}
}
}
//确保根节点为黑
_root->_col = BLACK;
return make_pair(newnode, true);
}
旋转实现:
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentP = parent->_parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = parentP;
if (parentP->_left == parent)
{
parentP->_left = subR;
}
else
{
parentP->_right = subR;
}
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentP = parent->_parent;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = parentP;
if (parentP->_left == parent)
{
parentP->_left = subL;
}
else
{
parentP->_right = subL;
}
}
}
bool IsRBTree()
{
//空树
if (_root == nullptr)
{
return true;
}
//根节点为黑色
if (_root->_col == RED)
{
cout << "根节点为红色" << endl;
return false;
}
//黑色结点数量各路径上相同
//先走一条得到基准值
int Blacknum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
Blacknum++;
cur = cur->_left;
}
//检查子树
int i = 0;
return _IsRBTree(_root, Blacknum, i);
}
bool _IsRBTree(Node* root, int blacknum, int count)
{
//递归到空节点
if (root == nullptr)
{
if (blacknum == count)
return true;
cout << "各路径上黑色节点个数不同" << endl;
return false;
}
//子节点为红则检查父节点是否为红(通过父节点检查子节点会遇到空节点)
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续红色节点" << endl;
return false;
}
//计数黑结点
if (root->_col == BLACK)
count++;
//递归左右子树
return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
}
红黑树的删除不做讲解,有兴趣可参考:《算法导论》或者《STL源码剖析》 http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html http://blog.csdn.net/chenhuajie123/article/details/11951777
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
//颜色
enum Colour
{
RED,
BLACK,
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _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:
RBTree()
:_root(nullptr)
{
}
void _Destory(Node*& root)
{
if (root == nullptr)
return;
_Destory(root->_left);
_Destory(root->_right);
delete root;
root = nullptr;
}
~RBTree()
{
_Destory(_root);
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
//空树的情况
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return make_pair(_root, true);
}
//查找位置插入节点
Node* cur = _root, * parent = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
//创建链接节点
cur = new Node(kv);
Node* newnode = cur;
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//父节点存在且为红,则需要调整(不能存在连续的红色节点)
while (parent && parent->_col == RED)
{
//此时当前节点一定有祖父节点
Node* granparent = parent->_parent;
//具体调整情况主要看叔叔节点
//分左右讨论
if (parent == granparent->_left)
{
Node* uncle = granparent->_right;
//情况1:叔叔节点存在且为红
if (uncle && uncle->_col == RED)
{
//修改颜色,继续向上检查
granparent->_col = RED;
parent->_col = uncle->_col = BLACK;
cur = granparent;
parent = cur->_parent;
}
else//情况2和3:叔叔节点不存在 或者存在且为黑
{
//单旋(三代节点为斜线)+变色
if (cur == parent->_left)
{
RotateR(granparent);
granparent->_col = RED;
parent->_col = BLACK;
}
else//双旋(三代节点为折线)+变色
{
RotateL(parent);
RotateR(granparent);
cur->_col = BLACK;
granparent->_col = RED;
}
//旋转后不需再向上调整了
break;
}
}
else//parent=grandparent->right
{
Node* uncle = granparent->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
granparent->_col = RED;
cur = granparent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(granparent);
parent->_col = BLACK;
granparent->_col = RED;
}
else
{
RotateR(parent);
RotateL(granparent);
cur->_col = BLACK;
granparent->_col = RED;
}
break;
}
}
}
//确保根节点为黑
_root->_col = BLACK;
return make_pair(newnode, true);
}
bool IsRBTree()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout << "根节点为红色" << endl;
return false;
}
int Blacknum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
Blacknum++;
cur = cur->_left;
}
int i = 0;
return _IsRBTree(_root, Blacknum, i);
}
private:
bool _IsRBTree(Node* root, int blacknum, int count)
{
if (root == nullptr)
{
if (blacknum == count)
return true;
cout << "各路径上黑色节点个数不同" << endl;
return false;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续红色节点" << endl;
return false;
}
if (root->_col == BLACK)
count++;
return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentP = parent->_parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = parentP;
if (parentP->_left == parent)
{
parentP->_left = subR;
}
else
{
parentP->_right = subR;
}
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentP = parent->_parent;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = parentP;
if (parentP->_left == parent)
{
parentP->_left = subL;
}
else
{
parentP->_right = subL;
}
}
}
private:
Node* _root;
};
#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"
#include <vector>
#include <string>
#include <stdlib.h>
#include <time.h>
void TestRBTree()
{
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
RBTree<int, int> t;
int n = 1000000;
srand(time(0));
for (int i = 0; i < n; ++i)
{
int e = rand();
t.Insert(make_pair(e, e));
}
//t.InOrder();
cout << t.IsRBTree() << endl;
}
void test_RBTree()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
RBTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
cout << t.IsRBTree() << endl;
}
int main()
{
test_RBTree();
TestRBTree();
return 0;
}