《红黑树实验报告》由会员分享，可在线阅读，更多相关《红黑树实验报告（9页珍藏版）》请在金锄头文库上搜索。
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：若插入的节点的叔叔节点是红色，则更改叔父两节点颜
4、色为黑色，置插入点为祖父节点，之后进入 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.File
5、OutputStream;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 IOExceptionint i=0;long startCon = System.currentTimeMillis();RedBlackTree rbt = new RedBlackTree();Ran
6、dom random = new Random();int 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;els
7、eRedBlackNode temp = root;while(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 i
8、nsertCase1(RedBlackNode newNode)/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 newNo
9、de)/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);else insertCase4(newNode);private void insertCase4(RedBlackNo
10、de 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;else if (newNode.equals(newNode.parent.right)&(newNode.parent.equals(grandPa.left) rotateLeft
11、(newNode.parent);newNode = newNode.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
12、(grandPa);private static RedBlackNode 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)&(no
13、de.parent!=nullNode)return node.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 =
14、temp;if(np!=nullNode)if (node.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
15、)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)if (node.parent.right=node) node.parent.right = nr;else node.parent.left = nr;else root=nr;nod
16、e.right = nrl;if(nrl!=null)nrl.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);四、实验截图：五、实验总结：红黑树是我接触过的最为复杂的数据结构。为了保持它的
