2012年4月25日---红黑树的现实和操作

出去流浪了一段时间，现在我又回来了，内容继续更新，算法继续学习。

在最近看的是红黑树，而且在这里停留了很久，因为总是遇到NullPointerException的问题，每天都在对程序进行调试，今天终于搞定了。这里先插入出现NullPointerException的情形：

/* * 红黑树的java实现 * @version 1.0 2012/4/25 * @author akon */package com.akon405.www;public class RBTree {RBTreeNode  nullNode=new RBTreeNode();//定义空节点RBTreeNode RBTreeRoot=nullNode;//定义一个根节点//初始化空节点nullNodepublic void init(){nullNode.data=0;nullNode.color=null;nullNode.left=nullNode;nullNode.right=nullNode;nullNode.parent=nullNode;}//中序遍历红黑树操作（中序遍历之后便可以排序成功）public void inOrderRBTree(RBTreeNode x){if(x!=nullNode){inOrderRBTree(x.left);//先遍历左子树System.out.print(x.data+",");//打印中间节点inOrderRBTree(x.right);//最后遍历右子树}}//红黑树的插入操作public void insert(RBTree T,RBTreeNode k){RBTreeNode x=T.RBTreeRoot;RBTreeNode y=nullNode;RBTreeNode node=new RBTreeNode();node=k;while(x!=nullNode){//while语句可以找到k节点所要插入的位置的父亲节点yy=x;if(x.data>node.data){x=x.left;}else{x=x.right;}}node.parent=y;if(y==nullNode){//二叉查找树为空树的情况下，直接插入到根节点，这里的y为已知的k的父亲节点T.RBTreeRoot=node;}else if(node.data<y.data){//插入到父亲节点y的左边y.left=node;}else{//插入到父亲节点y的右边y.right=node;}node.left=nullNode;//叶节点的子树须为nullnode.right=nullNode;node.color="red";//red代表红色（插入红色的结点，因为这样可以在插入过程中尽量避免对树的调整）insertFixup(node);//为了保证插入节点之后依然满足红黑树的性质，这里创建一个修复函数对红黑树的节点重新着色并旋转}//插入修复函数(颜色的调整，左旋，右旋)private void insertFixup(RBTreeNode k) {RBTreeNode y=nullNode;while(k.parent.color=="red"){//插入节点k的父亲节点为红色的情况下（因为插入的节点是红色节点，所以它的父亲节点必须为黑色）if(k.parent==k.parent.parent.left){//(1)k父亲节点为其父亲节点的左孩子y=k.parent.parent.right;//y的k的叔父节点if(y.color=="red"){//case 1（k的叔父节点为红色）k.parent.color="black";//k的父亲节点置为黑y.color="black";k.parent.parent.color="red";k=k.parent.parent;}else{//case 2（k的叔父节点为黑色）if(k==k.parent.right){//k为右孩子节点k=k.parent;leftRotate(k);}k.parent.color="black";k.parent.parent.color="red";rightRotate(k);}}else{//(2)k父亲节点为其父亲节点的右孩子,操作和前面(1)k父亲节点为其父亲节点的左孩子一样y=k.parent.parent.left;if(y.color=="red"){//case 1k.parent.color="black";y.color="black";k.parent.parent.color="red";k=k.parent.parent;}else{//case 2if(k==k.parent.right){k=k.parent;rightRotate(k);}k.parent.color="black";k.parent.parent.color="red";leftRotate(k);}}}RBTreeRoot.color="black";}//红黑树的删除操作public void delete(RBTreeNode x){//三种情况的节点RBTreeNode y;//y为真实删除的节点（x不一定是真实被删除的节点）//下面的if..else便可确定节点y（y为x节点或者为x的后继节点）if(x.left==nullNode||x.right==nullNode){y=x;}else{y=successor(x);}//把x置为y的非空孩子节点if(y.left!=nullNode){x=y.left;}else{x=y.right;}//删除y节点x.parent=y.parent;if(y.parent==nullNode){RBTreeRoot=x;}else if(y==y.parent.left){y.parent.left=x;}else{y.parent.left=x;}if(y!=x){x.data=y.data;}if(y.color=="black"){//修复红黑树（删除节点为红色的时候不影响红黑树的性质）deleteFixup(x);}}//删除修复函数public void deleteFixup(RBTreeNode x){RBTreeNode y;while(x!=RBTreeRoot&&x.color=="black"){if(x==x.parent.left){//x为其父亲节点的左孩子节点y=x.parent.right;//x的兄弟节点yif(y.color=="red"){//x的兄弟节点y为红色//第一种情况--x的兄弟节点y为红色y.color="black";y.parent.color="red";rightRotate(x.parent);y=x.parent.right;}else{//x的兄弟节点y为黑色if(y.left.color=="black"&&y.right.color=="black"){//第二种情况--x的兄弟节点y为黑色，y的孩子节点均为黑色y.color="red";x=x.parent;}else if(y.right.color=="black"&&y.left.color=="red"){//第三种情况--x的兄弟节点y为黑色，y的右孩子节点是黑色，左孩子是红色y.left.color="red";y.color="black";leftRotate(x);y=x.parent.right;}else if(y.right.color=="red"){//第四种情况--x的兄弟节点y为黑色，y的右孩子节点为红色y.color=x.parent.color;x.parent.color="black";y.right.color="black";leftRotate(x);x=RBTreeRoot;}}}else{//同样，原理一致，只是遇到左旋改为右旋，遇到右旋改为左旋，即可。其它代码不变。y=x.parent.left;//x的兄弟节点if(y.color=="red"){y.color="black";y.parent.color="red";rightRotate(x.parent);y=x.parent.right;}else{if(y.left.color=="black"&&y.right.color=="black"){y.color="red";x=x.parent;}else if(y.right.color=="black"&&y.left.color=="red"){y.left.color="red";y.color="black";leftRotate(x);y=x.parent.right;}else if(y.right.color=="red"){y.color=x.parent.color;x.parent.color="black";y.right.color="black";rightRotate(x);x=RBTreeRoot;}}}}x.color="black";}//查找节点的后继节点public RBTreeNode successor(RBTreeNode x){if(x.right!=nullNode){return searchMinNode(x.right);//右子树的最小值}RBTreeNode y=x.parent;while(y!=nullNode&&x==y.right){//向上找到最近的一个节点，其父亲节点的左子树包涵了当前节点或者其父亲节点为空x=y;y=y.parent;}return y;}//查找最小节点public RBTreeNode searchMinNode(RBTreeNode x){while(x.left!=nullNode){x=x.left;}return x;}//从r节点开始查找x节点public RBTreeNode search(RBTreeNode r,RBTreeNode x){if(r==nullNode||r.data==x.data){return r;}if(x.data<r.data){return search(r.left,x);}else{return search(r.right,x);}}//红黑树的左旋操作（选择的节点必须右孩子节点不为空）public void leftRotate(RBTreeNode x){//左旋分为三个步骤，每个步骤有两个操作，因为每个节点既有孩子节点又有父亲节点RBTreeNode y=x.right;//把x节点的右孩子节点赋给我们定义的y节点//第一步,y的左孩子节点转变为x的右孩子节点x.right=y.left;y.right.parent=x;//第二步,把x的父亲节点转变为y的父亲节点y.parent=x.parent;if(x.parent==nullNode){//x为根节点的情况下RBTreeRoot=y;}else if(x==x.parent.left){//x的父亲节点不为空并且x为其父亲节点的左孩子节点x.parent.left=y;}else{//x的父亲节点不为空并且x为其父亲节点的右孩子节点x.parent.right=y;}//第三步,把x节点转变为y的左孩子节点y.left=x;x.parent=y;//左旋完成}//红黑树的右旋操作（选择的节点必须左孩子节点不为空）public void rightRotate(RBTreeNode x){//右旋和左旋步骤基本一样，也分为三个步骤RBTreeNode y=x.left;//第一步，把y的右孩子节点转变为x的左孩子节点x.left=y.right;y.left.parent=x;//第二步，把x的父亲节点转变为y的父亲节点y.parent=x.parent;if(x.parent==nullNode){RBTreeRoot=y;}else if(x.parent.left==x){x.parent.left=y;}else{x.parent.right=y;}//第三步，把x节点转变为y的左孩子节点y.left=x;x.parent=y;//右旋完成}/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubint[] A={20,8,16,34,73,17,32,89};RBTree rb=new RBTree();rb.init();//通过循环插入构造红黑树for(int i=0;i<A.length;i++){RBTreeNode x=new RBTreeNode();x.data=A[i];x.color=null;x.left=rb.nullNode;x.right=rb.nullNode;x.parent=rb.nullNode;rb.insert(rb,x);}rb.inOrderRBTree(rb.RBTreeRoot);//中序遍历红黑树}}//红黑树的节点类class RBTreeNode{int data;String color;RBTreeNode left;RBTreeNode right;RBTreeNode parent;}

结果：17,32,34,73,89,

?

?