用c++实现自定义红黑树（带有插入功能，左旋转，右旋转）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了用c++实现自定义红黑树（带有插入功能，左旋转，右旋转），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7157字，纯文字阅读大概需要11分钟。
内容图文
**********************************头文件实现***************************
#ifndef REABLACKTREE_REDBLACKTREE_H
#define REABLACKTREE_REDBLACKTREE_H
#include <arpa/nameser.h>
template <class T>
class rbtree;
template <class T>
class rbtreenode;
template <class T>
class rbtreenode
{
friend class rbtree<T>;
public:
rbtreenode(const T& a=T(),rbtreenode<T>* lt=NULL,
rbtreenode<T>* ri=NULL, int c=rbtree<T>::black):data(a),leftnode(lt),rightnode(ri),color(c){
std::cout<<"进入红黑树节点构造函数"<<std::endl;
};
public:
T data;
rbtreenode<T>* leftnode;
rbtreenode<T>* rightnode;
int color; //表示节点颜色
};
template <class T>
class rbtree
{
public:
enum {red,black};
rbtree(const T &neginf);
~rbtree();
typedef rbtreenode<T> node;
void insert(const T& a);
void rotatewithleftchild(node* & k2);//带着左孩子，向右转 向右转节点设为k2，向左转节点设置为k1
void rotatewithrightchild(node* & k1);//带着右孩子，向左转
void doublerotateleftchild(node* &k3);//由于上面两种旋转均为单旋转，单旋转有一定缺陷，故引入双旋转 双旋转向右转
void doublerotaterightchild(node* &k1);//双旋转向左转
//需要处理有两个红色孩子的节点
//插入节点后，处理红色的父亲节点
void handlereorient(T &item);
rbtreenode<T>* rbrotate(T &item,node *parent);
//**********注意单旋转，双旋转（两次单旋转的叠加）传入参数k1,k2,k3,k4的不同，依次为从左到右的节点。**************8
//注意c++中引用不能返回为空 故此在此处可加上自定义引用类型
T find();
T findmax();//最右边的叶子节点
T findmin();//最左边的叶子节点
bool isempty();
void makeempty();
public:
node *header;//指向节点的头指针
node *nullnode;//空节点
node *current;//指向当前节点
node *parent;//指向当前节点的的父节点
node *grand;//祖父节点；
node *grandgrand;//曾祖父节点
void reclaimmemory(node *t); //用递归函数设计
};
template <class T>
rbtree<T>::rbtree(const T &neginf) {
std::cout<<"进入红黑树构造函数"<<std::endl;
nullnode=new node();
nullnode->leftnode=nullnode->rightnode=nullnode;
header=new node(neginf);
header->rightnode=header->leftnode=nullnode;
}
template <class T>
rbtree<T>::~rbtree() {
std::cout<<"进入红黑树析构函数"<<std::endl;
delete nullnode;
delete header;
}
template <class T>
void rbtree<T>::insert(const T &a) {
current=parent=grand=grandgrand=header;
nullnode->data=a;
while (current->data!=a)//二叉搜索树都不能重复
{
grandgrand=grand;//红黑树最主要的是平衡，在平衡阶段会用到这几个节点
grand=parent;
parent=current;
current=a<current->data ?current->leftnode:current->rightnode;
//若在查找的过程中一个节点的孩子都是红色的，需要做处理
if (current->leftnode->color==red&¤t->rightnode->color==red)
{
handlereorient(a);//处理
}
}
if (current!=nullnode) throw "插入时遇到重复的节点抛出异常";//判断当前的节点是否为空节点，不为空则抛出异常，为空不执行
current=new node(a,nullnode,nullnode);//current指向将新建立的节点，以及将current的parent的节点根据数据的大小，
// 用parent指向对像的左指针，或者右指针指向current
if (a<parent->data)
{
parent->leftnode=current;
} else if (a>parent->data)
{
parent->rightnode=current;
}
//**********************insert函数中以上代码类似于二叉查找树，可以插入节点，但是不会自动平衡*************
//自动平衡->红黑树
//自动平衡需要用到向左，向右旋转
//规定新插入的节点都用红色表示
handlereorient(a);//新插入节点是红色的，而它的父节点是红色的
}
//***************************单旋转与双旋转*****************************
//单旋转，向右转
template <class T>//向右转
void rbtree<T>::rotatewithleftchild(node* &k2) {
//定义k1
node* k1=k2->leftnode;
k2->leftnode=k1->rightnode;//横向移动
k1->rightnode=k2;
k2=k1;//替换根
}
//单旋转，向左转
template <class T>//向左转
void rbtree<T>::rotatewithrightchild(node *&k1) {
node* k2=k1->rightnode;
k1->rightnode=k2->leftnode;//横向移动
k2->leftnode=k1;
k1=k2;
}
//双旋转，向右转
template <class T>
void rbtree<T>::doublerotateleftchild(rbtree<T>::node *&k3) {
rotatewithrightchild(k3->leftnode);//k3左节点先向左转
rotatewithleftchild(k3);//k3节点，向右转
}
//双旋转，向左转
template <class T>
void rbtree<T>::doublerotaterightchild(rbtree<T>::node *&k1) {
rotatewithleftchild(k1->rightnode);//节点的右儿子向右转
rotatewithrightchild(k1);//此节点在向左转
}
//通用旋转函数
template <class T>
rbtreenode<T>* rbtree<T>::rbrotate(T &item, rbtree<T>::node *parent) {
//分为四种情况
if(item<parent->data)
{
if (item<parent->leftnode->data)
{
rotatewithleftchild(parent->leftnode);
} else{
rotatewithrightchild(parent->leftnode);
}
return parent->leftnode;
}
else if (item>parent->data)
{
if (item<parent->rightnode->data)
{
rotatewithleftchild(parent->rightnode);
} else
{
rotatewithrightchild(parent->rightnode);
}
return parent->rightnode;
}
}
//处理一个节点的两个子节点都是红色的，以及两个红色的节点相链接问题
template <class T>
void rbtree<T>::handlereorient(T &item) {
//改变颜色 一个黑色节点有两红色的儿子
current->color=red;
current->leftnode->color=black; //处理一个节点的两个儿子节点都为红色，将这个节点变为红色，儿子节点都变为黑色
current->rightnode->color=black;
if(parent->color==red)//处理当前节点和当前节点的父亲节点都为红色
{
grand->color=red;
if (item<grand->data!=item<parent->data)//判断新插入的节点是否是内部孙子
{
parent=rbrotate(item,grand);
}
current=rbrotate(item,grandgrand); //再加一次旋转，若是外部孙子，则只执行这次旋转，而内部孙子则进行上次旋转加本轮旋转（双旋转）
current->color=black;
}
header->rightnode->color=black;//根节点必须是黑色的
//单旋转
//双旋转
}
//红黑树新的功能
//是否为空
template <class T>
bool rbtree<T>::isempty() {
return header->rightnode==nullnode;
}
//清空
template <class T>
void rbtree<T>::makeempty() {
reclaimMemory(header->rightnode);//从根节点开始清除
header->rightnode=nullnode;
}
//清除函数
template <class T>
void rbtree<T>::reclaimmemory(rbtree<T>::node *t) {
if(t!=t->leftnode)
{
reclaimmemory(t->leftnode);
reclaimmemory(t->rightnode);
delete t;
}
}
#endif //REABLACKTREE_REDBLACKTREE_H
************************************.cpp文件实现****************************
#include <iostream>
#include "redblacktree.h"
#include <vector>
using namespace std;
//红黑树：高级的二叉查找树
//平衡树和非平衡树
//红黑树特征：节点1都有颜色，插入和删除节点的时候要遵守红黑规则
//红黑规则：
//1.每一个节点不是红色就是黑色
//2.根总是黑色。
//3.如果节点是红色的，则它的子节点必须是黑社的，（不予许两个红色相连，但允许两个黑色相连）
//4.从根到叶节点的每条路径，必须包含相同数目的黑色节点。
//当插入和删除节点后，不满足红黑规则，则要修正，修正方法
//1.改变节点的颜色
//2.旋转 注意：（当面临两个红节点相连接的时候）当新插入的节点是外部孙子，使用单旋转，若是内部孙子，则使用双旋转
void test_rbtree_insert() //没有动态平衡的红黑树
{
std::cout << "测试自己写的红黑树" << std::endl;
const int neginf=-99999;
rbtree<int> myredblacktree(neginf);
myredblacktree.insert(30);
myredblacktree.insert(15);
myredblacktree.insert(70);
myredblacktree.insert(20);
cout<<myredblacktree.header->data<<endl;
cout<<"-------"<<endl;
cout<<myredblacktree.header->rightnode->data<<endl;
cout<<myredblacktree.header->rightnode->rightnode->data<<endl;
cout<<"向右转"<<endl;
//测试向右转函数
myredblacktree.rotatewithleftchild(myredblacktree.header->rightnode);//传入节点为30，设为转向函数的根节点
cout<<myredblacktree.header->rightnode->data<<endl;
cout<<myredblacktree.header->rightnode->rightnode->data<<endl;
cout<<myredblacktree.header->rightnode->rightnode->leftnode->data<<endl;
cout<<myredblacktree.header->rightnode->rightnode->rightnode->data<<endl;
}
void test_rbtree() //有动态平衡红黑树插入
{
}
int main() {
return 0;
}
内容总结
以上是互联网集市为您收集整理的用c++实现自定义红黑树（带有插入功能，左旋转，右旋转）全部内容，希望文章能够帮你解决用c++实现自定义红黑树（带有插入功能，左旋转，右旋转）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】