红黑树实验报告

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

2、一样，也能够在O(log N)时间上完成。而红黑树的插入和删除节点的的方法只是在原二叉搜索树搜索和删除算法之后经过一定的过程来维持红黑树的性质不变。红黑树的每个节点上的属性除了有一个key、3个指针：parent、left、right以外，还多了一个属性：color。它只能是两种颜色：红或黑,当然也可以再加一些以key来索引的数据。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下5点性质：1. 每个节点是黑色的或是红色的。2. 根节点是黑色的。3. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点left、right都不指向NULL，而是指向一个定义好的空节点,这样可以保持算法

3、的一致性，简化算法）。4. 红色节点的父、左子、右子节点都是黑色。5. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。二、红黑树构造过程为了满足上述5条规则，在进行节点插入时需要进行如下操作；先按二叉搜索树规则进行插入，之后进行调整。分为5种调整情况：case1，case2，case3，case4，case5；Case1：若插入的是根节点，则不作操作，完成调整。否则转入case2；Case2：若插入节点是黑色节点，则不作操作，完成调整。否则转入case3；Case3：若插入的节点的叔叔节点是红色，则更改叔父两节点颜色为黑色，置插入点为祖父节点，之后进入case

4、1。否则转入case4；Case4：若插入节点、父节点和祖父节点不在同一条直线，以父为轴进行一次旋转，使节点、父节点和祖父节点在同一条直线。否则进入case5；Case5：以祖父为轴进行一次旋转，并且更改祖父节点为红色，父节点为红色。三、红黑树代码注：仅实现插入操作和存储读取操作1. TextMain.java /* * Author:BYC * Number: * Date:2012-5-20 */import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.

5、IOException;import java.io.ObjectInputStream;import java.io.ObjectOutputStream;import java.util.Random;public class TestMain public static void main(String args) throws IOExceptionint i=0;long startCon = System.currentTimeMillis();RedBlackTree rbt = new RedBlackTree();Random random = new Random();in

6、t randomNum = 0;/Insert one million numberswhile(i j)return 1;elseif(ij)return -1;else return 0;/The operation of insertpublic void insertNode(int i)int compare = 0;RedBlackNode newNode = new RedBlackNode(i,nullNode,nullNode,nullNode,RED);if(root=nullNode)root=newNode;elseRedBlackNode temp = root;wh

7、ile(true)compare = compare(i,temp.element);if(compare=0)return;elseif(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);private void insertCase1(RedBlackNode newN

8、ode)/System.out.println(Case1);if(newNode.parent=nullNode)newNode.color=BLACK;else insertCase2(newNode);private void insertCase2(RedBlackNode newNode)/System.out.println(Case2);if(newNode.parent.color!=BLACK)insertCase3(newNode);private void insertCase3(RedBlackNode newNode)/System.out.println(Case3

9、);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);else insertCase4(newNode);private void insertCase4(RedBlackNode newNode)/System.out.print

10、ln(Case4);RedBlackNode grandPa=getGrandpa(newNode);if(newNode.equals(newNode.parent.left)&(newNode.parent.equals(grandPa.right)rotateRight(newNode.parent);newNode = newNode.right;else if (newNode.equals(newNode.parent.right)&(newNode.parent.equals(grandPa.left) rotateLeft(newNode.parent);newNode = n

11、ewNode.left;insertCase5(newNode);private void insertCase5(RedBlackNode newNode)/System.out.println(Case5);RedBlackNode grandPa = getGrandpa(newNode);newNode.parent.color = BLACK;grandPa.color = RED;if(newNode.equals(newNode.parent.left)rotateRight(grandPa);else rotateLeft(grandPa);private static Red

12、BlackNode getUncle(RedBlackNode node)if(node.parent!=nullNode)if(node.parent).equals(node.parent.parent.right)return node.parent.parent.left;elsereturn node.parent.parent.right;return nullNode;private static RedBlackNode getGrandpa(RedBlackNode node)if(node!=nullNode)&(node.parent!=nullNode)return n

13、ode.parent.parent;elsereturn nullNode;/Rotate rightprivate 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(np!=nullNode)if (nod

14、e.parent.right=node) node.parent.right = nl;else node.parent.left = nl;else root = nl;node.left = nlr;if(nlr!=null)nlr.parent = node;node.parent = nl;nl.parent = np;nl.right = node;/System.out.println(nl.right.element);/Rotate Leftprivate void rotateLeft(RedBlackNode node)if(node.right!=nullNode)/in

15、t 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)if (node.parent.right=node) node.parent.right = nr;else node.parent.left = nr;else root=nr;node.right = nrl;if(nrl!=null)n

16、rl.parent = node;node.parent = nr;nr.parent = np;nr.left = node;/Print by LDRpublic void print()printTree(root);private void printTree(RedBlackNode node)if(node!=null)printTree(node.left);System.out.println(node.element);printTree(node.right);四、实验截图：五、实验总结：红黑树是我接触过的最为复杂的数据结构。为了保持它的性质，在进行节点插入时会进行很多判断和调整。开始我直接上手写代码，因为对结构理解不透彻，编码效率很低。后来决定重新理解红黑树结构，在查阅了维基百科的红黑树介绍(/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)和一篇很好的博文(http:/sat