学步园

JAVA红黑树

概念：每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色，提高二叉树的查找性能;

特性：

性质1. 节点是红色或黑色。

　　性质2. 根是黑色。

　　性质3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

　　性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

性能：O(log n)的时间之外，每次插入或删除需要O(log n)的空间。
实现：

JAVAQueue:用linkedlist写的队列

               import java.util.LinkedList;</p> <p>public class JavaQueue {</p> <p> /**<br /> * @param args<br /> */<br /> private LinkedList list = new LinkedList();</p> <p> public void push(Object v) {<br /> list.addFirst(v);<br /> }<br /> public Object pop() {<br /> return list.removeFirst();<br /> }</p> <p> public Object get() {<br /> return list.removeLast();<br /> }</p> <p> public boolean isEmpty(){<br /> return list.isEmpty();<br /> }</p> <p>}<br />

JAVAStack:用linkedlist写的堆栈

               import java.util.ArrayList;<br /> import java.util.HashMap;<br /> import java.util.LinkedList;<br /> import java.util.Map;</p> <p>import com.sun.xml.internal.bind.v2.schemagen.xmlschema.List;</p> <p>public class JavaStack {<br /> private LinkedList list = new LinkedList();<br /> public void push(Object v) {<br /> list.addFirst(v);<br /> }<br /> public Object pop(){<br /> return list.removeFirst();<br /> }<br /> public Object top(){<br /> return list.getFirst();<br /> }<br /> public boolean IsNull(){<br /> if(list.size()==0) return true;<br /> else return false;<br /> }<br /> /*public static void main(String[] args) {<br /> // TODO Auto-generated method stub<br /> JavaStack stack=new JavaStack();<br /> for(int i=0;i<10;i++)<br /> {<br /> stack.push(i);<br /> }<br /> System.out.println(stack.top());<br /> stack.pop();<br /> System.out.println(stack.top());<br /> Map map=new HashMap();<br /> A a=new A();<br /> A b=new A();<br /> A c=new A();<br /> int i=0;<br /> map.put(i, a);<br /> map.put(i++, b);<br /> map.put(i++, c);<br /> }<br /> */<br /> }<br />

TreeNode:定义的节点类

               public class TreeNode {<br /> //应该包含五个域,left,right,p,key,color;<br /> TreeNode leftNode;//指示左结点<br /> TreeNode rightNode;//指示右结点<br /> TreeNode pNode;//指示父结点或者NIL(T)哨兵结点<br /> int key;//结点的值<br /> int color;//其中0表示红，1表示黑<br /> public TreeNode getLeftNode() {<br /> return leftNode;<br /> }<br /> public void setLeftNode(TreeNode leftNode) {<br /> this.leftNode = leftNode;<br /> }<br /> public TreeNode getRightNode() {<br /> return rightNode;<br /> }<br /> public void setRightNode(TreeNode rightNode) {<br /> this.rightNode = rightNode;<br /> }<br /> public TreeNode getPNode() {<br /> return pNode;<br /> }<br /> public void setPNode(TreeNode node) {<br /> pNode = node;<br /> }<br /> public int getKey() {<br /> return key;<br /> }<br /> public void setKey(int key) {<br /> this.key = key;<br /> }<br /> public int getColor() {<br /> return color;<br /> }<br /> public void setColor(int color) {<br /> this.color = color;<br /> }<br /> //默认构造函数<br /> public TreeNode(TreeNode leftNode,TreeNode rightNode,TreeNode pNode,int key,int color){<br /> this.leftNode=leftNode;<br /> this.rightNode=rightNode;<br /> this.pNode=pNode;<br /> this.key=key;<br /> this.color=color;<br /> }<br /> }<br />

TestRBT类：主要功能实现

               import javax.swing.JOptionPane;<br /> import javax.swing.text.DefaultEditorKit.InsertBreakAction;</p> <p>import sun.management.counter.Variability;</p> <p>import com.sun.org.apache.regexp.internal.recompile;<br /> import com.sun.org.apache.xml.internal.security.Init;</p> <p>public class TestRBT {</p> <p> /**<br /> * @param args<br /> */<br /> public static void main(String[] args) {<br /> // TODO Auto-generated method stub<br /> // 1.建立一棵树，并进行初始化，也可通过插入节点进行建树<br /> // TreeNode[] node = new TreeNode[23];<br /> // 插入结点操作<br /> TreeNode nil = new TreeNode(null, null, null, -1, 1);//设定哨兵节点<br /> creatTree(nil);// 通过插入结点创建树，并以哨兵节点的父指针指向根节点<br /> showTree(nil.pNode, nil);// 展示插入建树后的结果<br /> deleteTree(nil, 8);// 删除节点，删除的节点也可从外部传入<br /> System.out.println("删除结点后：");<br /> showTree(nil.pNode, nil);// 展示删除树结点的结果<br /> }</p> <p> public static void initTree(TreeNode node, TreeNode nil) {<br /> //初始化构造树int[] a={1,2,5,7,8,11,14,15,4}<br /> TreeNode tempnode = new TreeNode(nil, nil, nil, -1, 1);<br /> node.leftNode = new TreeNode(nil, nil, node, 2, 0);<br /> node.rightNode = new TreeNode(nil, nil, node, 14, 1);</p> <p> tempnode = node.leftNode;<br /> tempnode.leftNode = new TreeNode(nil, nil, tempnode, 1, 1);<br /> tempnode.rightNode = new TreeNode(nil, nil, tempnode, 7, 1);</p> <p> tempnode = tempnode.rightNode;<br /> tempnode.leftNode = new TreeNode(nil, nil, tempnode, 5, 0);<br /> tempnode.rightNode = new TreeNode(nil, nil, tempnode, 8, 0);</p> <p> tempnode = node.rightNode;<br /> tempnode.rightNode = new TreeNode(nil, nil, tempnode, 15, 0);<br /> /*<br /> * int i = 2; while (i < 23) { if ((i == 2) || (i == 3) || (i == 4) ||<br /> * (i == 6) || (i == 7) || (i == 9) || (i == 11) || (i == 12) || (i ==<br /> * 14) || (i == 17) || (i == 18) || (i == 19) || (i == 20) || (i == 22))<br /> * node[i] = new TreeNode(nil, nil, nil, i, 1); i++; } // 赋值<br /> * node[7].setLeftNode(node[4]); node[7].setRightNode(node[11]);<br /> * node[4].setLeftNode(node[3]); node[4].setRightNode(node[6]);<br /> * node[4].setPNode(node[7]); node[3].setLeftNode(node[2]);<br /> * node[3].setPNode(node[4]); node[2].setPNode(node[3]);<br /> * node[6].setPNode(node[4]);<br /> *<br /> * node[11].setLeftNode(node[9]); node[11].setRightNode(node[18]);<br /> * node[11].setPNode(node[7]);<br /> *<br /> * node[18].setLeftNode(node[14]); node[18].setRightNode(node[19]);<br /> * node[18].setPNode(node[11]);<br /> *<br /> * node[14].setLeftNode(node[12]); node[14].setRightNode(node[17]);<br /> * node[14].setPNode(node[18]);<br /> *<br /> * node[19].setRightNode(node[22]); node[19].setPNode(node[18]);<br /> *<br /> * node[22].setLeftNode(node[20]); node[22].setPNode(node[19]);<br /> *<br /> * node[12].setPNode(node[14]); node[17].setPNode(node[14]);<br /> * node[20].setPNode(node[22]); // show(node);<br /> *<br /> */<br /> }</p> <p> public static void showTree(TreeNode node, TreeNode nil) {<br /> // 中序循环遍历树<br /> /*<br /> * JavaStack stack = new JavaStack(); // 将根结点输入栈中 while (node != nil ||<br /> * !stack.IsNull()) { if (node != nil) { stack.push(node); node =<br /> * node.leftNode; } else { TreeNode tempnode = (TreeNode) stack.pop();<br /> * System.out.print(tempnode.key+" " ); if (tempnode.rightNode != nil)<br /> * node = tempnode.rightNode; } }<br /> */<br /> // 层次遍历，分别打印出树的根结点,不用递归用循环提高效率<br /> JavaQueue queue = new JavaQueue();<br /> queue.push(node);// 将根结点输入栈中<br /> while (!queue.isEmpty()) {//队列不为空则出队列，继续添加新节点<br /> /**/<br /> TreeNode tempnode = (TreeNode) queue.get();<br /> int key = tempnode.key;<br /> StringBuffer str = new StringBuffer();//通过StringBuffer进行输出<br /> str.append("key:" + key);<br /> if (tempnode.color == 0) {<br /> str.append(" color:红色");<br /> } else {<br /> str.append(" color:黑色");<br /> }<br /> if (tempnode.leftNode != nil && tempnode.leftNode != null) {<br /> str.append(" lefttree:" + tempnode.leftNode.key);<br /> queue.push(tempnode.leftNode);<br /> }</p> <p> if (tempnode.rightNode != nil) {<br /> str.append(" righttree:" + tempnode.rightNode.key);<br /> queue.push(tempnode.rightNode);<br /> }<br /> System.out.println(str.toString());<br /> }<br /> }</p> <p> public static void leftRotate(TreeNode xnode, TreeNode nil) {<br /> //左旋转的实际为改变节点的前趋后继,三个节点，当前节点，当前节点的右节点，当前节点右节点的左节点<br /> TreeNode yNode = xnode.rightNode;// 设置右孩子为y结点<br /> xnode.rightNode = yNode.leftNode;<br /> if (yNode.leftNode != nil)<br /> yNode.leftNode.pNode = xnode;<br /> yNode.pNode = xnode.pNode;<br /> if (xnode.pNode == nil) {<br /> nil.pNode = yNode;<br /> } else if (xnode == xnode.pNode.leftNode) {<br /> xnode.pNode.leftNode = yNode;<br /> } else {<br /> xnode.pNode.rightNode = yNode;<br /> }<br /> yNode.leftNode = xnode;<br /> xnode.pNode = yNode;<br /> }</p> <p> public static void rightRotate(TreeNode xnode, TreeNode nil) {<br /> TreeNode yNode = xnode.leftNode;// 设置左孩子为y结点<br /> xnode.leftNode = yNode.rightNode;<br /> if (yNode.rightNode != nil) {</p> <p> yNode.rightNode.pNode = xnode;<br /> }<br /> yNode.pNode = xnode.pNode;<br /> if (xnode.pNode == nil) {<br /> nil.pNode = yNode;<br /> } else if (xnode == xnode.pNode.rightNode) {<br /> xnode.pNode.rightNode = yNode;<br /> } else {<br /> xnode.pNode.leftNode = yNode;<br /> }<br /> yNode.rightNode = xnode;<br /> xnode.pNode = yNode;<br /> }</p> <p> public static void InsertTreeNode(int i, TreeNode nil) {<br /> TreeNode newnode = new TreeNode(nil, nil, nil, i, 0);// 设置新插入结点初始值为i<br /> TreeNode tempnode = new TreeNode(nil, nil, nil, -1, 0);// 设置比较结点的父结点<br /> TreeNode recnode = new TreeNode(nil, nil, nil, -1, 0);// 设置一个循环树结点<br /> // 执行查找过程，找到相应的位置并进行插入，随后进行红黑性质的插入调整<br /> recnode = nil.pNode;<br /> if (recnode == null) {<br /> nil.pNode = newnode;<br /> newnode.color = 1;<br /> } else {<br /> while (recnode != nil) {<br /> tempnode = recnode;<br /> if (i < recnode.key) {<br /> recnode = recnode.leftNode;<br /> } else {<br /> recnode = recnode.rightNode;<br /> }<br /> }<br /> newnode.pNode = tempnode;<br /> if (newnode.key < tempnode.key) {<br /> tempnode.leftNode = newnode;<br /> } else {<br /> tempnode.rightNode = newnode;<br /> }<br /> // 执行修补程序<br /> InsertTreeNodeFixup(nil, newnode);<br /> }<br /> }</p> <p> public static void InsertTreeNodeFixup(TreeNode nil, TreeNode newnode) {<br /> TreeNode tempnode = new TreeNode(nil, nil, nil, -1, 0);<br /> /*执行插入主要解决红红冲突，具体情况有三种，注意插入的结点默认均为红色<br /> * 1.newnode 的叔叔为红,即将其父，叔结点均置为黑<br /> * 2.newnode 的叔叔是黑，newnode为父结点的右孩子<br /> * 3.newnode 的叔叔是黑，newnode为父结点的左孩子<br /> * 2,3的解决办法是先进行一次相应方向的旋转(左子树即左转，右子树即右转)，然后将newnode设为祖父结点，<br /> * 进行相应的反方向转动，最后设置根结点值为黑色<br /> * 插入操作可通过两次旋转彻底解决平衡问题<br /> */<br /> while (newnode.pNode.color == 0) {<br /> if (newnode.pNode == newnode.pNode.pNode.leftNode) {<br /> tempnode = newnode.pNode.pNode.rightNode;// 叔父结点为爷爷的左子树<br /> if (tempnode.color == 0) {// 叔父结点为红<br /> newnode.pNode.color = 1;<br /> tempnode.color = 1;<br /> newnode.pNode.pNode.color = 0;<br /> newnode = newnode.pNode.pNode;<br /> } else {<br /> if (newnode == newnode.pNode.rightNode)// 叔父结点为黑并为其父爷点的左子树<br /> {<br /> newnode = newnode.pNode;<br /> leftRotate(newnode, nil);<br /> }<br /> newnode.pNode.color = 1;<br /> newnode.pNode.pNode.color = 0;<br /> rightRotate(newnode.pNode.pNode, nil);<br /> }<br /> } else {<br /> tempnode = newnode.pNode.pNode.leftNode;// 叔父结点为爷爷的右子树<br /> if (tempnode.color == 0) {// 叔父结点为红<br /> newnode.pNode.color = 1;<br /> tempnode.color = 1;<br /> newnode.pNode.pNode.color = 0;<br /> newnode = newnode.pNode.pNode;<br /> } else // 叔父结点为黑并为其父爷点的左子树<br /> {<br /> if (newnode == newnode.pNode.leftNode) {<br /> newnode = newnode.pNode;<br /> rightRotate(newnode, nil);<br /> }<br /> newnode.pNode.color = 1;<br /> newnode.pNode.pNode.color = 0;</p> <p> leftRotate(newnode.pNode.pNode, nil);<br /> }<br /> }<br /> }<br /> nil.pNode.color = 1;<br /> }</p> <p> public static void creatTree(TreeNode nil) {<br /> // 新建NIL[T]结点<br /> // int number = Integer.parseInt(JOptionPane.showInputDialog("请输入个数:"));<br /> int[] number = new int[] { 1, 2, 5, 7, 8, 11, 14, 15, 4 };<br /> // int[] number = new int[] { 8,11,17,15,6,1,22,25,27 };<br /> for (int i = 0; i < number.length; i++) {<br /> // int inputValue = Integer.parseInt(JOptionPane<br /> // .showInputDialog("请输入树节点值:"));<br /> int inputValue = number[i];<br /> InsertTreeNode(inputValue, nil);<br /> }<br /> }</p> <p> public static void deleteTree(TreeNode nil, int i) {<br /> /*删除结点主要考虑三个问题：<br /> * 1.删除的为叶子节点，即左右子树为空<br /> * 2.删除的为带一棵子树的结点<br /> * 前面两种情况可以合并讨论，都是直接让父结点指向孩子结点或空节点(左右子树为空时)，删除后设置<br /> * 旋转结点，进行修复<br /> * 3.删除的为有左右子树的结点，需要取得其后继结点，作为新结点<br /> * </p> <p> *<br /> *<br /> *<br /> *<br /> * */<br /> // 查找到删除节点，从根结点开始循环遍历<br /> TreeNode zNode = new TreeNode(nil, nil, nil, i, 1);<br /> TreeNode xNode = new TreeNode(nil, nil, nil, -1, 1);<br /> TreeNode tempNode = nil.pNode;// 设置根结点<br /> TreeNode rootnode= new TreeNode(nil, nil, nil, -1, 1);</p> <p> boolean mark = false;// 查找对象结点<br /> while (tempNode != nil && mark == false) {<br /> if (zNode.key < tempNode.key) {<br /> tempNode = tempNode.leftNode;<br /> } else if (zNode.key > tempNode.key) {<br /> tempNode = tempNode.rightNode;<br /> } else {<br /> zNode = tempNode;<br /> mark = true;<br /> }<br /> }<br /> // zNode即为当前节点，进行删除操作<br /> TreeNode yNode = new TreeNode(nil, nil, nil, -1, 1);//y结点用于指示被删除节点<br /> if ((zNode.leftNode == nil) || (zNode.rightNode == nil)) {<br /> yNode = zNode;// 用yNode指向将被删除的结点<br /> } else {<br /> yNode = lookAfterNode(nil, zNode);// 寻找后继节点<br /> }<br /> // 进行删除，通过后继与父母结点之间建立双向关系进行删除<br /> if (yNode.leftNode != nil) {<br /> xNode = yNode.leftNode;<br /> } else {<br /> xNode = yNode.rightNode;<br /> }<br /> if ((zNode.leftNode == nil) && (zNode.rightNode == nil)) {<br /> rootnode=xNode.pNode;//此时指向空值时，nil的父母节点会改变，所以在此保留根结点，最后恢复时可用<br /> }<br /> xNode.pNode = yNode.pNode;<br /> // //////////////////////////////////////////</p> <p> if (yNode.pNode == nil) {<br /> nil.pNode = xNode;<br /> } else if (yNode == yNode.pNode.leftNode) {<br /> yNode.pNode.leftNode = xNode;<br /> } else {<br /> yNode.pNode.rightNode = xNode;<br /> }<br /> if (yNode != zNode) {<br /> zNode.key = yNode.key;<br /> }<br /> if (yNode.color == 1) {//解决黑黑冲突，如果为红则不需要改变<br /> deleteTreeFixUp(nil, xNode);<br /> }<br /> nil.pNode=rootnode;//还原根结点为nit的父母结点<br /> }</p> <p> public static TreeNode lookAfterNode(TreeNode nil, TreeNode node) {<br /> TreeNode returnNode = new TreeNode(nil, nil, nil, -1, 0);<br /> if (node.rightNode != nil) {<br /> returnNode = node.rightNode;<br /> while (returnNode.leftNode != nil) {<br /> returnNode = returnNode.leftNode;<br /> }<br /> return returnNode;<br /> }<br /> returnNode = node.pNode;<br /> while (returnNode != nil && node == returnNode.rightNode) {<br /> node = returnNode;<br /> returnNode = node.pNode;<br /> }<br /> return returnNode;<br /> }</p> <p> public static void deleteTreeFixUp(TreeNode nil, TreeNode xNode) {<br /> /* 删除修复：<br /> * 1.x的兄弟w是红色的<br /> * 2.x的兄弟w是黑色的，而且w的两个孩子都是黑色的<br /> * 3.x的兄弟w是黑色的，而且w的左孩子为红，右孩子为黑<br /> * 4.x的兄弟w是黑色的，而且w的左孩子为黑，右孩子为红<br /> * */<br /> TreeNode adjustNode = new TreeNode(nil, nil, nil, -1, 1);<br /> while (xNode != nil.pNode && xNode.color == 1) {<br /> if (xNode == xNode.pNode.leftNode) {<br /> adjustNode = xNode.pNode.rightNode;<br /> if (adjustNode.color == 0) {<br /> adjustNode.color = 1;<br /> xNode.pNode.color = 0;<br /> leftRotate(xNode.pNode, nil);<br /> adjustNode = xNode.pNode.rightNode;<br /> }<br /> if (adjustNode.leftNode.color == 1<br /> && adjustNode.rightNode.color == 1) {<br /> adjustNode.color = 0;<br /> xNode = xNode.pNode;<br /> } else if (adjustNode.rightNode.color == 1) {<br /> adjustNode.leftNode.color = 1;<br /> adjustNode.color = 0;<br /> rightRotate(adjustNode, nil);<br /> adjustNode = xNode.pNode.rightNode;<br /> }<br /> adjustNode.color = adjustNode.pNode.color;<br /> adjustNode.pNode.color = 1;<br /> adjustNode.rightNode.color = 1;<br /> leftRotate(xNode.pNode, nil);<br /> xNode = nil.pNode;<br /> } else {<br /> adjustNode = xNode.pNode.leftNode;<br /> if (adjustNode.color == 0) {<br /> adjustNode.color = 1;<br /> xNode.pNode.color = 0;<br /> rightRotate(xNode.pNode, nil);<br /> adjustNode = xNode.pNode.leftNode;<br /> }<br /> if (adjustNode.rightNode.color == 1<br /> && adjustNode.leftNode.color == 1) {<br /> adjustNode.color = 0;<br /> xNode = xNode.pNode;<br /> } else if (adjustNode.leftNode.color == 1) {<br /> adjustNode.rightNode.color = 1;<br /> adjustNode.color = 0;<br /> leftRotate(adjustNode, nil);<br /> adjustNode = xNode.pNode.leftNode;<br /> }<br /> adjustNode.color = adjustNode.pNode.color;<br /> adjustNode.pNode.color = 1;<br /> adjustNode.leftNode.color = 1;<br /> rightRotate(xNode.pNode, nil);<br /> xNode = nil.pNode;<br /> }<br /> }<br /> xNode.color = 1;<br /> }<br /> }