二叉树和红黑树的java实现

二叉查找树代码大致如下：

 

二叉树节点类：

 

package RBTree;

public class BSTreeNode {
	int data;
	BSTreeNode lchild;
	BSTreeNode rchild;
}

 

二叉树的功能实现类：

package RBTree;

public class BSTree {
	BSTreeNode root = null;
//	插入节点
	public void InsertNode(BSTree T, int data) {
		BSTreeNode node = new BSTreeNode();
		BSTreeNode y = null, x;
		node.data = data;
		node.lchild = null;
		node.rchild = null;
		x = root;
		while (x != null) {
			y = x;
			if (x.data > node.data)
				x = x.lchild;
			else
				x = x.rchild;
		}
		if (y == null)
			T.root = node;
		else if (y.data > node.data)
			y.lchild = node;
		else
			y.rchild = node;
	}
// 查找
	public BSTreeNode SearchNode(BSTreeNode node, int data) {
		if (node == null)
			return null;
		else if (node.data == data) {
			// System.out.println(node.data);
			return node;
		} else if (node.data > data)
			return SearchNode(node.lchild, data);
		else
			return SearchNode(node.rchild, data);

	}
//打印二叉树
	public void BSTreedisplay(BSTreeNode t, int h) { 
		for (int k = 0; k < h; k++)
			System.out.print("   ");
		if (t == null) {
			System.out.print("Nil");
		} else {

			System.out.println("(" + t.data + ",");
			BSTreedisplay(t.lchild, h + 1);
			System.out.print(",");
			System.out.println();

			BSTreedisplay(t.rchild, h + 1);
			System.out.print(")");
			System.out.println();
			for (int k = 0; k < h - 1; k++)
				System.out.print("   ");

		}

	}
}

 

 

红黑树

红黑树节点类：

package RBTree;

public class RBTreeNode {
	
	    public int data;
	    public String color;
	    public RBTreeNode parent;
	    public RBTreeNode lchild;
	    public RBTreeNode rchild;
	    
	
}

 

 

红黑树功能类：

 

package RBTree;

public class RBTree {
	
	RBTreeNode nulNode = new RBTreeNode();
	RBTreeNode root =nulNode;
	public RBTree(){
	
		this.nulNode.color ="B";
		this.nulNode.data = -1;
		this.nulNode.lchild = nulNode;
		this.nulNode.rchild = nulNode;
		this.nulNode.parent = nulNode;
	}
	
//	插入一个节点
	public void RBTreeInsert(RBTree T,int  data){
		RBTreeNode x = T.root,y=nulNode;
		RBTreeNode node = new RBTreeNode();
		node.data = data;
		node.parent =null;
		node.lchild = null;
		node.rchild = null;
		node.color =null;
		while(x!=nulNode){
			y=x;
			if(node.data<x.data)
				x=x.lchild;
			else
				x=x.rchild;
		}
		node.parent = y;
		if(y==nulNode){
			root = node;
		}
		else if(node.data<y.data){
			y.lchild = node;
		}
		else{
			y.rchild = node;
		}
		node.color = "R";
		node.lchild =nulNode;
		node.rchild = nulNode;
		RBInsertFixup(T,node);
		//System.out.println("Insert"+node.data+"success");
		
	}
//	插入节点中的节点调整 包括颜色调整和左右旋
	public void RBInsertFixup(RBTree T, RBTreeNode node){
		RBTreeNode y= nulNode;
		while(node.parent.color =="R"){
			if(node.parent == node.parent.parent.lchild){
				y = node.parent.parent.rchild;
				if(y.color == "R"){
					node.parent.color ="B";
					y.color = "B";
					node.parent.parent.color ="R";
					node = node.parent.parent;
				}
				else{
					if(node == node.parent.rchild){
					node = node.parent;
					LeftRotate(T,node);	
					}
					node.parent.color = "B";
					node.parent.parent.color = "R";
					RightRotate(T,node.parent.parent);
				}
			}
			else{
				y = node.parent.parent.lchild;
				if(y.color == "R"){
					node.parent.color ="B";
					y.color = "B";
					node.parent.parent.color ="R";
					node = node.parent.parent;
				}
				else{
					if(node == node.parent.lchild){
					node = node.parent;
					RightRotate(T,node);	
					}
					node.parent.color = "B";
					node.parent.parent.color = "R";
					LeftRotate(T,node.parent.parent);
				}
			}
		}
		
		T.root.color = "B";
	}
//	左旋
	private void LeftRotate(RBTree t, RBTreeNode node) {
		// TODO Auto-generated method stub
		RBTreeNode y;
		y = node.rchild;
		node.rchild = y.lchild;
		if(y.lchild !=nulNode){
			y.lchild.parent = node;
		}
		y.parent = node.parent;
		
		if(node.parent == nulNode){
			t.root =y;
		}
		else if(node == node.parent.lchild){
			node.parent.lchild = y;
		}
		else{
			node.parent.rchild = y;
		}
		
		y.lchild = node;
		node.parent = y;
		
	}
// 右旋	
	private void RightRotate(RBTree t, RBTreeNode node) {
		// TODO Auto-generated method stub
		RBTreeNode y;
		y = node.lchild;
		node.lchild = y.rchild;
		if(y.rchild !=nulNode){
			y.rchild.parent = node;
		}
		y.parent = node.parent;
		
		if(node.parent == nulNode){
			t.root =y;
		}
		else if(node == node.parent.lchild){
			node.parent.lchild = y;
		}
		else{
			node.parent.rchild = y;
		}
		
		y.rchild = node;
		node.parent = y;
	}
//	查找节点
	public RBTreeNode RBTreeSearch(RBTreeNode t, int z){
		
		if(t == nulNode){
			System.out.println("没有找到");	
			return nulNode;
		}
		else if(t.data == z)
				//System.out.println(y.data);
			return t;
				
			
		else if(t.data>z)
			return RBTreeSearch(t.lchild,z);
			
		else
			return RBTreeSearch(t.rchild,z);
			
		
	
	}
//	删除节点
	public RBTreeNode RBDelete(RBTree T,RBTreeNode node){
		RBTreeNode y,x;
		if(node.lchild ==nulNode || node.rchild ==nulNode)
			y = node;
		else
			y = TreeSuccessor(node);
		
		if(y.lchild !=nulNode)
			x = y.lchild;
		else
			x =y.rchild;
		x.parent = y.parent;
		if(y.parent == nulNode)
			T.root = node;
		
		else if(y==y.parent.lchild)
			y.parent.lchild = x;
		else
			y.parent.rchild = x;
		
		if(y != node){
			node.data = y.data;
		}
		
		if(y.color == "B"){
			RBDeleteFixup(T,x);
		}
		
		return y;
		
	}
//	删除的调整
	private void RBDeleteFixup(RBTree t, RBTreeNode x) {
		RBTreeNode w;
		while(x!=t.root && x.color =="B"){
			if(x == x.parent.lchild){
					w = x.parent.rchild;
					if(w.color =="R"){
						w.color = "B";
						w.parent.color ="R";
						LeftRotate( t, x.parent);
						w = x.parent.rchild;
					}
				
					if(w.lchild.color == "B" && w.rchild.color == "B"){
						w.color ="R";
						x= x.parent;
					}
					else{ 
						if(w.rchild.color =="B"){
							w.lchild.color ="R";
							w.color = "B";
							RightRotate(t,x);
							w=x.parent.rchild;
						}
				
						w.color = x.parent.color;
						x.parent.color = "B";
						w.rchild.color ="B";
						LeftRotate( t, x.parent);
						x = t.root;
					}
				}
			else{
				w = x.parent.lchild;
				if(w.color =="R"){
					w.color = "B";
					w.parent.color ="R";
					LeftRotate( t, x.parent);
					w = x.parent.rchild;
				}
			
				if(w.lchild.color == "B" && w.rchild.color == "B"){
					w.color ="R";
					x= x.parent;
				}
				else{ 
					if(w.rchild.color =="B"){
						w.lchild.color ="R";
						w.color = "B";
						LeftRotate(t,x);
						w=x.parent.rchild;
					}
			
					w.color = x.parent.color;
					x.parent.color = "B";
					w.rchild.color ="B";
					RightRotate( t, x.parent);
					x = t.root;
				}
			}
		}
		x.color = "B";
	}
	private RBTreeNode TreeSuccessor(RBTreeNode node) {
		RBTreeNode y;
		if(node.rchild!=nulNode)
			return TreeMin(node.rchild);
		y = node.parent;
		while(y!=nulNode&&node == y.rchild){
			node = y;
			y=y.parent;
		}
		return y;
	}
	private RBTreeNode TreeMin(RBTreeNode node) {
		while(node.rchild!=nulNode)
				node =node.rchild;
		return node;
	}
	
	public int RBTreeBlackHeight(RBTreeNode t){
		if(t ==nulNode)
			return 1;
		else
			return 1+RBTreeBlackHeight(t.lchild);
	}
//	打印红黑树
	public void RBTreedisplay(RBTreeNode t,int h){		  
		
		for(int k = 0;k<h;k++)
			System.out.print("   ");
		if(t == nulNode){
				System.out.print("Nil");
		}
		else {
		
			System.out.println("("+t.data+t.color+",");
			RBTreedisplay(t.lchild,h+1);
			System.out.println(",");
			
		
			RBTreedisplay(t.rchild,h+1);
			System.out.println(")");
			
			for(int k = 0;k<h-1;k++)
				System.out.print("   ");
			
		}
	}
}

扩展红黑树：

节点类：

package RBTree;

public class ExRBTreeNode {

    public int data;
    public String color;
    public ExRBTreeNode parent;
    public ExRBTreeNode lchild;
    public ExRBTreeNode rchild;
    public int size;
}

 功能类：

package RBTree;

public class ExRBTree {

	ExRBTreeNode nulNode = new ExRBTreeNode();
	ExRBTreeNode root =nulNode;
	public ExRBTree(){
	
		this.nulNode.color ="B";
		this.nulNode.data = -1;
		this.nulNode.lchild = nulNode;
		this.nulNode.rchild = nulNode;
		this.nulNode.parent = nulNode;
	}
	
	
	public void ExRBTreeInsert(ExRBTree T,int  data){
		ExRBTreeNode x = T.root,y=nulNode;
		ExRBTreeNode node = new ExRBTreeNode();
		node.data = data;
		node.parent =null;
		node.lchild = null;
		node.rchild = null;
		node.color =null;
		node.size =0;
		while(x!=nulNode){
			y=x;
			if(node.data<x.data)
				x=x.lchild;
			else
				x=x.rchild;
		}
		node.parent = y;
		if(y==nulNode){
			root = node;
		}
		else if(node.data<y.data){
			y.lchild = node;
		}
		else{
			y.rchild = node;
		}
		node.color = "R";
		node.lchild =nulNode;
		node.rchild = nulNode;
		ExRBInsertFixup(T,node);
		//System.out.println("Insert"+node.data+"success");
		
	}
	public void ExRBInsertFixup(ExRBTree T, ExRBTreeNode node){
		ExRBTreeNode y= nulNode;
		while(node.parent.color =="R"){
			if(node.parent == node.parent.parent.lchild){
				y = node.parent.parent.rchild;
				if(y.color == "R"){
					node.parent.color ="B";
					y.color = "B";
					node.parent.parent.color ="R";
					node = node.parent.parent;
				}
				else{
					if(node == node.parent.rchild){
					node = node.parent;
					LeftRotate(T,node);	
					}
					node.parent.color = "B";
					node.parent.parent.color = "R";
					RightRotate(T,node.parent.parent);
				}
			}
			else{
				y = node.parent.parent.lchild;
				if(y.color == "R"){
					node.parent.color ="B";
					y.color = "B";
					node.parent.parent.color ="R";
					node = node.parent.parent;
				}
				else{
					if(node == node.parent.lchild){
					node = node.parent;
					RightRotate(T,node);	
					}
					node.parent.color = "B";
					node.parent.parent.color = "R";
					LeftRotate(T,node.parent.parent);
				}
			}
		}
		
		T.root.color = "B";
	}
	
	private void LeftRotate(ExRBTree t, ExRBTreeNode node) {
		// TODO Auto-generated method stub
		ExRBTreeNode y;
		y = node.rchild;
		node.rchild = y.lchild;
		if(y.lchild !=nulNode){
			y.lchild.parent = node;
		}
		y.parent = node.parent;
		
		if(node.parent == nulNode){
			t.root =y;
		}
		else if(node == node.parent.lchild){
			node.parent.lchild = y;
		}
		else{
			node.parent.rchild = y;
		}
		
		y.lchild = node;
		node.parent = y;
		
	}
	
	private void RightRotate(ExRBTree t, ExRBTreeNode node) {
		// TODO Auto-generated method stub
		ExRBTreeNode y;
		y = node.lchild;
		node.lchild = y.rchild;
		if(y.rchild !=nulNode){
			y.rchild.parent = node;
		}
		y.parent = node.parent;
		
		if(node.parent == nulNode){
			t.root =y;
		}
		else if(node == node.parent.lchild){
			node.parent.lchild = y;
		}
		else{
			node.parent.rchild = y;
		}
		
		y.rchild = node;
		node.parent = y;
	}
	
	public int ExRBTreeGetSize(ExRBTreeNode t){
		
		if(t ==nulNode){
			return 0;
		}
		else
			return 1+ExRBTreeGetSize(t.lchild)+ExRBTreeGetSize(t.rchild);
		
	}
	
public ExRBTreeNode ExRBTreeSearch(ExRBTreeNode t, int z){
		
		if(t == nulNode){
			System.out.println("没有找到");	
			return nulNode;
		}
		else if(t.data == z)
				//System.out.println(y.data);
			return t;
				
			
		else if(t.data>z)
			return ExRBTreeSearch(t.lchild,z);
			
		else
			return ExRBTreeSearch(t.rchild,z);
		
	}
	
	public void SetExRBTreeSize(ExRBTree T,int data){
		
		ExRBTreeNode t = ExRBTreeSearch(T.root,data);
		t.size =ExRBTreeGetSize(t);
		
	}
	
	public int ExRBTreeGetRank(ExRBTree T,int data){
		ExRBTreeNode y;
		ExRBTreeNode t = ExRBTreeSearch(T.root,data);//找到该值对应的节点
		int r = t.lchild.size+1;
		y = t;
		while(y!=T.root){
			if(y ==y.parent.rchild)
				r = r+y.parent.lchild.size+1;
			y = y.parent;	
		}
		return r;
	}
	
public void ExRBTreedisplay(ExRBTreeNode t,int h){		
		
		for(int k = 0;k<h;k++)
			System.out.print("    ");
		if(t == nulNode){
				System.out.print("Nil");
		}
		else {
		
			System.out.println("("+t.data+t.color+t.size+",");
			ExRBTreedisplay(t.lchild,h+1);
			System.out.println(",");
			
		
			ExRBTreedisplay(t.rchild,h+1);
			System.out.println(")");
			
			for(int k = 0;k<h-1;k++)
				System.out.print("    ");
			
		}
	}
}

 

 

 

测试主类：

package RBTree;

import java.util.ArrayList;

public class RBTreeTest {

	public static void main(String args[]) {
		RBTree T1 = new RBTree();
		RBTree T = new RBTree();
		BSTree BT = new BSTree();

		// 插入要求的数组
		int arr[] = { 8, 11, 17, 15, 6, 1, 22, 25, 27 };
		for (int i = 0; i < arr.length; i++)
			T1.RBTreeInsert(T1, arr[i]);
		System.out.println("插入{8,11,17,15,6,1,22,25,27}后红黑树如下");
		T1.RBTreedisplay(T1.root, 0);// 打印树
		int bh = T1.RBTreeBlackHeight(T1.root);// 获取黑高度
		System.out.println("T1黑高度为" + bh);

		// 删除15元素后得到树并打印
		RBTreeNode q = null;
		q = T1.RBDelete(T1, T1.RBTreeSearch(T1.root, 15));
		System.out.println("删除的节点信息为" + q.data + q.color + "， 删除后树形如下：");
		T1.RBTreedisplay(T1.root, 0);// 打印树
		bh = T1.RBTreeBlackHeight(T1.root);// 获取黑高度
		System.out.println("删除节点15后，T1黑高度为" + bh);

		// 随机生成1-300000个不同的数值 分别插入二叉树BT与红黑树T 比较查找15000的时间代价
		ArrayList arrlist = new ArrayList();
		for (int i = 0; i < 300000; i++)
			arrlist.add(i + 1);

		for (int i = 0; i < 300000; i++) {
			int temp = (int) (Math.random() * arrlist.size());
			int data = (Integer) arrlist.remove(temp);
			T.RBTreeInsert(T, data);
			BT.InsertNode(BT, data);
		}
		// 二叉树中查找15000节点
		BSTreeNode p = null;
		long time = System.nanoTime();
		;
		p = BT.SearchNode(BT.root, 15000);
		long span = System.nanoTime() - time;
		System.out.println(p.data);
		long b = System.currentTimeMillis();
		System.out.println("二叉树查找时间为：" + span + "纳秒");
		// 红黑树中查找15000节点
		time = System.nanoTime();
		q = T.RBTreeSearch(T.root, 15000);
		span = System.nanoTime() - time;
		System.out.println(q.data + q.color);
		System.out.println("红黑树查找时间为：" + span + "纳秒");

		// 输出秩 为此建立了扩展红黑树ExRBTree
		ExRBTree T2 = new ExRBTree();
		int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
		for (int i = 0; i < arr1.length; i++)
			T2.ExRBTreeInsert(T2, arr1[i]);
		System.out.println("插入{1,2,3,4,5,6,7,8}后红黑树如下【格式为数据值 、节点颜色、size域】");
		for (int i = 0; i < arr1.length; i++)
			T2.SetExRBTreeSize(T2, arr1[i]);
		T2.ExRBTreedisplay(T2.root, 0);
		int k = T2.ExRBTreeGetRank(T2, 6);
		System.out.println("key值为6的rank为：" + k);

	}
}

 PS:很久以前自己写的代码了，这里整理了一下，搬到博客来，其中功能不是很完整，比如二叉树就没有写删除功能。