一个单纯的红黑树
jopen
9年前
#include <stdio.h> #define RED 1 #define BLACK 2 class Node { public: static Node* Nil; Node* left; Node* right; Node* p; int data; int color; Node(int da,int col=RED):data(da),color(col) { this->left=Nil; this->right=Nil; this->p=Nil; } Node():color(BLACK),data(0) {} }; class Tree { public: Node* root; Tree():root(0) {} }; void rotate_left(Node* n) { auto temp=n->right->left; n->right->left=n; n->right->p=n->p; if(n==n->p->left) n->p->left=n->right; else n->p->right=n->right; n->p=n->right; n->right=temp; } void rotate_right(Node* n) { auto temp=n->left->right; n->left->right=n; if(n==n->p->left) n->p->left=n->left; else n->p->right=n->left; n->left->p=n->p; n->p=n->right; n->left=temp; } void fixup(Tree* tree,Node* node) { while(node->p->color==RED) { auto g=node->p->p; if(node->p==g->left) { auto u=g->right; if(u->color==RED) { u->color=BLACK; node->p->color=BLACK; g->color=RED; node=g; }else { if(node==node->p->right) rotate_left(node->p); g->color=RED; node->p->color=BLACK; rotate_right(g); } }else { auto u=g->left; if(u->color==RED) { u->color=BLACK; node->p->color=BLACK; g->color=RED; node=g; }else { if(node==node->p->left) rotate_right(node->p); g->color=RED; node->p->color=BLACK; rotate_left(g); } } } while(tree->root->p!=Node::Nil) tree->root=tree->root->p; tree->root->color=BLACK; } void insert(Tree* tree,Node* root,Node* node) { if(tree->root==NULL) tree->root=node; else { if(root->data < node->data) { if(root->right!=Node::Nil) insert(tree,root->right,node); else { root->right=node; node->p=root; } }else { if(root->left!=Node::Nil) insert(tree,root->left,node); else { root->left=node; node->p=root; } } } fixup(tree,node); } void print_tree(Node* node) { if(node==Node::Nil) return; putchar('('); print_tree(node->left); putchar(')'); printf("%d",node->data); putchar('('); print_tree(node->right); putchar(')'); } Node* Node::Nil=new Node(); int main() { Node::Nil->left=Node::Nil; Node::Nil->right=Node::Nil; Node::Nil->p=Node::Nil; Tree* tree=new Tree(); int array[]={1,2,3,4,5,6,7,8}; for(int i=0;i<sizeof(array)/sizeof(int);++i) insert(tree,tree->root,new Node(array[i],RED)); print_tree(tree->root); return 0; } 相信大家最难理解的部分就是fixup的三种case，就是为什么在这里左旋，又为什么在这里右旋，这里推荐大家看一下introduction algorithms里对RB-TREE的描述。花了3页详细介绍了RB-TREE的每个步骤。