红黑树实现（Java语言）

冷不防 2022-04-22 03:56 159阅读 0赞

最近在看红黑树，也想自己写程序实现一下，因为红黑树的删除还没有看，所以程序中并没有包含删除操作，等看完了再补上，呵呵。。。

至于红黑树的原理我就不多说了，我是参考<算法导论>中的伪代码写的程序。

代码实现如下：

运行结果如下所示：

2 Black
    
    2 Black
    5 Red
    
    2 Red
    3 Black
    5 Red
    
    2 Black
    3 Black
    4 Red
    5 Black
    
    1 Red
    2 Black
    3 Black
    4 Red
    5 Black
    
    0 Red
    1 Black
    2 Red
    3 Black
    4 Red
    5 Black

从运行结果可以看出程序是没有问题的。有改进的地方大家可以提啊，谢谢！

今天看了看算法导论中关于红黑树删除的有关知识，自己实现了一下，现添加到上面的程序中，程序代码和运行结果如下所示，我是严格按照算法导论的伪代码写的，相信大家可以看得很清楚。

package com.datastructure.tree;
    
    public class MyRbTree {
    
    	RbTreeNode root=null;
    	RbTreeNode nilNode=null;
    	
    	public RbTreeNode getRoot() {
    		return root;
    	}
    	
    	public MyRbTree()
    	{
    		this.nilNode=new RbTreeNode(-1);
    		this.nilNode.color=TreeNodeColor.Black;
    		this.nilNode.left=null;
    		this.nilNode.right=null;
    		this.nilNode.parent=null;
    		this.root=this.nilNode;
    	}
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		MyRbTree mytree=new MyRbTree();
    		int[] array={41,38,31,12,19,8};
    		for(int i=0;i<array.length;i++)
    		{
    			System.out.println("插入"+array[i]);
    			mytree.insert(array[i]);
    			mytree.preorder(mytree.getRoot());
    			System.out.println();
    		}
    		for(int i=5;i>=0;i--)
    		{
    			System.out.println("删除"+array[i]);
    			mytree.delete(array[i]);
    			mytree.preorder(mytree.getRoot());
    			System.out.println();
    		}
    		
    	}
    	
    	private void leftRotate(MyRbTree tree,RbTreeNode x)
    	{
    		RbTreeNode y=x.right;
    		x.right=y.left;
    		y.left.parent=x;
    		y.parent=x.parent;
    		if(x.parent==this.nilNode)
    		{
    			tree.root=y;
    		}else
    		{
    			if(x==x.parent.left)
    				x.parent.left=y;
    			else
    				x.parent.right=y;
    		}
    		y.left=x;
    		x.parent=y;
    	}
    	
    	private void rightRotate(MyRbTree tree,RbTreeNode y)
    	{
    		RbTreeNode x=y.left;
    		y.left=x.right;
    		x.right.parent=y;
    		x.parent=y.parent;
    		if(y.parent==this.nilNode)
    		{
    			tree.root=x;
    		}else
    		{
    			if(y==y.parent.left)
    				y.parent.left=x;
    			else
    				y.parent.right=x;
    		}
    		x.right=y;
    		y.parent=x;
    	}
    	
    	private void insert(MyRbTree tree,int value)
    	{
    		RbTreeNode y=this.nilNode;
    		RbTreeNode x=tree.root;
    		RbTreeNode z=new RbTreeNode(value);
    		
    		while(x!=this.nilNode)
    		{
    			y=x;
    			if(value<x.key)
    				x=x.left;
    			else
    				x=x.right;
    		}
    		z.parent=y;
    		if(y==this.nilNode)
    		{
    			tree.root=z;
    		}else
    		{
    			if(value<y.key)
    			{
    				y.left=z;
    			}
    			else
    			{
    				y.right=z;
    			}
    		}
    		z.left=this.nilNode;
    		z.right=this.nilNode;
    		
    		insertFixUp(tree,z);
    		
    	}
    	
    	public void insert(int value)
    	{
    		insert(this,value);
    	}
    	
    	private RbTreeNode search(MyRbTree tree,int value)
    	{
    		RbTreeNode node=tree.root;
    		while((node!=tree.nilNode)&&(node.key!=value))
    		{
    			if(value<node.key)
    			{
    				node=node.left;
    			}else
    			{
    				node=node.right;
    			}
    		}
    		return node;
    	}
    	
    	public boolean search(int value)
    	{
    		if(search(this,value)!=this.nilNode)
    			return true;
    		else
    			return false;
    	}
    	
    	public RbTreeNode minimum(RbTreeNode x)
    	{
    		while(x.left!=this.nilNode)
    		{
    			x=x.left;
    		}
    		return x;
    	}
    	
    	
    	
    	public RbTreeNode successor(RbTreeNode x)
    	{
    		if(x.right!=this.nilNode)
    		{
    			return minimum(x.right);
    		}
    		RbTreeNode y=x.parent;
    		while(y!=this.nilNode&&x==y.right)
    		{
    			x=y;
    			y=y.parent;
    		}
    		return y;
    	}
    	
    	private boolean delete(MyRbTree tree,int value)
    	{
    		RbTreeNode z=search(tree,value);
    		if(z==tree.nilNode)
    		{
    			return false;
    		}
    		RbTreeNode y=null;
    		if(z.left==tree.nilNode||z.right==tree.nilNode)
    		{
    			y=z;
    		}else
    		{
    			y=successor(z);
    		}
    		RbTreeNode x=null;
    		if(y.left!=tree.nilNode)
    		{
    			x=y.left;
    		}else
    		{
    			x=y.right;
    		}
    		x.parent=y.parent;
    		if(y.parent==tree.nilNode)
    		{
    			this.root=x;
    		}else
    		{
    			if(y==y.parent.left)
    			{
    				y.parent.left=x;
    			}else
    			{
    				y.parent.right=x;
    			}
    		}
    		if(y!=z)
    		{
    			z.key=y.key;
    		}
    		if(y.color==TreeNodeColor.Black)
    		{
    			deleteFixUp(tree,x);
    		}
    		return true;
    	}
    	
    	private void deleteFixUp(MyRbTree tree,RbTreeNode x)
    	{
    		while(x!=tree.root&&x.color==TreeNodeColor.Black)
    		{
    			if(x==x.parent.left)
    			{
    				RbTreeNode w=x.parent.right;
    				if(w.color==TreeNodeColor.Red)
    				{
    					w.color=TreeNodeColor.Black;
    					x.color=TreeNodeColor.Red;
    					leftRotate(tree,x.parent);
    					w=x.parent.right;
    				}
    				if(w.left.color==TreeNodeColor.Black&&w.right.color==TreeNodeColor.Black)
    				{
    					w.color=TreeNodeColor.Red;
    					x=x.parent;
    				}else
    				{
    					if(w.right.color==TreeNodeColor.Black)
    					{
    						w.left.color=TreeNodeColor.Black;
    						w.color=TreeNodeColor.Red;
    						rightRotate(tree,w);
    						w=x.parent.right;
    					}
    					w.color=x.parent.color;
    					x.parent.color=TreeNodeColor.Black;
    					w.right.color=TreeNodeColor.Black;
    					leftRotate(tree,x.parent);
    					x=tree.root;
    				}
    			}else
    			{
    				RbTreeNode w=x.parent.left;
    				if(w.color==TreeNodeColor.Red)
    				{
    					w.color=TreeNodeColor.Black;
    					x.color=TreeNodeColor.Red;
    					rightRotate(tree,x.parent);
    					w=x.parent.left;
    				}
    				if(w.left.color==TreeNodeColor.Black&&w.right.color==TreeNodeColor.Black)
    				{
    					w.color=TreeNodeColor.Red;
    					x=x.parent;
    				}else
    				{
    					if(w.left.color==TreeNodeColor.Black)
    					{
    						w.right.color=TreeNodeColor.Black;
    						w.color=TreeNodeColor.Red;
    						leftRotate(tree,w);
    						w=x.parent.left;
    					}
    					w.color=x.parent.color;
    					x.parent.color=TreeNodeColor.Black;
    					w.left.color=TreeNodeColor.Black;
    					leftRotate(tree,x.parent);
    					x=tree.root;
    				}
    			}
    		}
    		x.color=TreeNodeColor.Black;
    	}
    	
    	public boolean delete(int value)
    	{
    		return delete(this,value);
    	}
    	
    	private void insertFixUp(MyRbTree tree,RbTreeNode z)
    	{
    		while(z.parent.color==TreeNodeColor.Red)
    		{
    			if(z.parent==z.parent.parent.left)
    			{
    				RbTreeNode uncle=z.parent.parent.right;
    				if(uncle.color==TreeNodeColor.Red)
    				{
    					z.parent.color=TreeNodeColor.Black;
    					uncle.color=TreeNodeColor.Black;
    					z.parent.parent.color=TreeNodeColor.Red;
    					z=z.parent.parent;
    				}else
    				{
    					if(z==z.parent.right)
    					{
    						z=z.parent;
    						leftRotate(tree,z);
    					}
    					z.parent.color=TreeNodeColor.Black;
    					z.parent.parent.color=TreeNodeColor.Red;
    					rightRotate(tree,z.parent.parent);
    				}
    			}else if(z.parent==z.parent.parent.right)
    			{
    				RbTreeNode uncle=z.parent.parent.left;
    				if(uncle.color==TreeNodeColor.Red)
    				{
    					z.parent.color=TreeNodeColor.Black;
    					uncle.color=TreeNodeColor.Black;
    					z.parent.parent.color=TreeNodeColor.Red;
    					z=z.parent.parent;
    				}else
    				{
    					if(z==z.parent.left)
    					{
    						z=z.parent;
    						rightRotate(tree,z);
    					}
    					z.parent.color=TreeNodeColor.Black;
    					z.parent.parent.color=TreeNodeColor.Red;
    					leftRotate(tree,z.parent.parent);
    				}
    				
    			}
    		}
    		tree.root.color=TreeNodeColor.Black;
    		
    	}
    	
    	public void preorder(RbTreeNode root)
    	{
    		if(root!=null)
    		{
    			preorder(root.left);
    			getNodeInfo(root);
    			preorder(root.right);
    		}
    	}
    	
    	public void getNodeInfo(RbTreeNode node)
    	{
    		if(node!=this.nilNode)
    		{
    			System.out.println(node.key+" "+node.color.toString());
    		}
    	}
    	
    	
    }
    
    class RbTreeNode{
    	TreeNodeColor color=TreeNodeColor.Red;
    	int key=-1;
    	RbTreeNode left=null;
    	RbTreeNode right=null;
    	RbTreeNode parent=null;
    	
    	public RbTreeNode(int value)
    	{
    		this.key=value;
    	}
    }

运行结果如下所示：

插入41
    41 Black
    
    插入38
    38 Red
    41 Black
    
    插入31
    31 Red
    38 Black
    41 Red
    
    插入12
    12 Red
    31 Black
    38 Black
    41 Black
    
    插入19
    12 Red
    19 Black
    31 Red
    38 Black
    41 Black
    
    插入8
    8 Red
    12 Black
    19 Red
    31 Black
    38 Black
    41 Black
    
    删除8
    12 Black
    19 Red
    31 Black
    38 Black
    41 Black
    
    删除19
    12 Red
    31 Black
    38 Black
    41 Black
    
    删除12
    31 Black
    38 Black
    41 Black
    
    删除31
    38 Black
    41 Red
    
    删除38
    41 Black
    
    删除41

我自己用纸也画了下插入和删除的红黑树图，跟运行的结果中每个节点的颜色都是吻合的，个人觉得是没有什么问题的，如果有什么问题，欢迎讨论，谢谢....