红黑树实验报告

红黑树实验报告一、红黑树特点简介红黑树（Red-BlackTree）是二叉搜索树（BinarySearchTree）的一种。二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。这种低效产生的原因是树没有维持一定的平衡性，要提高搜索效率，就要想办法来维持树左边的平衡，也就是要尽时降低树的高度，可行的做法就是用一些策略在每次修改树的内容之后都调整树的结构，使之满足一定的平衡条件。其中一种满足一定平衡条件而且目前应用广泛的是红黑树。它可以在每一次插入或删除节点之后都会花O（logN）的时间来对树的结构作修改，以保持树的平衡。而红黑树的查找方法与二叉搜索树完全一样，也能够在O(logN)时间上完成。而红黑树的插入和删除节点的的方法只是在原二叉搜索树搜索和删除算法之后经过一定的过程来维持红黑树的性质不变。红黑树的每个节点上的属性除了有一个key、3个指针：parent、left、right以外，还多了一个属性：color。它只能是两种颜色：红或黑,当然也可以再加一些以key来索引的数据。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下5点性质：1.每个节点是黑色的或是红色的。2.根节点是黑色的。3.空节点是黑色的（红黑树中，根节点的parent以及所有叶节点left、right都不指向NULL，而是指向一个定义好的空节点,这样可以保持算法的一致性，简化算法）。4.红色节点的父、左子、右子节点都是黑色。5.在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。二、红黑树构造过程为了满足上述5条规则，在进行节点插入时需要进行如下操作；先按二叉搜索树规则进行插入，之后进行调整。分为5种调整情况：case1，case2，case3，case4，case5；Case1：若插入的是根节点，则不作操作，完成调整。否则转入case2；Case2：若插入节点是黑色节点，则不作操作，完成调整。否则转入case3；Case3：若插入的节点的叔叔节点是红色，则更改叔父两节点颜色为黑色，置插入点为祖父节点，之后进入case1。否则转入case4；Case4：若插入节点、父节点和祖父节点不在同一条直线，以父为轴进行一次旋转，使节点、父节点和祖父节点在同一条直线。否则进入case5；Case5：以祖父为轴进行一次旋转，并且更改祖父节点为红色，父节点为红色。三、红黑树代码注：仅实现插入操作和存储读取操作1.TextMain.java/**Author:BYC*Number:71110214*Date:2012-5-20*/importjava.io.File;importjava.io.FileInputStream;importjava.io.FileOutputStream;importjava.io.IOException;importjava.io.ObjectInputStream;importjava.io.ObjectOutputStream;importjava.util.Random;publicclassTestMain{publicstaticvoidmain(String[]args)throwsIOException{inti=0;longstartCon=System.currentTimeMillis();RedBlackTreerbt=newRedBlackTree();Randomrandom=newRandom();intrandomNum=0;//Insertonemillionnumberswhile(i=500000){randomNum=random.nextInt(10000000);rbt.insertNode(randomNum);i++;}longendCon=System.currentTimeMillis();System.out.println(ConstructOver!Time:);System.out.println((newDouble(endCon-startCon))/1000);//SavetheObjectlongstartSave=System.currentTimeMillis();FilefilePath=newFile(E:/tree.tmp);FileOutputStreamfileOut=newFileOutputStream(filePath);ObjectOutputStreamobjectOut=newObjectOutputStream(fileOut);objectOut.writeObject(rbt);objectOut.close();fileOut.close();longendSave=System.currentTimeMillis();System.out.println(saveOver!Time:);System.out.println((newDouble(endSave-startSave))/1000);//readObjectlongstartRead=System.currentTimeMillis();FileInputStreamfileIn=newFileInputStream(filePath);ObjectInputStreamobjectIn=newObjectInputStream(fileIn);try{RedBlackTreetree=(RedBlackTree)objectIn.readObject();}catch(ClassNotFoundExceptione){e.printStackTrace();}objectIn.close();fileIn.close();longendRead=System.currentTimeMillis();System.out.println(ReadOver!Time:);System.out.println((newDouble(endRead-startRead))/1000);}}2.RedBlackTree.java/**Author:BYC*Number:71110214*Date:2012-5-20*/importjava.io.Serializable;publicclassRedBlackTreeimplementsSerializable{privatestaticfinalintBLACK=1;privatestaticfinalintRED=0;publicstaticRedBlackNodenullNode=null;//TheclassofNodeprivatestaticclassRedBlackNodeimplementsSerializable{intelement;RedBlackNodeleft;RedBlackNoderight;RedBlackNodeparent;intcolor;publicRedBlackNode(intele,RedBlackNodelf,RedBlackNoderg,RedBlackNodepar,intcol){element=ele;left=lf;right=rg;parent=par;color=col;}}publicRedBlackNoderoot;publicRedBlackTree(){root=nullNode;}privateintcompare(inti,intj){if(ij){return1;}else{if(ij){return-1;}else{return0;}}}//TheoperationofinsertpublicvoidinsertNode(inti){intcompare=0;RedBlackNodenewNode=newRedBlackNode(i,nullNode,nullNode,nullNode,RED);if(root==nullNode){root=newNode;}else{RedBlackNodetemp=root;while(true){compare=compare(i,temp.element);if(compare==0){return;}else{if(compare0){if(temp.left==nullNode){temp.left=newNode;break;}temp=temp.left;}else{if(temp.right==nullNode){temp.right=newNode;break;}temp=temp.right;}}}newNode.parent=temp;}insertCase1(newNode);}privatevoidinsertCase1(RedBlackNodenewNode){//System.out.println(Case1);if(newNode.parent==nullNode){newNode.color=BLACK;}else{insertCase2(newNode);}}privatevoidinsertCase2(RedBlackNodenewNode){//System.out.println(Case2);if(newNode.parent.color!=BLACK){insertCase3(newNode);}}privatevoidinsertCase3(RedBlackNodenewNode){//System.out.println(Case3);RedBlackNodeuncle=getUncle(newNode);RedBlackNodegrandPa=getGrandpa(newNode);if((uncle!=nullNode)&&(uncle.color==RED)){newNode.parent.color=BLACK;uncle.color=BLACK;grandPa.color=RED;insertCase1(grandPa);}else{insertCase4(newNode);}}privatevoidinsertCase4(RedBlackNodenewNode){//System.out.println(Case4);RedBlackNodegrandPa=getGrandpa(newNode);if(newNode.equals(newNode.parent.left)&&(newNode.parent.equals(grandPa.right))){rotateRight(newNode.parent);newNode=newNode.right;}elseif(newNode.equals(newNode.parent.right)&&(newNode.parent.equals(grandPa.left))){rotateLeft(newNode.parent);newNode=newNode.left;}insertCase5(newNode);}privatevoidinsertCase5(RedBlackNodenewNode){//System.out.println(Case5);RedBlackNodegrandPa=getGrandpa(newNode);newNode.parent.color=BLACK;grandPa.color=RED;if(newNode.equals(newNode.parent.left)){rotateRight(grandPa);}else{rotateLeft(grandPa);}}privatestaticRedBlackNodegetUncle(RedBlackNodenode){if(node.parent!=nullNode){if((node.parent).equals(node.parent.parent