- 浏览: 190006 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
only_java:
博主,你好。感谢这篇你的这篇文章,我的问题是跟你一样,也是在跑 ...
JVM Crash分析 -
shuofenglxy:
1 确保程序运行时没有更新程序需要的相关jar包。2 确保程序 ...
JVM Crash分析 -
renduly:
# A fatal error has been detect ...
JVM Crash分析 -
shuofenglxy:
renduly 写道博主好。这两天我在公司程序也出现了类似的问 ...
JVM Crash分析 -
renduly:
博主好。这两天我在公司程序也出现了类似的问题。博主能否说的详细 ...
JVM Crash分析
二叉查找树代码大致如下:
二叉树节点类:
package RBTree; public class BSTreeNode { int data; BSTreeNode lchild; BSTreeNode rchild; }
二叉树的功能实现类:
package RBTree; public class BSTree { BSTreeNode root = null; // 插入节点 public void InsertNode(BSTree T, int data) { BSTreeNode node = new BSTreeNode(); BSTreeNode y = null, x; node.data = data; node.lchild = null; node.rchild = null; x = root; while (x != null) { y = x; if (x.data > node.data) x = x.lchild; else x = x.rchild; } if (y == null) T.root = node; else if (y.data > node.data) y.lchild = node; else y.rchild = node; } // 查找 public BSTreeNode SearchNode(BSTreeNode node, int data) { if (node == null) return null; else if (node.data == data) { // System.out.println(node.data); return node; } else if (node.data > data) return SearchNode(node.lchild, data); else return SearchNode(node.rchild, data); } //打印二叉树 public void BSTreedisplay(BSTreeNode t, int h) { for (int k = 0; k < h; k++) System.out.print(" "); if (t == null) { System.out.print("Nil"); } else { System.out.println("(" + t.data + ","); BSTreedisplay(t.lchild, h + 1); System.out.print(","); System.out.println(); BSTreedisplay(t.rchild, h + 1); System.out.print(")"); System.out.println(); for (int k = 0; k < h - 1; k++) System.out.print(" "); } } }
红黑树
红黑树节点类:
package RBTree; public class RBTreeNode { public int data; public String color; public RBTreeNode parent; public RBTreeNode lchild; public RBTreeNode rchild; }
红黑树功能类:
package RBTree; public class RBTree { RBTreeNode nulNode = new RBTreeNode(); RBTreeNode root =nulNode; public RBTree(){ this.nulNode.color ="B"; this.nulNode.data = -1; this.nulNode.lchild = nulNode; this.nulNode.rchild = nulNode; this.nulNode.parent = nulNode; } // 插入一个节点 public void RBTreeInsert(RBTree T,int data){ RBTreeNode x = T.root,y=nulNode; RBTreeNode node = new RBTreeNode(); node.data = data; node.parent =null; node.lchild = null; node.rchild = null; node.color =null; while(x!=nulNode){ y=x; if(node.data<x.data) x=x.lchild; else x=x.rchild; } node.parent = y; if(y==nulNode){ root = node; } else if(node.data<y.data){ y.lchild = node; } else{ y.rchild = node; } node.color = "R"; node.lchild =nulNode; node.rchild = nulNode; RBInsertFixup(T,node); //System.out.println("Insert"+node.data+"success"); } // 插入节点中的节点调整 包括颜色调整和左右旋 public void RBInsertFixup(RBTree T, RBTreeNode node){ RBTreeNode y= nulNode; while(node.parent.color =="R"){ if(node.parent == node.parent.parent.lchild){ y = node.parent.parent.rchild; if(y.color == "R"){ node.parent.color ="B"; y.color = "B"; node.parent.parent.color ="R"; node = node.parent.parent; } else{ if(node == node.parent.rchild){ node = node.parent; LeftRotate(T,node); } node.parent.color = "B"; node.parent.parent.color = "R"; RightRotate(T,node.parent.parent); } } else{ y = node.parent.parent.lchild; if(y.color == "R"){ node.parent.color ="B"; y.color = "B"; node.parent.parent.color ="R"; node = node.parent.parent; } else{ if(node == node.parent.lchild){ node = node.parent; RightRotate(T,node); } node.parent.color = "B"; node.parent.parent.color = "R"; LeftRotate(T,node.parent.parent); } } } T.root.color = "B"; } // 左旋 private void LeftRotate(RBTree t, RBTreeNode node) { // TODO Auto-generated method stub RBTreeNode y; y = node.rchild; node.rchild = y.lchild; if(y.lchild !=nulNode){ y.lchild.parent = node; } y.parent = node.parent; if(node.parent == nulNode){ t.root =y; } else if(node == node.parent.lchild){ node.parent.lchild = y; } else{ node.parent.rchild = y; } y.lchild = node; node.parent = y; } // 右旋 private void RightRotate(RBTree t, RBTreeNode node) { // TODO Auto-generated method stub RBTreeNode y; y = node.lchild; node.lchild = y.rchild; if(y.rchild !=nulNode){ y.rchild.parent = node; } y.parent = node.parent; if(node.parent == nulNode){ t.root =y; } else if(node == node.parent.lchild){ node.parent.lchild = y; } else{ node.parent.rchild = y; } y.rchild = node; node.parent = y; } // 查找节点 public RBTreeNode RBTreeSearch(RBTreeNode t, int z){ if(t == nulNode){ System.out.println("没有找到"); return nulNode; } else if(t.data == z) //System.out.println(y.data); return t; else if(t.data>z) return RBTreeSearch(t.lchild,z); else return RBTreeSearch(t.rchild,z); } // 删除节点 public RBTreeNode RBDelete(RBTree T,RBTreeNode node){ RBTreeNode y,x; if(node.lchild ==nulNode || node.rchild ==nulNode) y = node; else y = TreeSuccessor(node); if(y.lchild !=nulNode) x = y.lchild; else x =y.rchild; x.parent = y.parent; if(y.parent == nulNode) T.root = node; else if(y==y.parent.lchild) y.parent.lchild = x; else y.parent.rchild = x; if(y != node){ node.data = y.data; } if(y.color == "B"){ RBDeleteFixup(T,x); } return y; } // 删除的调整 private void RBDeleteFixup(RBTree t, RBTreeNode x) { RBTreeNode w; while(x!=t.root && x.color =="B"){ if(x == x.parent.lchild){ w = x.parent.rchild; if(w.color =="R"){ w.color = "B"; w.parent.color ="R"; LeftRotate( t, x.parent); w = x.parent.rchild; } if(w.lchild.color == "B" && w.rchild.color == "B"){ w.color ="R"; x= x.parent; } else{ if(w.rchild.color =="B"){ w.lchild.color ="R"; w.color = "B"; RightRotate(t,x); w=x.parent.rchild; } w.color = x.parent.color; x.parent.color = "B"; w.rchild.color ="B"; LeftRotate( t, x.parent); x = t.root; } } else{ w = x.parent.lchild; if(w.color =="R"){ w.color = "B"; w.parent.color ="R"; LeftRotate( t, x.parent); w = x.parent.rchild; } if(w.lchild.color == "B" && w.rchild.color == "B"){ w.color ="R"; x= x.parent; } else{ if(w.rchild.color =="B"){ w.lchild.color ="R"; w.color = "B"; LeftRotate(t,x); w=x.parent.rchild; } w.color = x.parent.color; x.parent.color = "B"; w.rchild.color ="B"; RightRotate( t, x.parent); x = t.root; } } } x.color = "B"; } private RBTreeNode TreeSuccessor(RBTreeNode node) { RBTreeNode y; if(node.rchild!=nulNode) return TreeMin(node.rchild); y = node.parent; while(y!=nulNode&&node == y.rchild){ node = y; y=y.parent; } return y; } private RBTreeNode TreeMin(RBTreeNode node) { while(node.rchild!=nulNode) node =node.rchild; return node; } public int RBTreeBlackHeight(RBTreeNode t){ if(t ==nulNode) return 1; else return 1+RBTreeBlackHeight(t.lchild); } // 打印红黑树 public void RBTreedisplay(RBTreeNode t,int h){ for(int k = 0;k<h;k++) System.out.print(" "); if(t == nulNode){ System.out.print("Nil"); } else { System.out.println("("+t.data+t.color+","); RBTreedisplay(t.lchild,h+1); System.out.println(","); RBTreedisplay(t.rchild,h+1); System.out.println(")"); for(int k = 0;k<h-1;k++) System.out.print(" "); } } }
扩展红黑树:
节点类:
package RBTree; public class ExRBTreeNode { public int data; public String color; public ExRBTreeNode parent; public ExRBTreeNode lchild; public ExRBTreeNode rchild; public int size; }
功能类:
package RBTree; public class ExRBTree { ExRBTreeNode nulNode = new ExRBTreeNode(); ExRBTreeNode root =nulNode; public ExRBTree(){ this.nulNode.color ="B"; this.nulNode.data = -1; this.nulNode.lchild = nulNode; this.nulNode.rchild = nulNode; this.nulNode.parent = nulNode; } public void ExRBTreeInsert(ExRBTree T,int data){ ExRBTreeNode x = T.root,y=nulNode; ExRBTreeNode node = new ExRBTreeNode(); node.data = data; node.parent =null; node.lchild = null; node.rchild = null; node.color =null; node.size =0; while(x!=nulNode){ y=x; if(node.data<x.data) x=x.lchild; else x=x.rchild; } node.parent = y; if(y==nulNode){ root = node; } else if(node.data<y.data){ y.lchild = node; } else{ y.rchild = node; } node.color = "R"; node.lchild =nulNode; node.rchild = nulNode; ExRBInsertFixup(T,node); //System.out.println("Insert"+node.data+"success"); } public void ExRBInsertFixup(ExRBTree T, ExRBTreeNode node){ ExRBTreeNode y= nulNode; while(node.parent.color =="R"){ if(node.parent == node.parent.parent.lchild){ y = node.parent.parent.rchild; if(y.color == "R"){ node.parent.color ="B"; y.color = "B"; node.parent.parent.color ="R"; node = node.parent.parent; } else{ if(node == node.parent.rchild){ node = node.parent; LeftRotate(T,node); } node.parent.color = "B"; node.parent.parent.color = "R"; RightRotate(T,node.parent.parent); } } else{ y = node.parent.parent.lchild; if(y.color == "R"){ node.parent.color ="B"; y.color = "B"; node.parent.parent.color ="R"; node = node.parent.parent; } else{ if(node == node.parent.lchild){ node = node.parent; RightRotate(T,node); } node.parent.color = "B"; node.parent.parent.color = "R"; LeftRotate(T,node.parent.parent); } } } T.root.color = "B"; } private void LeftRotate(ExRBTree t, ExRBTreeNode node) { // TODO Auto-generated method stub ExRBTreeNode y; y = node.rchild; node.rchild = y.lchild; if(y.lchild !=nulNode){ y.lchild.parent = node; } y.parent = node.parent; if(node.parent == nulNode){ t.root =y; } else if(node == node.parent.lchild){ node.parent.lchild = y; } else{ node.parent.rchild = y; } y.lchild = node; node.parent = y; } private void RightRotate(ExRBTree t, ExRBTreeNode node) { // TODO Auto-generated method stub ExRBTreeNode y; y = node.lchild; node.lchild = y.rchild; if(y.rchild !=nulNode){ y.rchild.parent = node; } y.parent = node.parent; if(node.parent == nulNode){ t.root =y; } else if(node == node.parent.lchild){ node.parent.lchild = y; } else{ node.parent.rchild = y; } y.rchild = node; node.parent = y; } public int ExRBTreeGetSize(ExRBTreeNode t){ if(t ==nulNode){ return 0; } else return 1+ExRBTreeGetSize(t.lchild)+ExRBTreeGetSize(t.rchild); } public ExRBTreeNode ExRBTreeSearch(ExRBTreeNode t, int z){ if(t == nulNode){ System.out.println("没有找到"); return nulNode; } else if(t.data == z) //System.out.println(y.data); return t; else if(t.data>z) return ExRBTreeSearch(t.lchild,z); else return ExRBTreeSearch(t.rchild,z); } public void SetExRBTreeSize(ExRBTree T,int data){ ExRBTreeNode t = ExRBTreeSearch(T.root,data); t.size =ExRBTreeGetSize(t); } public int ExRBTreeGetRank(ExRBTree T,int data){ ExRBTreeNode y; ExRBTreeNode t = ExRBTreeSearch(T.root,data);//找到该值对应的节点 int r = t.lchild.size+1; y = t; while(y!=T.root){ if(y ==y.parent.rchild) r = r+y.parent.lchild.size+1; y = y.parent; } return r; } public void ExRBTreedisplay(ExRBTreeNode t,int h){ for(int k = 0;k<h;k++) System.out.print(" "); if(t == nulNode){ System.out.print("Nil"); } else { System.out.println("("+t.data+t.color+t.size+","); ExRBTreedisplay(t.lchild,h+1); System.out.println(","); ExRBTreedisplay(t.rchild,h+1); System.out.println(")"); for(int k = 0;k<h-1;k++) System.out.print(" "); } } }
测试主类:
package RBTree; import java.util.ArrayList; public class RBTreeTest { public static void main(String args[]) { RBTree T1 = new RBTree(); RBTree T = new RBTree(); BSTree BT = new BSTree(); // 插入要求的数组 int arr[] = { 8, 11, 17, 15, 6, 1, 22, 25, 27 }; for (int i = 0; i < arr.length; i++) T1.RBTreeInsert(T1, arr[i]); System.out.println("插入{8,11,17,15,6,1,22,25,27}后红黑树如下"); T1.RBTreedisplay(T1.root, 0);// 打印树 int bh = T1.RBTreeBlackHeight(T1.root);// 获取黑高度 System.out.println("T1黑高度为" + bh); // 删除15元素后得到树并打印 RBTreeNode q = null; q = T1.RBDelete(T1, T1.RBTreeSearch(T1.root, 15)); System.out.println("删除的节点信息为" + q.data + q.color + ", 删除后树形如下:"); T1.RBTreedisplay(T1.root, 0);// 打印树 bh = T1.RBTreeBlackHeight(T1.root);// 获取黑高度 System.out.println("删除节点15后,T1黑高度为" + bh); // 随机生成1-300000个不同的数值 分别插入二叉树BT与红黑树T 比较查找15000的时间代价 ArrayList arrlist = new ArrayList(); for (int i = 0; i < 300000; i++) arrlist.add(i + 1); for (int i = 0; i < 300000; i++) { int temp = (int) (Math.random() * arrlist.size()); int data = (Integer) arrlist.remove(temp); T.RBTreeInsert(T, data); BT.InsertNode(BT, data); } // 二叉树中查找15000节点 BSTreeNode p = null; long time = System.nanoTime(); ; p = BT.SearchNode(BT.root, 15000); long span = System.nanoTime() - time; System.out.println(p.data); long b = System.currentTimeMillis(); System.out.println("二叉树查找时间为:" + span + "纳秒"); // 红黑树中查找15000节点 time = System.nanoTime(); q = T.RBTreeSearch(T.root, 15000); span = System.nanoTime() - time; System.out.println(q.data + q.color); System.out.println("红黑树查找时间为:" + span + "纳秒"); // 输出秩 为此建立了扩展红黑树ExRBTree ExRBTree T2 = new ExRBTree(); int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; for (int i = 0; i < arr1.length; i++) T2.ExRBTreeInsert(T2, arr1[i]); System.out.println("插入{1,2,3,4,5,6,7,8}后红黑树如下【格式为数据值 、节点颜色、size域】"); for (int i = 0; i < arr1.length; i++) T2.SetExRBTreeSize(T2, arr1[i]); T2.ExRBTreedisplay(T2.root, 0); int k = T2.ExRBTreeGetRank(T2, 6); System.out.println("key值为6的rank为:" + k); } }
PS:很久以前自己写的代码了,这里整理了一下,搬到博客来,其中功能不是很完整,比如二叉树就没有写删除功能。
评论
4 楼
javaliver
2011-02-28
测试结果如下:
(1,
Nil,
(13,
(2,
Nil,
(6,
(4,
Nil,
Nil)
,
(8,
Nil,
(11,
(9,
Nil,
Nil)
,
Nil)
)
)
)
,
(17,
Nil,
Nil)
)
)
优雅....
3 楼
laitaogood
2011-02-26
貌似JDK源码里有这些实现吧。。。
2 楼
shuofenglxy
2011-02-11
wangxin0072000 写道
二叉树的插入算法貌似有问题.我download下来,试了一下,打印的树是错的
这个我试了是 没有问题哈。写了个demo测试一下,突然发现这个两年前的代码风格惨不忍睹。
package RBTree; public class BSTreeTest { public static void main(String[]args){ int[] data = {1,13,2,17,6,8,4,11,9}; BSTree bstree = new BSTree(); for(int i = 0;i<data.length;i++) bstree.InsertNode(bstree, data[i]); bstree.BSTreedisplay(bstree.root, 0); } }
测试结果如下:
(1,
Nil,
(13,
(2,
Nil,
(6,
(4,
Nil,
Nil)
,
(8,
Nil,
(11,
(9,
Nil,
Nil)
,
Nil)
)
)
)
,
(17,
Nil,
Nil)
)
)
结果是正确的啊,可能是打印的树形不太好吧,说明一下 每一个节点值+逗号,然后换行,然后左节点+逗号,然后换行,然后右节点。如果该节点为某一节点的子节点,那么它前方带有左括弧,它的右子节点带有右括弧。
唉,等有时间了,我加下代码注释,另外改进下代码吧,看着真囧。
1 楼
wangxin0072000
2011-02-11
二叉树的插入算法貌似有问题.我download下来,试了一下,打印的树是错的
发表评论
-
数组查值
2011-09-27 16:42 783问题描述:{4,5,7,8,1,2} 找值为K的元素。 两种 ... -
全排列 递归式
2011-09-27 15:18 836简单的整理一下全排列思路。全部遍历,打印前筛选条件。全部遍历则 ... -
简单的四则运算计算器
2011-09-27 11:27 829这是一个简单的四则运算计算器,不支持括号,没有做乘法的越 ... -
ZZ并查集
2011-02-22 15:40 852原文出处:http://blog.si ... -
ZZ那些优雅的数据结构(1) : BloomFilter——大规模数据处理利器
2011-02-21 14:39 1050原文来自:http://www.cnblogs.com/hea ... -
矩阵链乘法算法讲解
2011-02-15 15:57 4316矩阵链乘是一个计算 ... -
把二元查找树转变成排序的双向链表
2011-02-14 19:59 1975分析:二叉树中序遍历即可得到一个有序的结果,只要按照中序遍历的 ... -
A Simple Ordered Hashtable
2011-02-11 15:26 929原文来自: http://wuhua.iteye.com/bl ... -
递归总结二 汉诺塔问题
2011-02-07 19:38 1089汉诺塔是貌似递归入门的引导题目,把这个过程写下来,mark一下 ... -
递归总结一 全排列问题
2011-02-07 18:48 1539全排列问题:这是描述 ... -
几种常见的排序算法
2011-02-05 13:19 1109这里是以前写的算法总结了。照搬过来而已。 package S ... -
LIS 最长递增子序列算法总结
2011-02-05 12:53 1429这里包含了三种求得递增子序列的算法。 是以前写的代码,这里就 ... -
求1的个数问题
2011-01-25 16:14 1104又是一年笔试时,很多学弟们开始笔试了。今天学弟问求一个int数 ... -
消除递归典型应用2------N阶台阶问题
2011-01-25 16:12 1361问题描述:一个人可以一步走1或2或3级台阶,问到N级台阶共有多 ... -
左右手法则的典型应用---字符串逆序
2011-01-25 16:10 1156问题:输入 I am a boy 输出boy a am I ... -
一个正整数拆分为连续的几个整数之和
2011-01-25 16:08 2569import java.util.Scanner; pu ... -
斐波那契序列的基本实现
2011-01-25 16:07 1642今天实在没事干,刚好别人问了我下斐波那契面试怎么回答。就 ... -
矩阵型数据 顺时针打印
2011-01-25 15:28 1382输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 ...
相关推荐
描述了红黑树的基本结构 以及与二叉树的性能比较
使用java语言编程实现了平衡二叉树、二叉树、二叉搜索树、红黑树四种树相关的数据结构,还实现了多种排序算法。并且是在J2EE下实现的。
COMP2211Project1 二叉树和红黑树的 Java 代码
四、红黑树 本质:自平衡二叉树 在二叉查找树基础上,添加以下性质 节点是红色或黑色 根节点是黑色 每个为空的叶子节点是黑色的 每个红色节点的两个子节点都是黑色 从任一节点到其每个叶子节点的所有路径都包含...
红黑树的本质是二叉树,二叉树在插入元素的时候是根据关键字(可以理解为用来识别每个节点的id,一般是hash 来判断)的大小来判断插入到哪一个分支的,如下图所示: (备注:大写字母代表每个节点相当于每个节点的...
在队列的代码中,引用了链表的代码
红黑树创建,插入,删除操作代码。包括创建,插入操作,删除操作,代码有详细的注释,java代码实现。
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS 共...
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
第一次从无到有写代码,从二叉树到红黑树,到打印树的设计,写了将近2个星期。
红黑树问题是各大计算机考研命题以及面试算法题目中的热门,接下来我们为大家图解红黑树及Java进行红黑二叉树遍历的方法,需要的朋友可以参考下
chapter-01 - git 操作命令 【 √ 】 chapter-02 - java 基础 【 △ 】 chapter-03 - 数据结构与算法 【 △ 】 chapter-14 - java 集合 【 △ 】 chapter-19 - java IO 流 【 √ 】 chapter-23 - java 反射 【 × 】
红黑树红黑二叉树的递归 Java 实现,正在进行中。 我是来自澳大利亚墨尔本的 21 岁的计算机程序员。 欢迎为这个项目贡献任何你想要的代码或评论。
http://blog.chinaunix.net/uid-24774106-id-3440620.html 是这个作者的,里面放了我写的二叉树的源码
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS 共...
java面试各大知识点,非常齐全。jvm内存分区,gc算法,类...数据结构包括堆栈,队列,链表,二叉树,红黑树,算法包括各种排序,贪心算法,动态规划。以及进阶的分布式,大数据,机器学习,内容非常全,精心总结的。