红黑树的代码实现

. //by svking //2012.5

#include #include #include

#define MAXSIZE 1000 typedef int ElemType; #define RED 0 #define BLACK 1 typedef struct RBTNode {

char color; ElemType data; struct RBTNode * p; struct RBTNode * left; struct RBTNode * right; }RBTNode, * PRBTNode;

typedef struct RBTree {

PRBTNode root;

PRBTNode nil; //统一的空节点，该节点是黑的 }RBTree, * PRBTree;

int leftRotate (PRBTree tree, PRBTNode t); int rightRotate (PRBTree tree, PRBTNode t); PRBTNode insertRB (PRBTree tree, ElemType d); int insertRB_fixup (PRBTree tree, PRBTNode t); int createRBTree (PRBTree tree, ElemType d[], int n); int initRB (PRBTree tree);

PRBTNode maximum (PRBTree tree, PRBTNode t); PRBTNode minimum (PRBTree tree, PRBTNode t); PRBTNode next (PRBTree tree, PRBTNode t); PRBTNode precursor (PRBTree tree, PRBTNode t); int walkNext (PRBTree tree);

int inOrderWalk (PRBTree tree, PRBTNode t); int deleteRB_fixup (PRBTree tree, PRBTNode c); PRBTNode deleteRB (PRBTree tree, PRBTNode t); int main () {

PRBTNode p; int d[MAXSIZE]; int n = 0;

1 / 11

. int i; RBTree tree; initRB(&tree);

/* insertRB(&tree, 11); insertRB(&tree, 2); insertRB(&tree, 14);

insertRB(&tree, 1); insertRB(&tree, 7); insertRB(&tree, 15); insertRB(&tree, 5); insertRB(&tree, 8); insertRB(&tree, 4); */ p= insertRB(&tree, 26); insertRB(&tree, 17); insertRB(&tree, 41); insertRB(&tree, 14); insertRB(&tree, 21); insertRB(&tree, 30); insertRB(&tree, 47); insertRB(&tree, 10); insertRB(&tree, 16); insertRB(&tree, 19); insertRB(&tree, 23); insertRB(&tree, 28); insertRB(&tree, 38); insertRB(&tree, 7); insertRB(&tree, 12); insertRB(&tree, 15); insertRB(&tree, 20); insertRB(&tree, 3); insertRB(&tree, 35); insertRB(&tree, 39);

srand(time(NULL));

/* puts(\请输入数据的个数：\随机生成的%d个数据是：\\n\\建树开场\

inOrderWalk(&tree,tree.root); puts(\);

printf(\根是%d \\n\,tree.root->data);

printf(\删除%d后：\,p->data); deleteRB(&tree, p);

inOrderWalk(&tree,tree.root); puts(\);

printf(\根是%d \\n\,tree.root->data);

2 / 11

. return0; }

PRBTNode insertRB (PRBTree tree, ElemType d)

{//插入元素//!!!记得插入的元素的初始化，p指向为父母节点，left和right赋值为NULL。 PRBTNode t = NULL; PRBTNode p = NULL;

int flag = 0; //用来表示插入在左边的树还是右边的树 t = tree->root;

//插入的节点是root,并做相应的初始化if (tree->root == tree->nil) {

tree->root = (PRBTNode)malloc(sizeof(RBTNode)); tree->root->data = d; tree->root->color = BLACK;

tree->root->p = tree->root->left =tree->root->right = tree->nil;

return tree->root; }

while (t != tree->nil) {

p = t;

if (d < t->data) {

flag = 0; t = t->left; } else {

if (d > t->data) {

flag = 1; t = t->right; }else {

if ( (flag=rand()%2) == 0) t = t->left; else

t = t->right; } }

}//while //将t指向带插入节点的地址，并初始化 t = (PRBTNode)malloc(sizeof(RBTNode)); t->data = d;

3 / 11