算法导论之红黑树

清疚 2022-07-24 09:13 159阅读 0赞

**红黑树定义**：是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是红色也可以是黑色。通过对任意一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长2倍，因而是近似于平衡的。

**红黑树的性质**：

1.每个节点或者是红色的，或者是黑色的。

2.根结点是黑色的。

3.每个叶子结点都是黑色的。

4.如果一个结点的颜色是红色的，则它的两个子结点都是黑色的。

5.对每个结点，从该结点到其他所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

**C语言实现代码**如下：

#include <stdio.h>
    
    struct RedBlackNode{
    	int value;
    	char color;
    	struct RedBlackNode *right;
    	struct RedBlackNode *left;
    	struct RedBlackNode *parent;
    };
    
    typedef struct RedBlackNode RBNode;
    //定义全局变量当做叶子结点 
    RBNode *nil;
    //左旋转 
    RBNode *LEFT_ROTATE(RBNode *root,RBNode *x){
    	RBNode *y=x->right;
    	x->right=y->left;
    	if(y->left!=nil){
    		y->left->parent=x;
    	}
    	y->parent=x->parent;
    	if(x->parent==nil){
    		root=y;
    	}else if(x==x->parent->left){
    		x->parent->left=y;
    	}else{
    		x->parent->right=y;
    	}
    	y->left=x;
    	x->parent=y;
    	return root;
    }
    //右旋转 
    RBNode *RIGHT_ROTATE(RBNode *root,RBNode *x){
    	RBNode *y=x->left;
    	x->left=y->right;
    	if(y->right!=nil){
    		y->right->parent=x;
    	}
    	y->parent=x->parent;
    	if(x->parent==nil){
    		root=y;
    	}else if(x==x->parent->right){
    		x->parent->right=y;
    	}else{
    		x->parent->left=y;
    	}
    	y->right=x;
    	x->parent=y;
    	return root;
    }
    
    //用树v代替树u 
    RBNode *RB_TRANSPLANT(RBNode *root,RBNode *u,RBNode *v){
    	if(u->parent==nil){
    		root=v;
    	}else if(u==u->parent->left){
    		u->parent->left=v;
    	}else{
    		u->parent->right=v;
    	}
    	v->parent=u->parent;
    	return root;
    }
    //查找结点z下的最小值的结点 
    RBNode *TREE_MINIMUM(RBNode	 *z){
    	RBNode *rs=z;
    	while(rs->left!=nil){
    		rs=rs->left;
    	}
    	return rs;
    }
    //删除后对红黑树进行调整 
    RBNode *RB_DELETE_FIXUP(RBNode *root,RBNode *x){
    	RBNode *w = nil;
    	while(x!=root && x->color=='B'){
    		if(x==x->parent->left){
    			w = x->parent->right;
    			if(w->color=='R'){
    				w->color='B';
    				x->parent->color='R';
    				root = LEFT_ROTATE(root,x->parent);
    				w=x->parent->right;
    			}
    			if(w->left->color=='B' && w->right->color=='B'){
    				w->color='R';
    				x=x->parent;
    			}else {
    				if(w->right->color=='B'){
    					w->left->color='B';
    					w->color='R';
    					root = RIGHT_ROTATE(root,w);
    					w = x->parent->right;
    				}
    				w->color=x->parent->color;
    				x->parent->color='B';
    				w->right->color='B';
    				root = LEFT_ROTATE(root,x->parent);
    				x = root;
    			}
    		}else {
    			RBNode *w = x->parent->left;
    			if(w->color=='R'){
    				w->color='B';
    				x->parent->color='R';
    				root = RIGHT_ROTATE(root,x->parent);
    				w=x->parent->left;
    			}
    			if(w->right->color=='B' && w->left->color=='B'){
    				w->color='R';
    				x=x->parent;
    			}else {
    				if(w->left->color=='B'){
    					w->right->color='B';
    					w->color='R';
    					root = LEFT_ROTATE(root,w);
    					w = x->parent->left;
    				}
    				w->color=x->parent->color;
    				x->parent->color='B';
    				w->left->color='B';
    				root = RIGHT_ROTATE(root,x->parent);
    				x = root;
    			}
    		}
    	}
    	x->color='B';
    	return root;
    }
    //删除红黑树中某一结点 
    RBNode *RB_DELETE(RBNode *root,RBNode *z){
    	RBNode *y=z;
    	RBNode *x=nil;
    	char Y_ORIGINAL_COLOR=y->color;
    	if(z->left==nil){
    		x = z->right;
    		root=RB_TRANSPLANT(root,z,z->right);
    	}else if(z->right==nil){
    		x = z->left;
    		root = RB_TRANSPLANT(root,z,z->left);
    	}else{
    		y=TREE_MINIMUM(z->right);
    		Y_ORIGINAL_COLOR=y->color;
    		x=y->right;
    		if(y->parent==z){
    			x->parent=y;
    		}else{
    			root = RB_TRANSPLANT(root,y,y->right);
    			y->right=z->right;
    			y->right->parent=y;
    		}
    		root = RB_TRANSPLANT(root,z,y);
    		y->left=z->left;
    		y->left->parent=y;
    		y->color=z->color;
    	}
    	if(Y_ORIGINAL_COLOR=='B'){
    		root = RB_DELETE_FIXUP(root,x);
    	}
    	return root;
    }
    //插入某结点后的调整
    RBNode *RB_INSERT_FIXUP(RBNode *root,RBNode *z){
    	while(z->parent->color=='R'){
    		if(z->parent==z->parent->parent->left){
    			RBNode *y=z->parent->parent->right;
    			if(y->color=='R'){
    				z->parent->color='B';
    				y->color='B';
    				z->parent->parent->color='R';
    				z=z->parent->parent;
    			}else{
    				if(z==z->parent->right){
    					z=z->parent;
    					root = LEFT_ROTATE(root,z);
    				}
    				z->parent->color='B';
    				z->parent->parent->color='R';
    				root = RIGHT_ROTATE(root,z->parent->parent);
    			}
    		}else {
    			RBNode *y=z->parent->parent->left;
    			if(y->color=='R'){
    				z->parent->color='B';
    				y->color='B';
    				z->parent->parent->color='R';
    				z=z->parent->parent;
    			}else{
    				if(z==z->parent->left){
    					z=z->parent;
    					root = RIGHT_ROTATE(root,z);
    				}
    				z->parent->color='B';
    				z->parent->parent->color='R';
    				root = LEFT_ROTATE(root,z->parent->parent);
    			}
    		}
    	}
    	root->color='B';
    	return root;
    }
    //插入一个节点 
    RBNode *RB_INSERT(RBNode *root,RBNode *z){
    	RBNode *x=root,*y=nil;
    	while(x!=nil){
    		y=x;
    		if(z->value<x->value){
    			x=x->left;
    		}else{
    			x=x->right;
    		}
    	}
    	z->parent=y;
    	if(y==nil){
    		root=z;
    	}else if(z->value<y->value){
    		y->left=z;
    	}else{
    		y->right=z;
    	}
    	z->left=nil;
    	z->right=nil;
    	z->color='R';
    	root = RB_INSERT_FIXUP(root,z);
    	return root;
    }
    //中序遍历树
    void inOrder(RBNode	*tree) {
    	if (tree != nil) {
    		inOrder(tree->left);
    		printf("%d,%c\n",tree->value,tree->color);
    		inOrder(tree->right);
    	}
    } 
    //选择一个节点
    RBNode	*selectNode(RBNode	*root,int key){
    	RBNode	*temp = root;
    	while (temp!=nil) {
    		if (temp->value	>key) {
    			temp=temp->left;
    		}else if (temp->value<key) {
    			temp=temp->right;
    		}else {
    			return temp;
    		}
    	}
    	return temp;
    } 
    int main(int argc, char *argv[])
    {
    	nil=(RBNode *)malloc(sizeof(RBNode));
    	nil->color='B';
    	RBNode *root = nil;
    	int a[] = { 41, 38, 31, 12, 19, 8 };
    	int i = 0,n=sizeof(a)/sizeof(int);
    	for (; i < n; i++) {
    		RBNode *z = (RBNode *)malloc(sizeof(RBNode));
    		z->value = a[i];
    		root = RB_INSERT(root, z);
    	}
    	inOrder(root);
    	
    	printf("\n测试删除根节点：\n");
    	RBNode *deleteNode = selectNode(root,38);
    	root = RB_DELETE(root,deleteNode);
    	inOrder(root);
    	return 0;
    }

**Java语言实现代码**如下：

package algorithms;
    
    public class RB_Tree {
    	public rb_node T = null;
    	private static String RED = "red";
    	private static String BLACK = "black";
    	private static rb_node T_nil = new rb_node(BLACK);
    
    	public static class rb_node {
    		String color;
    		int key;
    		rb_node left;
    		rb_node right;
    		rb_node p;
    
    		public rb_node() {
    			this.color = RED;
    			this.key = Integer.MIN_VALUE;
    			this.left = T_nil;
    			this.right = T_nil;
    			this.p = T_nil;
    		}
    
    		public rb_node(String color) {
    			this.color = color;
    			this.key = Integer.MIN_VALUE;
    			this.left = null;
    			this.right = null;
    			this.p = null;
    		}
    	}
    
    	private static rb_node LEFT_ROTATE(rb_node T, rb_node x) {
    		rb_node y = x.right;
    		x.right = y.left;
    		if (y.left != T_nil) {
    			y.left.p = x;
    		}
    		y.p = x.p;
    		if (x.p == T_nil) {
    			T = y;
    		} else if (x == x.p.left) {
    			x.p.left = y;
    		} else {
    			x.p.right = y;
    		}
    		y.left = x;
    		x.p = y;
    		return T;
    	}
    
    	private static rb_node RIGHT_ROTATE(rb_node T, rb_node x) {
    		rb_node y = x.left;
    		x.left = y.right;
    		if (y.right != T_nil) {
    			y.right.p = x;
    		}
    		y.p = x.p;
    		if (x.p == T_nil) {
    			T = y;
    		} else if (x == x.p.left) {
    			x.p.left = y;
    		} else {
    			x.p.right = y;
    		}
    		y.right = x;
    		x.p = y;
    		return T;
    	}
    
    	public rb_node RB_INSERT(rb_node T, rb_node z) {
    		rb_node y = T_nil;
    		rb_node x = T;
    		while (x != T_nil) {
    			y = x;
    			if (z.key < x.key) {
    				x = x.left;
    			} else {
    				x = x.right;
    			}
    		}
    		z.p = y;
    		if (y == T_nil) {
    			T = z;
    		} else if (z.key < y.key) {
    			y.left = z;
    		} else {
    			y.right = z;
    		}
    		z.color = RED;
    		T = RB_INSERT_FIXUP(T, z);
    		return T;
    	}
    
    	private static rb_node RB_INSERT_FIXUP(rb_node T, rb_node z) {
    		while (z.p.color == RED) {
    			if (z.p == z.p.p.left) {
    				rb_node y = z.p.p.right;
    				if (y.color == RED) {
    					z.p.color = BLACK;
    					y.color = BLACK;
    					z.p.p.color = RED;
    					z = z.p.p;
    				} else {
    					if (z == z.p.right) {
    						z = z.p;
    						T = LEFT_ROTATE(T, z);
    					}
    					z.p.color = BLACK;
    					z.p.p.color = RED;
    					T = RIGHT_ROTATE(T, z.p.p);
    				}
    			} else {
    				rb_node y = z.p.p.left;
    				if (y.color == RED) {
    					z.p.color = BLACK;
    					y.color = BLACK;
    					z.p.p.color = RED;
    					z = z.p.p;
    				} else {
    					if (z == z.p.left) {
    						z = z.p;
    						T = RIGHT_ROTATE(T, z);
    					}
    					z.p.color = BLACK;
    					z.p.p.color = RED;
    					T = LEFT_ROTATE(T, z.p.p);
    				}
    			}
    
    		}
    		T.color = BLACK;
    		return T;
    	}
    
    	public rb_node RB_DELETE(rb_node T, rb_node z) {
    		rb_node y = z, x;
    		String y_original_color = y.color;
    		if (z.left == T_nil) {
    			x = z.right;
    			T = RB_TRANSPLANT(T, z, z.right);
    		} else if (z.right == T_nil) {
    			x = z.left;
    			T = RB_TRANSPLANT(T, z, z.left);
    		} else {
    			y = TREE_MINIMUM(z.right);
    			y_original_color = y.color;
    			x = y.right;
    			if (y.p == z) {
    				x.p = y;
    			} else {
    				T = RB_TRANSPLANT(T, y, y.right);
    				y.right = z.right;
    				y.right.p = y;
    			}
    			T = RB_TRANSPLANT(T, z, y);
    			y.left = z.left;
    			y.left.p = y;
    			y.color = z.color;
    		}
    		if (y_original_color == BLACK) {
    			T = RB_DELETE_FIXUP(T, x);
    		}
    		return T;
    	}
    
    	private static rb_node RB_DELETE_FIXUP(rb_node T, rb_node x) {
    		rb_node w = T_nil;
    		while (x != T && x.color == BLACK) {
    			if (x == x.p.left) {
    				w = x.p.right;
    				if (w.color == RED) {
    					w.color = BLACK;
    					x.p.color = RED;
    					T = LEFT_ROTATE(T, x.p);
    					w = x.p.right;
    				}
    				if (w.left.color == BLACK && w.right.color == BLACK) {
    					w.color = RED;
    					x = x.p;
    				} else {
    					if (w.right.color == BLACK) {
    						w.left.color = BLACK;
    						w.color = RED;
    						T = RIGHT_ROTATE(T, w);
    						w = x.p.right;
    					}
    					x.p.color = BLACK;
    					w.color = RED;
    					T = LEFT_ROTATE(T, x.p);
    					x = T;
    				}
    			} else {
    				w = x.p.left;
    				if (w.color == RED) {
    					w.color = BLACK;
    					x.p.color = RED;
    					T = RIGHT_ROTATE(T, x.p);
    					w = x.p.left;
    				}
    				if (w.left.color == BLACK && w.right.color == BLACK) {
    					w.color = RED;
    					x = x.p;
    				} else {
    					if (w.left.color == BLACK) {
    						w.right.color = BLACK;
    						w.color = RED;
    						T = LEFT_ROTATE(T, w);
    						w = x.p.left;
    					}
    					x.p.color = BLACK;
    					w.color = RED;
    					T = RIGHT_ROTATE(T, x.p);
    					x = T;
    				}
    			}
    
    		}
    		x.color = BLACK;
    		return T;
    	}
    
    	private static rb_node TREE_MINIMUM(rb_node z) {
    		while (z.left != T_nil) {
    			z = z.left;
    		}
    		return z;
    	}
    
    	private static rb_node RB_TRANSPLANT(rb_node T, rb_node u, rb_node v) {
    		if (u.p == T_nil) {
    			T = v;
    		} else if (u == u.p.left) {
    			u.p.left = v;
    		} else {
    			u.p.right = v;
    		}
    		v.p = u.p;
    		return T;
    	}
    
    	public rb_node selectNode(int key) {
    		rb_node temp = this.T;
    		while (temp != T_nil) {
    			if (temp.key > key) {
    				temp = temp.left;
    			} else if (temp.key < key) {
    				temp = temp.right;
    			} else {
    				return temp;
    			}
    		}
    		return temp;
    	}
    
    	public RB_Tree() {
    		T = T_nil;
    	}
    
    	public void preOrder(rb_node tree) {
    		if (tree != T_nil) {
    			System.out.print(tree.key + "->" + tree.color + "\t");
    			preOrder(tree.left);
    			preOrder(tree.right);
    		}
    	}
    
    	public void inOrder(rb_node tree) {
    		if (tree != T_nil) {
    			inOrder(tree.left);
    			System.out.print(tree.key + "->" + tree.color + "\t");
    			inOrder(tree.right);
    		}
    	}
    
    	public void postOrder(rb_node tree) {
    		if (tree != T_nil) {
    			postOrder(tree.left);
    			postOrder(tree.right);
    			System.out.print(tree.key + "," + tree.color);
    		}
    	}
    
    	public static void main(String[] args) {
    		String pre = "30 10 20 60 40 50 80 70 90 ";
    		String in = "10 20 30 40 50 60 70 80 90 ";
    		String post = "20 10 50 40 70 90 80 60 30 ";
    		RB_Tree RB = new RB_Tree();
    		// int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };
    		int a[] = { 41, 38, 31, 12, 19, 8 };
    		for (int i = 0; i < a.length; i++) {
    			rb_node z = new rb_node();
    			z.key = a[i];
    			RB.T = RB.RB_INSERT(RB.T, z);
    		}
    
    		RB.inOrder(RB.T);
    		System.out.println();
    		// 测试删除数据
    		rb_node z = RB.selectNode(38);
    		RB.T = RB.RB_DELETE(RB.T, z);
    		RB.inOrder(RB.T);
    	}
    
    }

在以上的两个版本中，都用了一个哨兵来标记叶子结点（即null结点）。

**参考资料**：  
算法导论  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51448271  
作者：WSYW12