红黑树实验报告

一、红黑树特点简介

红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种。二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。这种低效产生的原因是树没有维持一定的平衡性，要提高搜索效率，就要想办法来维持树左边的平衡，也就是要尽时降低树的高度，可行的做法就是用一些策略在每次修改树的内容之后都调整树的结构，使之满足一定的平衡条件。其中一种满足一定平衡条件而且目前应用广泛的是红黑树。它可以在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。而红黑树的查找方法与二叉搜索树完全一样，也能够在O(log N)时间上完成。而红黑树的插入和删除节点的的方法只是在原二叉搜索树搜索和删除算法之后经过一定的过程来维持红黑树的性质不变。 红黑树的每个节点上的属性除了有一个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 */

import java.io.File;

import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.util.Random;

public class TestMain {

public static void main(String[] args) throws IOException{

int i=0;

long startCon = System.currentTimeMillis(); RedBlackTree rbt = new RedBlackTree(); Random random = new Random(); int randomNum = 0; //Insert one million numbers while(i <=500000){ }

long endCon = System.currentTimeMillis(); System.out.println(\"Construct Over!Time:\");

System.out.println((new Double(endCon - startCon)) / 1000);

//Save the Object

long startSave = System.currentTimeMillis(); File filePath = new File(\"E:/tree.tmp\");

FileOutputStream fileOut = new FileOutputStream(filePath); ObjectOutputStream objectOut = new ObjectOutputStream(fileOut); objectOut.writeObject(rbt); objectOut.close(); fileOut.close();

long endSave = System.currentTimeMillis(); System.out.println(\"save Over!Time:\");

System.out.println((new Double(endSave - startSave)) / 1000);

randomNum = random.nextInt(10000000); rbt.insertNode(randomNum); i++;

}

}

//readObject

long startRead = System.currentTimeMillis();

FileInputStream fileIn = new FileInputStream(filePath); ObjectInputStream objectIn = new ObjectInputStream(fileIn); try { }

objectIn.close(); fileIn.close();

long endRead = System.currentTimeMillis(); System.out.println(\"Read Over!Time:\");

System.out.println((new Double(endRead - startRead)) / 1000);

RedBlackTree tree = (RedBlackTree)objectIn.readObject(); e.printStackTrace();

} catch (ClassNotFoundException e) {

2. RedBlackTree.java

/*

* Author:BYC * Number:71110214 * Date:2012-5-20 */

import java.io.Serializable;

public class RedBlackTree implements Serializable{

private static final int BLACK = 1; private static final int RED = 0;

public static RedBlackNode nullNode = null;

//The class of Node

private static class RedBlackNode implements Serializable{ int element; RedBlackNode left;

RedBlackNode right; RedBlackNode parent; int color;

public RedBlackNode (int ele,RedBlackNode lf, RedBlackNode rg,RedBlackNode par,int col){

element = ele; left = lf; right = rg; parent = par; color = col;

}

}

public RedBlackNode root; public RedBlackTree(){ }

private int compare(int i,int j){ }

//The operation of insert public void insertNode(int i){

int compare = 0;

RedBlackNode newNode = new RedBlackNode(i,nullNode,nullNode,nullNode,RED); if(root==nullNode){

root=newNode;

RedBlackNode temp = root; while(true){

compare = compare(i,temp.element); if(compare==0){

return; if(compare<0){ }

if(temp.left==nullNode){ }

temp = temp.left; if(temp.right==nullNode){ }

temp = temp.right;

temp.right = newNode; break;

temp.left = newNode; break;

}else{

}else{ if(i>j){ }

return 1; if(ireturn -1; return 0; }else { }else{ root=nullNode;

}else {

}

}

}

}

newNode.parent=temp;

insertCase1(newNode);

private void insertCase1(RedBlackNode newNode){ }

private void insertCase2(RedBlackNode newNode){ }

private void insertCase3(RedBlackNode newNode){ }

private void insertCase4(RedBlackNode newNode){

//System.out.println(\"Case4\");

RedBlackNode grandPa=getGrandpa(newNode);

if(newNode.equals(newNode.parent.left)&&(newNode.parent.equals(grandPa.right))){

rotateRight(newNode.parent); newNode = newNode.right;

rotateLeft(newNode.parent); newNode = newNode.left; //System.out.println(\"Case3\");

RedBlackNode uncle = getUncle(newNode); RedBlackNode grandPa = getGrandpa(newNode); if((uncle!=nullNode)&&(uncle.color==RED)){ }

newNode.parent.color = BLACK; uncle.color = BLACK; grandPa.color = RED; insertCase1(grandPa); insertCase4(newNode); //System.out.println(\"Case2\"); if(newNode.parent.color!=BLACK){ }

insertCase3(newNode); //System.out.println(\"Case1\"); if(newNode.parent==nullNode){ }

newNode.color=BLACK; insertCase2(newNode); }else {

}else {

}else if (newNode.equals(newNode.parent.right)&&(newNode.parent.equals(grandPa.left))) {

}

}

insertCase5(newNode);

private void insertCase5(RedBlackNode newNode){ }

private static RedBlackNode getUncle(RedBlackNode node){ }

private static RedBlackNode getGrandpa(RedBlackNode node){ }

//Rotate right

private void rotateRight(RedBlackNode node){

if(node.left!=null){

//int temp = node.element; RedBlackNode nlr = node.left.right; RedBlackNode nl = node.left; RedBlackNode np = node.parent;

//node.element = nl.element; //nl.element = temp;

if((node!=nullNode)&&(node.parent!=nullNode)){ }

return node.parent.parent; return nullNode; }else{

if(node.parent!=nullNode){ }

return nullNode;

if((node.parent).equals(node.parent.parent.right)){ }

return node.parent.parent.left; return node.parent.parent.right; }else{

//System.out.println(\"Case5\");

RedBlackNode grandPa = getGrandpa(newNode); newNode.parent.color = BLACK; grandPa.color = RED;

if(newNode.equals(newNode.parent.left)){ }

rotateRight(grandPa); rotateLeft(grandPa); }else {

}

}

if(np!=nullNode){

if (node.parent.right==node) { } else { }

node.left = nlr; if(nlr!=null){ }

node.parent = nl; nl.parent = np; nl.right = node;

//System.out.println(nl.right.element);

nlr.parent = node; root = nl;

node.parent.right = nl; }else { }

node.parent.left = nl;

//Rotate Left

private void rotateLeft(RedBlackNode node){

if(node.right!=nullNode){

//int temp = node.element; RedBlackNode nrl = node.right.left; RedBlackNode nr = node.right; RedBlackNode np = node.parent;

//node.element = nr.element; //nr.element = temp;

if(np!=nullNode){ }

node.right = nrl; if(nrl!=null){

if (node.parent.right==node) {

node.parent.right = nr; }else { }

node.parent.left = nr;

}else {

root=nr;

}

}

}

}

nrl.parent = node;

node.parent = nr; nr.parent = np; nr.left = node;

//Print by LDR public void print(){ }

private void printTree(RedBlackNode node){ }

if(node!=null){ printTree(node.left);

System.out.println(node.element); printTree(node.right); }

printTree(root);

四、实验截图：

五、实验总结：

红黑树是我接触过的最为复杂的数据结构。为了保持它的性质，在进行节点插入时会进行很多判断和调整。开始我直接上手写代码，因为对结构理解不透彻，编码效率很低。后来决定重新理解红黑树结构，在查阅了维基百科的红黑树介绍(http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)和一篇很好的博文(http://saturnman.blog.163.com/blog/static/5576112010969420383/)后，我对红黑树的结构和插入调整有了清晰地认识。之后的编码工作变得一场顺利。总之，这次红黑树实验不光让我掌握了红黑树这种特定数据结构，更令对学习数据结构有了新的领悟。

六、参考资料：

1.维基百科(http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91) 2.一路博客(http://saturnman.blog.163.com/blog/static/5576112010969420383/) 3.算法导论

4.数据结构（C++描述） 作者：金远平