本文主要是介绍RB-Tree(红黑树,Red-Back Tree)的C语言算法实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
源文件：red_back_tree.h
#ifndef _RED_BACK_TREE
#define _RED_BACK_TREE
#include <iostream.h>
#define BLACK 0
#define RED 1
typedef struct _RBNode{
int key;
int color;
struct _RBNode *parent, *leftchild, *rightchild;
} RBNode,*RBTree;
static RBNode _Nil = {0, BLACK, NULL, NULL, NULL};
const static RBTree Nil = &_Nil;
#define EQ(x, y) ((x)->key==(y)->key)
#define LT(x, y) ((x)->key < (y)->key)
#define RBTREE_SIZE sizeof(RBNode)
/* 根据关键字集合创建RBTree */
int create_RBTree(RBTree &T, int keys[], int n);
/* 左旋 */
void L_Rote(RBTree &T, RBTree x);
/* 右旋 */
void R_Rote(RBTree &T, RBTree x);
/* 将新节点插入到RBTree中 */
int insert_to_RBTree(RBTree &T, RBTree node);
/* 调整插入T的z结点 */
void fixup_insert_RBTree(RBTree &T, RBTree z);
/* 找到关键字所对应的节点 */
RBTree find_RBTree(const RBTree T, int key);
/* 删除z元素，并返回真正被删除结点的指针。要求z为T中一存在的结点~ */
RBTree delete_from_RBTree(RBTree &T, RBTree z);
/* 删除以key为关键字的结点，~若成功，则返回1，否则返回0. */
int delete_from_RBTree(RBTree &T, int key);
/* 当删除x的原父亲之后，调整x */
void fixup_delete_RBTree(RBTree &T, RBTree x);
/* 先序遍历RBTree */
void pre_order_RBTree(const RBTree T);
void _pre_order_RBTree(const RBTree T);
#endif
源代码：red_back_tree.cpp
#include "red_back_tree.h"
#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <memory.h>
int create_RBTree(RBTree &T, int keys[], int n)
{
RBTree p = NULL;
for(int i = 0; i < n; i++)
{
if(!(p=(RBTree) malloc (RBTREE_SIZE)))
{
exit(-1);
}
p->leftchild = p->rightchild = Nil;
p->key = keys[i];
insert_to_RBTree(T, p);
pri这篇关于RB-Tree(红黑树,Red-Back Tree)的C语言算法实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
