c2java 第2篇 红黑树之插入

红黑树在C++ STL 和 java Collection 里面作为Set, Map 的底层存储结构,非常重要。作为CS树中一个特别树种, 理解了它, 差不多就算入门道了。套用钱砚堂赞王芗斋先生的话:(郭老)夫子之墙高千仞,君既入室且登堂。

/*RBTree.java -- Red Black Tree doc: 0. 红黑树与AVL树的比较: 插入最多只需要2次旋转(插入12时);树高度最多为2*log(n) 1. 红黑树是2-3-4树的二叉表示。 2. 2-3-4树映射为红黑树的特征: 根节点是黑色的; 不可能出现连续两个红节点; 2-3-4树的一个节点对应到红黑树中一个黑节点。 3. 2-3-4树的插入方法: 沿路分裂4-节点;总是在叶子节点处插入。 网上一直有人问下面的R1-R4插入规则是怎么来的,其实是由2,3推导出的。 2-3-4树插入很容易在纸上画出来,节点转换到红黑树也容易;但是直接画 红黑树要对旋转很熟练才行。 4. 关于X的右旋实际上是指把X的位置提升一层,X的父节点下降一层, 即“右转螺旋升”。像六封四闭跟步后的手下按,腰螺旋上升。 关于类和成员的权限,我的做法是: 1. C文件什么都不加默认是extern,java里面什么都不加默认是package-private,即同一目录内访问没有限制。 2. 如果对应的C文件里面函数前面是static, 则java里面的方法加上private。 3. 如果是强调给第三方用,就加上public。 官方参考http://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html author: ludi 2014.03 */ class RBNode> { final static int BLACK = 0, RED = 1; RBNode parent, left, right; int color; T nodeValue; RBNode(T item, RBNode left, RBNode right, RBNode parent, int color) { nodeValue = item; this.left = left; this.right = right; this.parent = parent; this.color = color; } } public class RBTree> { RBNode root; RBNode NIL = null; public RBTree() {/*构造方法: 这样构造NIL使得它可以像其他节点那样参与旋转*/ if (NIL == null) NIL = new RBNode(null, null, null, null, RBNode.BLACK); root = NIL; } public void deleteTree(RBNode t) {/*析构方法*/ if (t != NIL){ deleteTree(t.left); deleteTree(t.right); t = null; } } private void rotate (RBNode pivot, int type) {/*type == 0: 左旋*/ RBNode p = pivot.parent, g = pivot.parent.parent; if(0 == type){ p.right = pivot.left; pivot.left = p; pivot.parent = g; p.parent = pivot; if (p.right != NIL) p.right.parent = p; }else{ p.left = pivot.right; pivot.right = p; pivot.parent = g; p.parent = pivot; if (p.left != NIL) p.left.parent = p; } if (p == root) root = pivot; else if (p == g.right) g.right = pivot; else g.left = pivot; } private void split4Node(RBNode x) {/*提升4-节点并做必要的旋转*/ /*翻转颜色*/ x.color = RBNode.RED; x.left.color = RBNode.BLACK; x.right.color = RBNode.BLACK; RBNode p = x.parent; if (p.color == RBNode.RED){/*如果父节点是红色则需要旋转*/ RBNode g = x.parent.parent; g.color = RBNode.RED; if ( p == g.left && x == p.right ){/*x是g的内部孙子*/ rotate(x, 0); x.color = RBNode.BLACK; p = x; /*准备右旋*/ }else if ( p == g.right && x == p.left ){ rotate(x, 1); x.color = RBNode.BLACK; p = x; }else{ p.color = RBNode.BLACK; } rotate(p, p == g.left ? 1 : 0); } } public boolean add(T item) {/*插入*/ RBNode curr = root, parent = NIL, newNode; while (curr != NIL){/*查找插入点*/ if (curr.nodeValue.equals(item)) return false; /*R1 沿路分裂4-节点*/ if (curr.left.color == RBNode.RED && curr.right.color == RBNode.RED) split4Node(curr); parent = curr; if (item.compareTo(curr.nodeValue) (item, NIL, NIL, parent, RBNode.RED); if (parent == NIL){ root = newNode; }else{ if (item.compareTo(parent.nodeValue) t){ if(t == NIL)return; visitInOrder(t.left); System.out.print(t.nodeValue + " "); visitInOrder(t.right); } int height(RBNode t){ int hl, hr; if(t == NIL)return -1; hl = height(t.left); hr = height(t.right); hl = 1 + (hl > hr ? hl : hr); System.out.print(t.nodeValue + ":" + hl + " "); return hl; } } class Test{ public static void main(String[] arg){ RBTree tree = new RBTree(); //int[] arr = {40, 20, 10, 35, 50, 25, 30}; int[] arr = {2,15,12,4,8,10,25,35,55,11}; for(int x: arr){ tree.add(x); } System.out.println("tree height: "); tree.height(tree.root); System.out.println(); System.out.println("visitInOrder:"); tree.visitInOrder(tree.root); System.out.println(); tree.deleteTree(tree.root); tree = null; } } /* [email protected]:~/java $ javac -encoding UTF-8 RBTree.java && java Test tree height: 2:0 8:0 11:0 10:1 4:2 15:0 55:0 35:1 25:2 12:3 visitInOrder: 2 4 8 10 11 12 15 25 35 55 [email protected]:~/java $ */

由于删除操作比较复杂,准备后面参考有些领悟后再贴上。

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:java xml解析 学习笔记(1)——DOM
下一篇:马踏棋盘算法
相关文章
图文推荐

c2java 第2篇 红黑树之插入
适配器模式
c2java 第2篇 红黑树之插入
Handler的介绍和使用
c2java 第2篇 红黑树之插入
struts2上传文件
c2java 第2篇 红黑树之插入
通过JFreeChart的饼状
分类:默认分类 时间:2015-03-11 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.069 (s). 10 q(s)