红黑树、二叉搜索树的实现和性能比较
问题描述： 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋、右旋等），删除，搜索（指定Key值节点）。
另外，红黑树实现计算树黑高的算法。
实验要求：
1).插入测试，输入 8，11，17，15，6，1，22，25，27，建立红黑树，按照红黑树信息输出方式 输出整棵红黑树以及黑高。
2).删除测试，删除1）中红黑树中Key=15的节点，按照 红黑树信息输出方式 输出调整后的整棵红黑树以及黑高。
3).随机产生300,000个不同自然数Key值（1－300,000，每个数出现一次，出现顺序随机），建立红黑树，查找Key=15000的节点，输出查找花费时间。
用上面的数据，建立二叉搜索树，查找Key=15000的节点，输出查找花费时间。
4). 重复3－5次3）中操作，求各自平均时间。
5). 在1)－4)的红黑树算法基础上修改完成P307 14.1-4算法 OS_Key_Rank(T,k). 输入 1,2,3,4,5,6,7,8 建树， k=6, 输出OS_Key_Rank的返回值。
文档要点：总结红黑树和二叉搜索树在查找上的性能分析，描述此类算法的应用。
三、实验过程及程序运行结果分析
1.插入8，11，17，15，6，1，22，25，27，建立红黑树，按照 红黑树信息输出方式输出的红黑树的形状如下图所示，红黑树的黑高度为：2
2. 删除1)中红黑树中Key=15的节点，按照红黑树信息输出方式输出调整后的整棵红黑树如下图所示，黑高度仍为2。
3. 随机产生300,000个不同自然数Key值（1－300,000，每个数出现一次，出现顺序随机），建立红黑树，查找Key=15000的节点，输出查找花费时间，下图为红黑树查找节点所花费的时间，由于红黑树查找节点的时间复杂度为红黑树的高，而红黑树的高不超过2lg(n+1),所以搜索时间非常短。
程序中先后5次建立红黑树和二叉查找树，计算每次的搜索时间，并且分别打印红黑树的黑高度和二叉查找树的高度。最后打印出5次查找的平均时间，结果显示红黑树的查找性能要优于二叉查找树。
程序运行结果如下图所示：每次建立的红黑树黑高度都为12，而二叉查找树的高度不稳定，每次都不一样
4. 建立OS_RBTree树，完成OS_Key_Rank(T,k).算法，下图为输入1,2,3,4,5,6,7,8 建树所建立的带size域的红黑树，当 k=6时, OS_Key_Rank的返回值为6，程序结果如下图所示：
四、实验总结
由于二叉树对某个元素的搜索是与该元素的距离树根结点的高度来决定的，而红黑树的高度不会超过2lg(n+1),因此可以在O(logn)时间内做查找，插入和删除，时间非常快，而二叉查找树通常情况不是一个平衡的二叉树，最坏情况下，树的高度可以达到n，因此查找的时间为O（n）。
如果在实际应用中，遇到了对时间性能要求非常高的查找时，这时候可以考虑运用红黑树，比如Linux内核管理中的虚拟存储器的管理，STL的中map和set等都是用红黑树实现的。
附录：c++源码实现
其中test.txt中的内容是一串数字：8 11 17 15 6 1 22 25 27
main.cpp
#include <iostream>
#include <windows.h>
#include "RedBlackFinal.h"
#include "BSTree.h"
#include "Function.h"
#include "OS_RBTree.h"
using namespace std;
int main()
{
RBTree<int> rbtree;
const string fileName = "test.txt";
rbtree.BuildTree(fileName);
rbtree.PrintFormat(rbtree.GetRoot(),0);
cout << endl << "The black height of this RBTree is " << rbtree.GetBlackHeight() << endl << endl;
rbtree.Delete(15);
cout << "delete the node whose value is 15:" << endl;
rbtree.PrintFormat(rbtree.GetRoot(),0);
cout << endl << "The black height of this RBTree is " << rbtree.GetBlackHeight() << endl << endl;
const int TIMES = 5;
RBTree<int> tree1[TIMES]; //红黑树
BSTree<int> tree2[TIMES]; //二叉搜索树
LARGE_INTEGER litmp;
LONGLONG start=0,end=0;
double dfMinus, dfFreq, dfTim;
QueryPerformanceFrequency(&litmp);
dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率
srand((unsigned)time(0));
double sumTime1,sumTime2;
sumTime1 = sumTime2 = 0.0;
const string name = "data.txt";
int key = 15000;
for(int i=0; i<TIMES; ++i)
{
BuildRandFile(name); //生成300000个随机数，保存到文件中
tree1[i].BuildTree(name);
tree2[i].BuildTree(name);
QueryPerformanceCounter(&litmp);
start = litmp.QuadPart; // 获得初始值
tree1[i].IsGetNode(key); //查找键值为Key的节点
QueryPerformanceCounter(&litmp);
end = litmp.QuadPart; //获得中止值
dfMinus = (double)(end-start);
dfTim = dfMinus / dfFreq; // 获得对应的时间为秒
sumTime1 += dfTim * 1000;
cout << "The black height of this RBTree[" << i << "] is " << tree1[i].GetBlackHeight() << endl << endl;
QueryPerformanceCounter(&litmp);
start = litmp.QuadPart; // 获得初始值
tree2[i].IsGetNode(key); //查找键值为Key的节点
QueryPerformanceCounter(&litmp);
end = litmp.QuadPart; //获得中止值
dfMinus = (double)(end-start);
dfTim = dfMinus / dfFreq; // 获得对应的时间为秒
sumTime2 += dfTim * 1000;
cout << "The black height of this BSTree[" << i << "] is " << tree2[i].GetHeight() << endl << endl;
}
cout << "The average of search time of RBTree is " << sumTime1 / TIMES << "ms" << endl;
cout << "The average of search time of BSTree is " << sumTime2 / TIMES << "ms" << endl;
cout << endl;
OS_RBTree<int> osTree;
for(int i=1;i<=8;++i)
osTree.Insert(i);
osTree.PrintFormat(osTree.GetRoot(),0);
cout << endl;
cout << "the rank value is " << osTree.OS_Key_Rank(6) << endl;
return 0;
}
RedBlack.h
#ifndef REDBLACKFINAL_H
#define REDBLACKFINAL_H
#include <iostream>
#include <stack>
#include <fstream>
#include <string>
using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::stack;
using std::ifstream;
using std::ofstream;
template <typename KEY>
class RBTree
{
class Node ; //节点定义
public:
RBTree();
~RBTree();
void Insert(KEY key);
void Delete(KEY key);
void InOrder();
void PrintFormat(Node*,int);
void BuildTree(const string &name);
int GetBlackHeight();
ifstream& input(ifstream&);
Node* GetRoot()
{
return root;
}
inline Node* GetNode(KEY key)
{
return FindKey(key);
}
inline bool IsGetNode(KEY key);
bool Empty()
{
return root == nullNode;
}
private:
enum NodeColor {RED,BLACK}; //节点颜色，枚举类型
Node *root,*nullNode;
void LeftRotate(Node *node); //左旋
void RightRotate(Node *node); //右旋
void InsertFixup(Node *node); //插入调整
void DeleteFixup(Node *node); //删除调整
void PrintKeyAndColor(Node*);
void MakeSpace(int level);
bool Clear(Node *);
Node* GetUncle(Node *node)
{
Node *result = NULL,*parent,*grandFather;
parent = node->parent;
grandFather = parent->parent;
if(parent == grandFather->left)
result = grandFather->right;
else
result = grandFather->left;
return result;
}
Node* FindKey(KEY key)
{
Node *result;
result = root;
while (result!=nullNode && key!=result->key)
{
if (key < result->key)
{
result = result->left;
}
else if(key > result->key)
{
result = result->right;
}
}
return result;
}
Node* RBTreeSuccessor(Node *node)
{
Node *result;
result = node->right;
if(result != nullNode)
while(result->left != nullNode)
result = result->left;
else
{
result = node->parent;
while (result!=nullNode && node==result->right)
{
node = result;
result = result->parent;
}
}
return result;
}
};
template <typename T>
void RBTree<T>::BuildTree(const string &name)
{
ifstream in(name.c_str());
while (!in.eof())
{
int data;
in >> data;
Insert(data);
}
in.close();
}
template <typename KEY>
void RBTree<KEY>::MakeSpace(int level)
{
for(int i=0; i<level; ++i)
cout << " ";
}
template <typename KEY>
void RBTree<KEY>::PrintFormat(Node* node,int level)
{
if(node == root)
cout << "(";
PrintKeyAndColor(node);
if(node == node->parent->left)
cout << ",";
cout << endl;
MakeSpace(level + 1);
cout << "(";
if (node->left == nullNode)
{
PrintKeyAndColor(node->left);
cout << ",";
}
else
{
PrintFormat(node->left,level + 1);
}
cout << endl;
MakeSpace(level + 1);
if (node->right == nullNode)
{
PrintKeyAndColor(node->right);
// cout << ")";
}
else
{
PrintFormat(node->right,level + 1);
}
cout << endl;
MakeSpace(level + 1);
cout << ")";
if(node == root)
cout << endl << ")";
}
template <typename KEY>
void RBTree<KEY>::PrintKeyAndColor(Node* node)
{
if (node == nullNode)
{
cout << "NIL" ;
}
else
{
cout << node->key;
if(node->color == RED)
cout << "R";
else
cout << "B";
}
}
//template <typename KEY>
//ifstream& RBTree<KEY>::input(ifstream& in)
//{
// while (!in.eof())
// {
// int data;
// in >> data;
// Insert(data);
// }
// return in;
//}
template <typename KEY>
void RBTree<KEY>::InOrder()
{
// cout << "this time is starting ********" << endl;
stack<Node*> st;
Node *node = root;
while (!st.empty() || node!=nullNode)
{
while (node != nullNode)
{
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
if(node == root)
{
cout << "root = " << node->key << " " << node->color << endl;
cout << "root->left = " << node->left->key << " " << node->left->color << endl;
cout << "root->right = " << node->right->key << " " << node->right->color << endl;
}
cout << node->key << " ";
node = node->right;
}
}
template <typename KEY>
class RBTree<KEY>::Node //节点定义
{
public:
Node(KEY k ,NodeColor col):key(k),color(col),left(NULL),right(NULL),parent(NULL) {}
Node():key(-1),color(BLACK),left(NULL),right(NULL),parent(NULL) {}
KEY key;
NodeColor color;
Node *left,*right,*parent;
};
template <typename KEY>
RBTree<KEY>::RBTree()
{
nullNode = new Node();
nullNode->left = nullNode; //此处是否可指向root？
nullNode->right = nullNode;
nullNode->parent = nullNode;
root = nullNode;
}
template <typename KEY>
void RBTree<KEY>::Insert(KEY key)
{
Node *node,*temp;
temp = NULL;
node = root;
while (node != nullNode)
{
temp = node;
if (key < node->key)
{
node = node->left;
}
else if(key > node->key)
{
node = node->right;
}
else
return;
}
Node *newNode = new Node(key,RED);
newNode->left = nullNode;
newNode->right = nullNode;
newNode->parent = nullNode;
if(root == nullNode)
{
root = newNode;
root->color = BLACK;
nullNode->left = root;
nullNode->right = root;
nullNode->parent = root;
return; //如果插入根节点，不用fixup
}
else
{
node = temp;
if(key < node->key)
node->left = newNode;
else
node->right = newNode;
}
newNode->parent = node;
InsertFixup(newNode);
}
template <typename KEY>
void RBTree<KEY>::InsertFixup(Node *node)
{
Node *parent = NULL;
while ((parent = node->parent) && node->parent->color == RED)
{
if (parent == parent->parent->left)
{
Node *uncle = GetUncle(node);
if (uncle->color == RED) //uncle may be nullNode
{
parent->color = BLACK;
uncle->color = BLACK;
parent->parent->color = RED;
node = parent->parent;
}
else
{
if(node == parent->right)
{
node = parent;
LeftRotate(node);
}
parent = node->parent;
parent->color = BLACK;
parent->parent->color = RED;
RightRotate(parent->parent);
}
}
else
{
Node *uncle = GetUncle(node);
if (uncle->color == RED)
{
parent->color = BLACK;
uncle->color = BLACK;
parent->parent->color = RED;
node = parent->parent;
}
else
{
if(node == parent->left)
{
node = parent;
RightRotate(node);
}
parent = node->parent;
parent->color = BLACK;
parent->parent->color = RED;
LeftRotate(parent->parent);
}
}
}
root->color = BLACK;
}
template <typename KEY>
void RBTree<KEY>::Delete(KEY key)
{
Node *node = FindKey(key); //找到被删除的节点
if(node == nullNode)
return;
Node *child = nullNode,*real = nullNode;
if(node->left==nullNode || node->right==nullNode)
real = node;
else
real = RBTreeSuccessor(node); //物理删除的节点
if (real->left != nullNode)
{
child = real->left;
}
else
{
child = real->right;
}
child->parent = real->parent; //没有判断child是否为NIL
if(real->parent == nullNode)
{
root = child;
nullNode->left = root;
nullNode->right = root;
nullNode->parent = root;
}
else if (real == real->parent->left)
{
real->parent->left = child;
}
else
{
real->parent->right = child;
}
if(node != real) //物理删除的节点不是node
node->key = real->key;
if(real->color == BLACK) //颜色为黑，需要fixup
DeleteFixup(child);
delete real;
real = NULL;
}
template <typename KEY>
void RBTree<KEY>::DeleteFixup(Node *node)
{
while (node!=root && node->color==BLACK)
{
Node* parent = node->parent;
if (node == parent->left)
{
Node *brother = parent->right;
if (brother->color == RED) //case1
{
parent->color = RED;
brother->color = BLACK;
LeftRotate(parent);
brother = parent->right; //reset brother node
} //case1 can run into from case2 to case4
if (brother->left->color==BLACK && brother->right->color==BLACK) //case2
{
brother->color = RED;
node = parent;
}
else //case2 and case3 must not exist!!!
{
if(brother->right->color==BLACK) //case3
{
brother->left->color = BLACK;
brother->color = RED;
RightRotate(brother);
brother = parent->right; //reset brother node
} //case3 can run into case4
brother->color = parent->color; //case4
parent->color = BLACK;
brother->right->color = BLACK;
LeftRotate(parent);
node = root; //break
}
}
else
{
Node *brother = parent->left;
if (brother->color == RED) //case1
{
parent->color = RED;
brother->color = BLACK;
RightRotate(parent);
brother = parent->left; //reset brother node
}
if (brother->left->color==BLACK && brother->right->color==BLACK) //case2
{
brother->color = RED;
node = parent;
}
else //case2 and case3 must not exist!!!
{
if(brother->left->color==BLACK) //case3
{
brother->right->color = BLACK;
brother->color = RED;
LeftRotate(brother);
brother = parent->left; //reset brother node
}
brother->color = parent->color; //case4
parent->color = BLACK;
brother->left->color = BLACK;
RightRotate(parent);
node = root; //break
}
}
}
node->color = BLACK;
nullNode->parent = root;
root->color = BLACK;
}
template <typename KEY>
void RBTree<KEY>::RightRotate(Node *node)
{
Node *leftNode = node->left;
node->left = leftNode->right;
leftNode->right->parent = node;
leftNode->parent = node->parent;
if(leftNode->right!=nullNode)
{
leftNode->right->parent = node;
}
if (node->parent != nullNode)
{
if (node == node->parent->left)
{
node->parent->left = leftNode;
}
else
{
node->parent->right = leftNode;
}
}
else
{
root = leftNode;
nullNode->left = root;
nullNode->right = root;
}
node->parent = leftNode;
leftNode->right = node;
}
template <typename KEY>
void RBTree<KEY>::LeftRotate(Node *node)
{
Node *rightNode = node->right;
node->right = rightNode->left;
rightNode->left->parent = node;
rightNode->parent = node->parent;
if(rightNode->left!=nullNode)
{
rightNode->left->parent = node;
}
if(node->parent != nullNode)
{
if(node == node->parent->left) //node is the left child of its parent
node->parent->left = rightNode;
else
node->parent->right = rightNode;
}
else
{
root = rightNode;
nullNode->left = root;
nullNode->right = root;
}
//node is root
node->parent = rightNode;
rightNode->left = node;
}
template <typename KEY>
bool RBTree<KEY>::IsGetNode(KEY key)
{
if(FindKey(key) != nullNode)
return true;
else
return false;
}
template <typename KEY>
int RBTree<KEY>::GetBlackHeight()
{
Node *pNode = root;
int height = 0;
while (pNode != nullNode)
{
if(pNode->color == BLACK)
++height;
pNode = pNode->left;
}
return height;
}
template <typename KEY>
bool RBTree<KEY>::Clear(Node * node)
{
if (node != nullNode)
{
Clear(node->left);
Clear(node->right);
delete node;
}
delete nullNode;
return true;
}
template <typename KEY>
RBTree<KEY>::~RBTree()
{
Clear(root);
}
#endif // REDBLACKFINAL_H
OS_RBTree.h
#ifndef OS_RBTREE_H
#define OS_RBTREE_H
#include <iostream>
#include <stack>
#include <fstream>
#include <string>
using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::stack;
using std::ifstream;
using std::ofstream;
template <typename KEY>
class OS_RBTree
{
class Node ; //节点定义
public:
OS_RBTree();
~OS_RBTree();
void Insert(KEY key);
void Delete(KEY key);
void BuildTree(const string &name);
int OS_Key_Rank(KEY key);
void PrintFormat(Node* node,int level);
void MakeSpace(int);
void PrintKeyAndColor(Node* node);
Node* GetRoot()
{
return root;
}
private:
enum NodeColor {RED,BLACK}; //节点颜色，枚举类型
Node *root,*nullNode;
void LeftRotate(Node *node); //左旋
void RightRotate(Node *node); //右旋
void InsertFixup(Node *node); //插入调整
void DeleteFixup(Node *node); //删除调整
bool Clear(Node *);
Node* GetUncle(Node *node)
{
Node *result = NULL,*parent,*grandFather;
parent = node->parent;
grandFather = parent->parent;
if(parent == grandFather->left)
result = grandFather->right;
else
result = grandFather->left;
return result;
}
Node* FindKey(KEY key)
{
Node *result;
result = root;
while (result!=nullNode && key!=result->key)
{
if (key < result->key)
{
result = result->left;
}
else if(key > result->key)
{
result = result->right;
}
}
return result;
}
Node* OS_RBTreeSuccessor(Node *node)
{
Node *result;
result = node->right;
if(result != nullNode)
while(result->left != nullNode)
result = result->left;
else
{
result = node->parent;
while (result!=nullNode && node==result->right)
{
node = result;
result = result->parent;
}
}
return result;
}
};
template <typename KEY>
class OS_RBTree<KEY>::Node //节点定义
{
public:
Node(KEY k ,NodeColor col):key(k),size(1),color(col),left(NULL),right(NULL),parent(NULL) {}
Node():key(-1),size(0),color(BLACK),left(NULL),right(NULL),parent(NULL) {}
KEY key;
int size;
NodeColor color;
Node *left,*right,*parent;
};
template <typename KEY>
OS_RBTree<KEY>::OS_RBTree()
{
nullNode = new Node();
nullNode->left = nullNode; //此处是否可指向root？
nullNode->right = nullNode;
nullNode->parent = nullNode;
root = nullNode;
}
template <typename KEY>
int OS_RBTree<KEY>::OS_Key_Rank(KEY key)
{
Node *node = FindKey(key);
int r = node->left->size + 1;
while (node != root)
{
if(node == node->parent->right)
r += node->parent->left->size + 1;
node = node->parent;
}
return r;
}
template <typename KEY>
void OS_RBTree<KEY>::Insert(KEY key)
{
Node *node,*temp;
temp = NULL;
node = root;
while (node != nullNode)
{
++node->size; //修改size域
temp = node;
if (key < node->key)
{
node = node->left;
}
else if(key > node->key)
{
node = node->right;
}
else
return;
}
Node *newNode = new Node(key,RED);
newNode->left = nullNode;
newNode->right = nullNode;
newNode->parent = nullNode;
if(root == nullNode)
{
root = newNode;
root->color = BLACK;
nullNode->left = root;
nullNode->right = root;
nullNode->parent = root;
return; //如果插入根节点，不用fixup
}
else
{
node = temp;
if(key < node->key)
node->left = newNode;
else
node->right = newNode;
}
newNode->parent = node;
InsertFixup(newNode);
}
template <typename KEY>
void OS_RBTree<KEY>::InsertFixup(Node *node)
{
Node *parent = NULL;
while ((parent = node->parent) && node->parent->color == RED)
{
if (parent == parent->parent->left)
{
Node *uncle = GetUncle(node);
if (uncle->color == RED) //uncle may be nullNode
{
parent->color = BLACK;
uncle->color = BLACK;
parent->parent->color = RED;
node = parent->parent;
}
else
{
if(node == parent->right)
{
node = parent;
LeftRotate(node);
}
parent = node->parent;
parent->color = BLACK;
parent->parent->color = RED;
RightRotate(parent->parent);
}
}
else
{
Node *uncle = GetUncle(node);
if (uncle->color == RED)
{
parent->color = BLACK;
uncle->color = BLACK;
parent->parent->color = RED;
node = parent->parent;
}
else
{
if(node == parent->left)
{
node = parent;
RightRotate(node);
}
parent = node->parent;
parent->color = BLACK;
parent->parent->color = RED;
LeftRotate(parent->parent);
}
}
}
root->color = BLACK;
}
template <typename KEY>
void OS_RBTree<KEY>::Delete(KEY key)
{
Node *node;
node = root;
while (node!=nullNode && key!=node->key)
{
--node->size; //修改node的size域
if (key < node->key)
{
node = node->left;
}
else if(key > node->key)
{
node = node->right;
}
}
if(node == nullNode)
return;
--node->size; //修改node的size域
Node *child = nullNode,*real = nullNode;
if(node->left==nullNode || node->right==nullNode)
real = node;
else
{
Node *result;
result = node->right;
if(result != nullNode)
while(result->left != nullNode)
{
--result->size; //修改node的size域
result = result->left;
}
real = result; //物理删除的节点
}
if (real->left != nullNode)
{
child = real->left;
}
else
{
child = real->right;
}
child->parent = real->parent; //没有判断child是否为NIL
if(real->parent == nullNode)
{
root = child;
nullNode->left = root;
nullNode->right = root;
nullNode->parent = root;
}
else if (real == real->parent->left)
{
real->parent->left = child;
}
else
{
real->parent->right = child;
}
if(node != real) //物理删除的节点不是node
node->key = real->key;
if(real->color == BLACK) //颜色为黑，需要fixup
DeleteFixup(child);
delete real;
real = NULL;
}
template <typename KEY>
void OS_RBTree<KEY>::DeleteFixup(Node *node)
{
while (node!=root && node->color==BLACK)
{
Node* parent = node->parent;
if (node == parent->left)
{
Node *brother = parent->right;
if (brother->color == RED) //case1
{
parent->color = RED;
brother->color = BLACK;
LeftRotate(parent);
brother = parent->right; //reset brother node
} //case1 can run into from case2 to case4
if (brother->left->color==BLACK && brother->right->color==BLACK) //case2
{
brother->color = RED;
node = parent;
}
else //case2 and case3 must not exist!!!
{
if(brother->right->color==BLACK) //case3
{
brother->left->color = BLACK;
brother->color = RED;
RightRotate(brother);
brother = parent->right; //reset brother node
} //case3 can run into case4
brother->color = parent->color; //case4
parent->color = BLACK;
brother->right->color = BLACK;
LeftRotate(parent);
node = root; //break
}
}
else
{
Node *brother = parent->left;
if (brother->color == RED) //case1
{
parent->color = RED;
brother->color = BLACK;
RightRotate(parent);
brother = parent->left; //reset brother node
}
if (brother->left->color==BLACK && brother->right->color==BLACK) //case2
{
brother->color = RED;
node = parent;
}
else //case2 and case3 must not exist!!!
{
if(brother->left->color==BLACK) //case3
{
brother->right->color = BLACK;
brother->color = RED;
LeftRotate(brother);
brother = parent->left; //reset brother node
}
brother->color = parent->color; //case4
parent->color = BLACK;
brother->left->color = BLACK;
RightRotate(parent);
node = root; //break
}
}
}
node->color = BLACK;
nullNode->parent = root;
root->color = BLACK;
}
template <typename KEY>
void OS_RBTree<KEY>::RightRotate(Node *node)
{
Node *leftNode = node->left;
//修改size域
leftNode->size = node->size;
node->size = leftNode->right->size + node->right->size + 1; //修改node的size域
node->left = leftNode->right;
leftNode->right->parent = node;
leftNode->parent = node->parent;
if(leftNode->right!=nullNode)
{
leftNode->right->parent = node;
}
if (node->parent != nullNode)
{
if (node == node->parent->left)
{
node->parent->left = leftNode;
}
else
{
node->parent->right = leftNode;
}
}
else
{
root = leftNode;
nullNode->left = root;
nullNode->right = root;
}
node->parent = leftNode;
leftNode->right = node;
}
template <typename KEY>
void OS_RBTree<KEY>::LeftRotate(Node *node)
{
Node *rightNode = node->right;
rightNode->size = node->size; //修改size域
node->size = node->left->size + rightNode->left->size + 1; //修改node的size域
node->right = rightNode->left;
rightNode->left->parent = node;
rightNode->parent = node->parent;
if(rightNode->left!=nullNode)
{
rightNode->left->parent = node;
}
if(node->parent != nullNode)
{
if(node == node->parent->left) //node is the left child of its parent
node->parent->left = rightNode;
else
node->parent->right = rightNode;
}
else
{
root = rightNode;
nullNode->left = root;
nullNode->right = root;
}
//node is root
node->parent = rightNode;
rightNode->left = node;
}
template <typename KEY>
void OS_RBTree<KEY>::MakeSpace(int level)
{
for(int i=0; i<level; ++i)
cout << " ";
}
template <typename KEY>
void OS_RBTree<KEY>::PrintFormat(Node* node,int level)
{
if(node == root)
cout << "(";
PrintKeyAndColor(node);
cout << endl;
MakeSpace(level + 1);
cout << "(";
if (node->left == nullNode)
{
PrintKeyAndColor(node->left);
// cout << ",";
}
else
{
PrintFormat(node->left,level + 1);
}
cout << endl;
MakeSpace(level + 1);
if (node->right == nullNode)
{
PrintKeyAndColor(node->right);
// cout << ")";
}
else
{
PrintFormat(node->right,level + 1);
}
cout << endl;
MakeSpace(level + 1);
cout << ")";
if(node == root)
cout << endl << ")";
}
template <typename KEY>
void OS_RBTree<KEY>::PrintKeyAndColor(Node* node)
{
if (node == nullNode)
{
cout << "NIL" ;
}
else
{
cout << node->key;
if(node->color == RED)
cout << "R" ;
else
cout << "B";
cout << ",size: " << node->size;
}
// if(node == node->parent->left)
// cout << "," << endl;
}
template <typename KEY>
bool OS_RBTree<KEY>::Clear(Node * node)
{
if (node != nullNode)
{
Clear(node->left);
Clear(node->right);
delete node;
}
delete nullNode;
return true;
}
template <typename KEY>
OS_RBTree<KEY>::~OS_RBTree()
{
Clear(root);
}
#endif // OS_RBTREE_H