- 浏览: 34419 次
- 性别:
- 来自: 北京
最新评论
-
cjf068:
LuckYes 写道楼主如果用最小堆的话,最好用调整堆的方式来 ...
求最小的k个数问题 -
LuckYes:
楼主如果用最小堆的话,最好用调整堆的方式来构建堆,这样效率更高 ...
求最小的k个数问题 -
cjf068:
这个算法的基本思路, ...
大数乘法 -
liujunsong:
这个算法的基本思路,是小学3年级的 算法,就是简单的把乘法运算 ...
大数乘法 -
shuidexiongdi:
去年我也写了一个http://shuidexiongdi.it ...
大数乘法
红黑树 规则
* 1.每个节点不是红色就是黑色
* 2.根总是黑色
* 3.如果节点是红色,则它的两个子节点必须是黑色(反之则不一定)
* 4.从根到叶节点或空子节点的每条路径,必须包括相同数目的黑节点(空节点为黑色)
节点类:
红黑树类:
* 1.每个节点不是红色就是黑色
* 2.根总是黑色
* 3.如果节点是红色,则它的两个子节点必须是黑色(反之则不一定)
* 4.从根到叶节点或空子节点的每条路径,必须包括相同数目的黑节点(空节点为黑色)
节点类:
package org.jf.alg.tree; public class RBNode <T extends Comparable>{ public static int COLOR_RED = 1; public static int COLOR_BLACK = 2; private RBNode left; private RBNode right; private RBNode parent; private int color = COLOR_RED;//实际上是父节点指向子节点链的颜色 private T data; public RBNode(T data) { this.data = data; } public RBNode(int color,T data) { this.color = color; this.data = data; } public T value() { return this.data; } public void setParent(RBNode parent) { this.parent=parent; } public RBNode parent() { return this.parent; } public void setLeft(RBNode left) { this.left = left; } public RBNode left() { return this.left; } public void setRight(RBNode right) { this.right = right; } public RBNode right() { return this.right; } // public void setRed() // { // color=COLOR_RED; // } public void setColor(int color) { this.color = color; } // public void setBlack() // { // color=COLOR_BLACK; // } public boolean isRed() { return color==COLOR_RED; } public boolean isBlack() { return color==COLOR_BLACK; } }
红黑树类:
package org.jf.alg.tree; /** * * 红黑树 * * @author junfeng.chen * * @param <T> */ public class RBTree <T extends Comparable> { /** * * 红黑树 规则 * 1.每个节点不是红色就是黑色 * 2.根总是黑色 * 3.如果节点是红色,则它的两个子节点必须是黑色(反之则不一定) * 4.从根到叶节点或空子节点的每条路径,必须包括相同数目的黑节点(空节点为黑色) * * * */ private RBNode root; private int count; public RBTree() { } public void addData(T data) { if(data==null) return; if(root==null) { root = new RBNode(data); root.setColor(RBNode.COLOR_BLACK); count++; return; } else { RBNode node = new RBNode(data); RBNode<Comparable> pnode = findParent(root,data); if(pnode.value().compareTo(data)>0)//data<pnode -->left { pnode.setLeft(node); } else { pnode.setRight(node); } node.setParent(pnode); node.setColor(RBNode.COLOR_RED); this.fixAfterInsertion(node); } count++; } /** * * * * * @param x 当前插入的节点 * @param parent 父节点 */ private void fixAfterInsertion(RBNode x) { /** * 以 x p g 分别表示当前插入的节点 x的父节点 和 x的祖父节点(即 p 的父节点) * * * 调整节点保持红黑树性质,分三大类情况 * 1.p是黑色的 , 不用调整 * 2.p是红色的,x是g的一个外侧子孙 * 只要一次旋转和一些颜色变化 * { * (1)改变g的颜色 * (2)改变p的颜色 * (3)以x的祖父节点g为顶点旋转(向x上升的方向旋转) * { * (3-1)若x是g外侧子孙节点,且为p的左子节点,右旋 * (3-2)若x是g的外侧子孙节点,且为p的右子节点,左旋 * } * * } * * 3.p是红色的,x是g的一个内存子孙 * 需要2次旋转和一些颜色变化 * { * (1)改变x和g的颜色 * (2)以x的父节点p为顶点旋转(向着x上升的方向) * (2-1)若x是p的左子节点,右旋 * (2-2)若x是p的右子节点,左旋 * (3)再以x的祖父节点为顶旋转(向x上升的方向) * * * } * * */ RBNode p=x.parent(); //case1 if(p==null||p.isBlack()) return; RBNode g=p.parent(); int flag=0;//left +1 right -1 if(flag=0) 内侧 else 外侧 if(p==g.left()) { flag+=1; if(x==p.left()) flag+=1; else flag+=-1; }else { flag+=-1; if(x==p.left()) flag+=1; else flag+=-1; } //case2 if(flag!=0)// { if(g.isBlack()) g.setColor(RBNode.COLOR_RED); else g.setColor(RBNode.COLOR_BLACK); p.setColor(RBNode.COLOR_BLACK); if(x==p.left()) this.rotateRight(g); else this.rotateLeft(g); } else { boolean right = false; if(p==g.right()) right=true; x.setColor(RBNode.COLOR_BLACK); if(g.isBlack()) g.setColor(RBNode.COLOR_RED); else g.setColor(RBNode.COLOR_BLACK); if(x==p.left()) this.rotateRight(p); else this.rotateLeft(p); if(right) this.rotateLeft(g); else this.rotateRight(g); } //x 是g的外侧子孙 //x 是g的内侧子孙 } /** * * 参考算法导论 * 右旋 * x y y.right * 旋转支点为x 其左子节点为y,左子节点的由子节点为r * y成为新的根(取代p的位置) * x成为y的右孩子 * y的左孩子的右孩子成为x的左孩子 * * y=x.left * x.left=y.right * y.right.parent=x * y.parent=x.parent * * if x.parent is null // x is root * then root = y * else if x==x.parent.left * then x.parent.left=y * else x.parent.right=y * y.right=x; * x.parent=y; * * @param p */ private void rotateRight(RBNode x) { RBNode y=x.left(); x.setLeft(y.right()); if(y.right()!=null) y.right().setParent(x); y.setParent(x.parent()); if(x.parent()==null) root=y; else if(x==x.parent().left()) x.parent().setLeft(y); else x.parent().setRight(y); y.setRight(x); x.setParent(y); } /** * 左旋 * x y y.left * 旋转支点为x 其右子节点为y 右子节点的左子节点为left * * y成为新的根 * x成为y的左孩子 * y的左孩子成为x的右孩子 * * * y=x.right * x.right=y.left * y.left.parent=x * y.parent=x.parent * * if x.parent is null // x is tree root * then root=y * else if x=x.parent.left * then x.parent.left=y * else x.parent.right=y * y.left=x; * x.parent=y * * * @param p */ private void rotateLeft(RBNode x) { RBNode y=x.right(); x.setRight(y.left()); if(y.left()!=null) y.left().setParent(x); y.setParent(x.parent()); if(x.parent()==null) root=y; else if(x==x.parent().left()) x.parent().setLeft(y); else x.parent().setRight(y); y.setLeft(x); x.setParent(y); } private RBNode findParent(RBNode<Comparable> root,Comparable data) { /** * 与根比较 * if data>=root * 则查看右子树 如果右子树不存在 则返回根 * 否则 在右子树中查找 *else * 则查找左子树 如果左子树存在 则返回根 * 否则 在左子树中查找 */ RBNode left = root.left(); RBNode right = root.right(); Comparable value_root = root.value(); if(data.compareTo(value_root)>=0)//右子树 { if(right==null) return root; else { return findParent(right, data); } } else//左子树 { if(left==null) return root; else return findParent(left,data); } } public boolean contains(T data) { return false; } public int getCount() { return this.count; } public static void main(String args[]) { RBTree rbTree = new RBTree(); for(int i=0;i<10;i++) { rbTree.addData(i); } } }
发表评论
-
中文数字到阿拉伯数字转换
2012-04-24 10:18 1875昨天博客上看到一童鞋 ... -
布隆过滤器
2012-04-23 15:39 956package org.jf.alg; import ... -
基本的排序算法
2012-04-21 21:07 735插入排序 选择排序 快速排序 。。。。 后续补充 pack ... -
日期计算
2012-04-19 23:04 862简单日期计算类: 日期大小比较 日期之间天数计算 pack ... -
判断数组中是否存在两个元素之和等于给定数值
2012-04-06 22:58 2006已知int数组a按升序排列,要求用线性时间复杂的算法,判断是否 ... -
求最大子数组之和
2012-04-06 22:51 1304求最大子数组之和的线性解法:本算法受编程珠玑中提示而得 /** ... -
LRUCache
2012-03-15 14:35 1656MyLRUCache 缓存类 package org.jf ... -
求变位词组合
2012-03-13 22:53 853public class CharComp { ... -
计算24点
2012-03-13 21:49 1260计算n个数的全排列 package org.jf.alg. ... -
表达式计算
2012-03-10 23:02 906中缀表达式转后缀 后缀表达式计算 支持整型 分数计算,只支持 ... -
Many2One缓冲
2012-03-06 12:35 932多线程并发操作中,为了尽量减少同步锁的开销,一般都会尽可能减少 ... -
行文件分组统计
2012-03-02 22:57 831有些情况下,对于一个结构化的以行为记录的文本文件,需要按列分组 ... -
简单LRU缓存实现
2012-02-09 21:12 1071链表保存键值,由于没有权值策略,简单的将当前访问过的节点放到链 ... -
大根堆
2012-02-08 22:23 1419大根堆,可用于优先级队列 package org.jf.a ... -
固定容量二叉堆
2012-02-08 17:26 997固定容量的二叉堆实现,可用于快速求top k 问题。如要求一个 ... -
大数乘法
2012-02-07 00:16 2886论坛看到的一个面试题,实现任意大整数字符串相乘,返回结果字符串 ...
相关推荐
红黑树详解(带目录源码) 本文适合那些有对二叉树有一定的基础,并且熟悉C语言的读者。本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。
红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...
红黑树527378231
红黑树527378236
红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在实现高效的数据结构和算法时。在Java中,虽然标准库并未直接提供红黑树的类,但我们可以自定义实现,如提供的`Red...
红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本性质的同时,通过引入颜色属性来保证树的平衡,从而达到高效的插入、删除和查找操作。在这个“红黑树demo python...
解析红黑树(ppt文档) 红黑树是一种自平衡二叉查找树,它的每个节点都包含一个键值和对应的值。红黑树的主要特点是它可以自动维持平衡,从而保证查找、插入、删除操作的时间复杂度为 O(log n)。 红黑树的五个性质...
红黑树(Red-Black Tree)是一种自平衡的二叉查找树,由计算机科学家Rudolf Bayer在1972年提出。它在保持二叉查找树特性的同时,通过引入颜色属性来确保树的平衡,从而提高了数据操作的效率。在C++中,红黑树常用于...
红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性:红色或黑色。这种颜色属性用于确保树的平衡,使得在树中的...
红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持搜索效率的同时,通过特定的颜色规则来维护树的平衡,从而保证了插入、删除和查找操作的时间复杂度都能达到O(log n)。在本项目中,...
红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性:红色或黑色。这种颜色属性被用来确保树的某些关键性质,...
红黑树在线生成的一个工具,从网上找的,我这样应该得不到分。大哭https://www.cnblogs.com/bbvi/p/5576201.html 删除可能存在问题,替换节点的兄弟节点为黑色节点时有问题,其他部分是没有问题的,凑合着看看
红黑树性质: 1. 每个结点或红或黑。 2. 根结点为黑色。 3. 每个叶结点(实际上就是NULL指针)都是黑色的。 4. 如果一个结点是红色的,那么它的周边3个节点都是黑色的。 5. 对于每个结点,从该结点到其所有子孙叶结点的...
红黑树添加
实验1:实现红黑树的基本算法, 对n的取值分别为 12、24、36、48、60,随机生成n 个互异的正整数(K1, K2, K3, ……, Kn)作为节点的关键字,向一棵初始空的红黑树中依次插入这n 个节点,统计算法运行所需时间 ,画...