haorui215
- 浏览: 194505 次
- 性别:
- 来自: 上海
-
文章分类
最新评论
-
hao3721：
dsfasd
ehcache 使用 -
nihaokid：
方法是不会存在在对象内存中的，它存在于方法区，建议看看jvm的 ...
Java 深层理解 父类引用指向子类对象 -
vissalan：
有一点没看明白Father f1 = (Father)s;这时 ...
Java 深层理解 父类引用指向子类对象 -
咖啡舞者：
非常感谢这种分享精神.
在BREW中实现自己的GUI（8）－IWEB的封装 -
咖啡舞者：
这是创建的代码。
在设备上调的。
界面在手机和模拟器上显示的差异
红黑树可能是要考虑情况最多的BST树了，它有自己的规则（见代码的注释），通过这些规则可以保证花费较小的代价来达到相对平衡。
注意，红黑树仍然不是平衡树，但是统计性能要好于AVL树。
要保持红黑树的规则，主要通过两类操作，一类是换色，一类还是旋转。
红黑树插入主要要解决红-红冲突，而删除主要则解决“双黑”
同样，红黑树的删除节点实现是最复杂的，不过，复杂也就在于考虑的情况多，掌握了这几种情况实现还是不困难。
其实，红黑树其实是一颗扩充的二叉树，所以也是满二叉树，其空节点可以看做是扩充的叶节点。但是红黑树的扩充叶节点是有特殊意义的。
下面是代码：
<!---->package
algorithms.tree;
/**
* R-B Tree has following four rules:
* 1)every node is either red or black
* 2)root and empty node (external leaf node) are always black.
* 3)the red node's parent node must be black
* 4)every simple path start from node X to its descendant contains same number of black node
*
*
* @author yovn
*
*/
public class RBTree < E extends Comparable < E >> extends DefaultBSTree < E > implements BSTree < E > {
public static class RBPrinter < E extends Comparable < E >> implements DefaultBSTree.NodeVisitor < E >
{
@Override
public void visit(E ele) {
}
@Override
public void visitNode(algorithms.tree.DefaultBSTree.BSTNode < E > node) {
RBNode < E > n = (RBNode < E > )node;
if ( ! n.isNull())
System.out.print(n.key + " ( " + (n.color == RBNode.RED ? " RED " : " BLACK " ) + " ), " );
}
}
static class RBNode < E extends Comparable < E >> extends BSTNode < E >
{
static final boolean RED = false ;
static final boolean BLACK = true ;
RBNode < E > parent;
boolean color; // red or black
RBNode(RBNode < E > p,E key, boolean color) {
super (key);
this .color = color;
this .parent = p;
}
final boolean isNull(){ return key == null ;}
}
@Override
public final boolean delete(E ele) {
RBNode < E > cur;
int cmp;
if (root == null ) return false ;
cur = (RBNode < E > )root;
while ( ! cur.isNull() && (cmp = ele.compareTo(cur.key)) != 0 )
{
if (cmp < 0 )cur = (RBNode < E > )cur.left;
else cur = (RBNode < E > )cur.right;
}
if (cur.isNull())
{
// can't find specified key
return false ;
}
if ( ! ((RBNode < E > )cur.left).isNull() &&! ((RBNode < E > )cur.right).isNull())
{
RBNode < E > prev = (RBNode < E > )cur.left;
while ( ! ((RBNode < E > )prev.right).isNull())
{
prev = (RBNode < E > )prev.right;
}
cur.key = prev.key;
cur = prev;
}
if ( ! ((RBNode < E > )cur.left).isNull())
{
if (cur == root) {
root = cur.left;
((RBNode < E > )root).color = RBNode.BLACK;
return true ;
}
if (cur.parent.left == cur)
{
cur.parent.left = cur.left;
((RBNode < E > )cur.left).parent = cur.parent;
}
else
{
cur.parent.right = cur.left;
((RBNode < E > )cur.left).parent = cur.parent;
}
if (cur.color == RBNode.BLACK)
{
((RBNode < E > )cur.left).color = RBNode.BLACK;
}
}
else if ( ! ((RBNode < E > )cur.right).isNull())
{
if (cur == root) {
root = cur.right;
((RBNode < E > )root).color = RBNode.BLACK;
return true ;
}
if (cur.parent.left == cur)
{
cur.parent.left = cur.right;
((RBNode < E > )cur.right).parent = cur.parent;
}
else
{
cur.parent.right = cur.right;
((RBNode < E > )cur.right).parent = cur.parent;
}
if (cur.color == RBNode.BLACK)
{
((RBNode < E > )cur.right).color = RBNode.BLACK;
}
}
else
{
if (cur == root)
{
root = null ;
return true ;
}
RBNode < E > todo;
if (cur.parent.left == cur)
{
todo = newNullNode(cur.parent);
cur.parent.left = todo;
}
else
{
todo = newNullNode(cur.parent);
cur.parent.right = todo;
}
if (cur.color == RBNode.BLACK)
{
// now todo is a double black node, we will eliminate the double black
fixup_double_black(todo);
}
}
return true ;
}
@Override
public E findMax() {
if (isEmpty()) return null ;
BSTNode < E > node = root;
while ( ! ((RBNode < E > )node.right).isNull())
{
node = node.right;
}
return node.key;
}
@Override
public E findMin() {
if (isEmpty()) return null ;
BSTNode < E > node = root;
while ( ! ((RBNode < E > )node.left).isNull())
{
node = node.left;
}
return node.key;
}
private final RBNode < E > newNullNode(RBNode < E > p)
{
return new RBNode < E > (p, null ,RBNode.BLACK);
}
private final RBNode < E > newNormalNode(RBNode < E > p,E key, boolean color)
{
RBNode < E > node = new RBNode < E > (p,key,color);
node.left = newNullNode(node);
node.right = newNullNode(node);
return node;
}
private final void fixup_double_black(RBNode < E > cur) {
RBNode < E > sibling;
RBNode < E > p;
while (cur != root) // until its parent,parent maybe double black
{
p = cur.parent;
if (p.left == cur)
{
sibling = (RBNode < E > )p.right;
if (sibling.color == RBNode.RED)
{
rotate_from_right(p);
p.color = RBNode.RED;
sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation
// this case transformed to another case handled in other place
}
else
{
if (((RBNode < E > )sibling.right).color == RBNode.RED)
{
rotate_from_right(p);
sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
p.color = RBNode.BLACK;
((RBNode < E > )sibling.right).color = RBNode.BLACK;
// ok done!
return ;
}
else if (((RBNode < E > )sibling.left).color == RBNode.RED)
{
rotate_from_left(sibling);
sibling.color = RBNode.RED;
sibling.parent.color = RBNode.BLACK; // its parent was previously be its left child, remember we have done a left rotation from sibling
// now transformed to previous case, double black 's sibling(black) have right child colored red
}
else // sibling's two children are both black
{
// re-coloring the sibling and parent
sibling.color = RBNode.RED;
if (p.color == RBNode.BLACK)
{
cur = p;
// now the cur node was not double black node ,but p was a double black
}
else
{
p.color = RBNode.BLACK; // eliminated the double black node
return ;
}
}
}
}
else
{
sibling = (RBNode < E > )p.left;
if (sibling.color == RBNode.RED)
{
rotate_from_left(p);
p.color = RBNode.RED;
sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation
// this case transformed to another case handled in other place
}
else
{
if (((RBNode < E > )sibling.left).color == RBNode.RED)
{
rotate_from_left(p);
sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
p.color = RBNode.BLACK;
((RBNode < E > )sibling.left).color = RBNode.BLACK;
// ok done!
return ;
}
else if (((RBNode < E > )sibling.right).color == RBNode.RED)
{
rotate_from_right(sibling);
sibling.color = RBNode.RED;
sibling.parent.color = RBNode.BLACK; // its parent was previously be its right child, remember we have done a left rotation from sibling
// now transformed to previous case, double black 's sibling(black) have right child colored red
}
else // sibling's two children are both black
{
// re-coloring the sibling and parent
sibling.color = RBNode.RED;
if (p.color == RBNode.BLACK)
{
cur = p;
// now the cur node was not double black node ,but p was a double black
}
else
{
p.color = RBNode.BLACK; // eliminated the double black node
return ;
}
}
}
}
}
}
@Override
public final void insert(E ele) {
if (root == null )
{
root = newNormalNode( null ,ele,RBNode.BLACK); // now root's black-height(bh) is 1
return ;
}
RBNode < E > ret = _insert((RBNode < E > )root,ele); // first insert it
_insert_fixup(ret); // fix-up the R-B tree from node cur;
}
private final void _insert_fixup(RBNode < E > cur) {
RBNode < E > p,g;
// we should fix until it is black colored
while (cur != root && cur.color == RBNode.RED)
{
p = cur.parent;
if (p.color == RBNode.BLACK)
{
// that's fine, the insertion will not change any black height, and will not violate any rule.
return ;
}
g = p.parent; // we can assume the p is not null now.
if (p == g.left)
{
RBNode < E > uncle = (RBNode < E > )g.right;
if (uncle.color == RBNode.RED)
{
// re-coloring
g.color = RBNode.RED;
uncle.color = p.color = RBNode.BLACK;
// now the g maybe conflict with its parent;
cur = g;
}
else
{
if (cur == p.right)
{
// this case we should do left rotation, and then it will transform to next case
cur = rotate_from_right(p);
cur = (RBNode < E > )cur.left;
// transformed to next case
}
cur = rotate_from_left(g);
cur.color = RBNode.BLACK;
((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;
}
}
else
{
RBNode < E > uncle = (RBNode < E > )g.left;
if (uncle.color == RBNode.RED)
{
// re-coloring
g.color = RBNode.RED;
uncle.color = p.color = RBNode.BLACK;
// now the g maybe conflict with its parent;
cur = g;
}
else
{
if (cur == p.left)
{
// this case we should do right rotation, and then it will transform to next case
cur = rotate_from_left(p);
cur = (RBNode < E > )cur.right;
// transformed to next case
}
cur = rotate_from_right(g);
cur.color = RBNode.BLACK;
((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;
}
}
}
((RBNode < E > )root).color = RBNode.BLACK;
}
private final RBNode < E > rotate_from_right(RBNode < E > p) {
RBNode < E > g = p.parent;
RBNode < E > cur = (RBNode < E > )p.right;
p.right = cur.left;
if (cur.left != null )((RBNode < E > )cur.left).parent = p;
cur.left = p;
p.parent = cur;
if (g != null )
{
if (g.left == p)g.left = cur;
else g.right = cur;
}
else root = cur;
cur.parent = g;
return cur;
}
private final RBNode < E > rotate_from_left(RBNode < E > p) {
RBNode < E > co
/**
* R-B Tree has following four rules:
* 1)every node is either red or black
* 2)root and empty node (external leaf node) are always black.
* 3)the red node's parent node must be black
* 4)every simple path start from node X to its descendant contains same number of black node
*
*
* @author yovn
*
*/
public class RBTree < E extends Comparable < E >> extends DefaultBSTree < E > implements BSTree < E > {
public static class RBPrinter < E extends Comparable < E >> implements DefaultBSTree.NodeVisitor < E >
{
@Override
public void visit(E ele) {
}
@Override
public void visitNode(algorithms.tree.DefaultBSTree.BSTNode < E > node) {
RBNode < E > n = (RBNode < E > )node;
if ( ! n.isNull())
System.out.print(n.key + " ( " + (n.color == RBNode.RED ? " RED " : " BLACK " ) + " ), " );
}
}
static class RBNode < E extends Comparable < E >> extends BSTNode < E >
{
static final boolean RED = false ;
static final boolean BLACK = true ;
RBNode < E > parent;
boolean color; // red or black
RBNode(RBNode < E > p,E key, boolean color) {
super (key);
this .color = color;
this .parent = p;
}
final boolean isNull(){ return key == null ;}
}
@Override
public final boolean delete(E ele) {
RBNode < E > cur;
int cmp;
if (root == null ) return false ;
cur = (RBNode < E > )root;
while ( ! cur.isNull() && (cmp = ele.compareTo(cur.key)) != 0 )
{
if (cmp < 0 )cur = (RBNode < E > )cur.left;
else cur = (RBNode < E > )cur.right;
}
if (cur.isNull())
{
// can't find specified key
return false ;
}
if ( ! ((RBNode < E > )cur.left).isNull() &&! ((RBNode < E > )cur.right).isNull())
{
RBNode < E > prev = (RBNode < E > )cur.left;
while ( ! ((RBNode < E > )prev.right).isNull())
{
prev = (RBNode < E > )prev.right;
}
cur.key = prev.key;
cur = prev;
}
if ( ! ((RBNode < E > )cur.left).isNull())
{
if (cur == root) {
root = cur.left;
((RBNode < E > )root).color = RBNode.BLACK;
return true ;
}
if (cur.parent.left == cur)
{
cur.parent.left = cur.left;
((RBNode < E > )cur.left).parent = cur.parent;
}
else
{
cur.parent.right = cur.left;
((RBNode < E > )cur.left).parent = cur.parent;
}
if (cur.color == RBNode.BLACK)
{
((RBNode < E > )cur.left).color = RBNode.BLACK;
}
}
else if ( ! ((RBNode < E > )cur.right).isNull())
{
if (cur == root) {
root = cur.right;
((RBNode < E > )root).color = RBNode.BLACK;
return true ;
}
if (cur.parent.left == cur)
{
cur.parent.left = cur.right;
((RBNode < E > )cur.right).parent = cur.parent;
}
else
{
cur.parent.right = cur.right;
((RBNode < E > )cur.right).parent = cur.parent;
}
if (cur.color == RBNode.BLACK)
{
((RBNode < E > )cur.right).color = RBNode.BLACK;
}
}
else
{
if (cur == root)
{
root = null ;
return true ;
}
RBNode < E > todo;
if (cur.parent.left == cur)
{
todo = newNullNode(cur.parent);
cur.parent.left = todo;
}
else
{
todo = newNullNode(cur.parent);
cur.parent.right = todo;
}
if (cur.color == RBNode.BLACK)
{
// now todo is a double black node, we will eliminate the double black
fixup_double_black(todo);
}
}
return true ;
}
@Override
public E findMax() {
if (isEmpty()) return null ;
BSTNode < E > node = root;
while ( ! ((RBNode < E > )node.right).isNull())
{
node = node.right;
}
return node.key;
}
@Override
public E findMin() {
if (isEmpty()) return null ;
BSTNode < E > node = root;
while ( ! ((RBNode < E > )node.left).isNull())
{
node = node.left;
}
return node.key;
}
private final RBNode < E > newNullNode(RBNode < E > p)
{
return new RBNode < E > (p, null ,RBNode.BLACK);
}
private final RBNode < E > newNormalNode(RBNode < E > p,E key, boolean color)
{
RBNode < E > node = new RBNode < E > (p,key,color);
node.left = newNullNode(node);
node.right = newNullNode(node);
return node;
}
private final void fixup_double_black(RBNode < E > cur) {
RBNode < E > sibling;
RBNode < E > p;
while (cur != root) // until its parent,parent maybe double black
{
p = cur.parent;
if (p.left == cur)
{
sibling = (RBNode < E > )p.right;
if (sibling.color == RBNode.RED)
{
rotate_from_right(p);
p.color = RBNode.RED;
sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation
// this case transformed to another case handled in other place
}
else
{
if (((RBNode < E > )sibling.right).color == RBNode.RED)
{
rotate_from_right(p);
sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
p.color = RBNode.BLACK;
((RBNode < E > )sibling.right).color = RBNode.BLACK;
// ok done!
return ;
}
else if (((RBNode < E > )sibling.left).color == RBNode.RED)
{
rotate_from_left(sibling);
sibling.color = RBNode.RED;
sibling.parent.color = RBNode.BLACK; // its parent was previously be its left child, remember we have done a left rotation from sibling
// now transformed to previous case, double black 's sibling(black) have right child colored red
}
else // sibling's two children are both black
{
// re-coloring the sibling and parent
sibling.color = RBNode.RED;
if (p.color == RBNode.BLACK)
{
cur = p;
// now the cur node was not double black node ,but p was a double black
}
else
{
p.color = RBNode.BLACK; // eliminated the double black node
return ;
}
}
}
}
else
{
sibling = (RBNode < E > )p.left;
if (sibling.color == RBNode.RED)
{
rotate_from_left(p);
p.color = RBNode.RED;
sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation
// this case transformed to another case handled in other place
}
else
{
if (((RBNode < E > )sibling.left).color == RBNode.RED)
{
rotate_from_left(p);
sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
p.color = RBNode.BLACK;
((RBNode < E > )sibling.left).color = RBNode.BLACK;
// ok done!
return ;
}
else if (((RBNode < E > )sibling.right).color == RBNode.RED)
{
rotate_from_right(sibling);
sibling.color = RBNode.RED;
sibling.parent.color = RBNode.BLACK; // its parent was previously be its right child, remember we have done a left rotation from sibling
// now transformed to previous case, double black 's sibling(black) have right child colored red
}
else // sibling's two children are both black
{
// re-coloring the sibling and parent
sibling.color = RBNode.RED;
if (p.color == RBNode.BLACK)
{
cur = p;
// now the cur node was not double black node ,but p was a double black
}
else
{
p.color = RBNode.BLACK; // eliminated the double black node
return ;
}
}
}
}
}
}
@Override
public final void insert(E ele) {
if (root == null )
{
root = newNormalNode( null ,ele,RBNode.BLACK); // now root's black-height(bh) is 1
return ;
}
RBNode < E > ret = _insert((RBNode < E > )root,ele); // first insert it
_insert_fixup(ret); // fix-up the R-B tree from node cur;
}
private final void _insert_fixup(RBNode < E > cur) {
RBNode < E > p,g;
// we should fix until it is black colored
while (cur != root && cur.color == RBNode.RED)
{
p = cur.parent;
if (p.color == RBNode.BLACK)
{
// that's fine, the insertion will not change any black height, and will not violate any rule.
return ;
}
g = p.parent; // we can assume the p is not null now.
if (p == g.left)
{
RBNode < E > uncle = (RBNode < E > )g.right;
if (uncle.color == RBNode.RED)
{
// re-coloring
g.color = RBNode.RED;
uncle.color = p.color = RBNode.BLACK;
// now the g maybe conflict with its parent;
cur = g;
}
else
{
if (cur == p.right)
{
// this case we should do left rotation, and then it will transform to next case
cur = rotate_from_right(p);
cur = (RBNode < E > )cur.left;
// transformed to next case
}
cur = rotate_from_left(g);
cur.color = RBNode.BLACK;
((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;
}
}
else
{
RBNode < E > uncle = (RBNode < E > )g.left;
if (uncle.color == RBNode.RED)
{
// re-coloring
g.color = RBNode.RED;
uncle.color = p.color = RBNode.BLACK;
// now the g maybe conflict with its parent;
cur = g;
}
else
{
if (cur == p.left)
{
// this case we should do right rotation, and then it will transform to next case
cur = rotate_from_left(p);
cur = (RBNode < E > )cur.right;
// transformed to next case
}
cur = rotate_from_right(g);
cur.color = RBNode.BLACK;
((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;
}
}
}
((RBNode < E > )root).color = RBNode.BLACK;
}
private final RBNode < E > rotate_from_right(RBNode < E > p) {
RBNode < E > g = p.parent;
RBNode < E > cur = (RBNode < E > )p.right;
p.right = cur.left;
if (cur.left != null )((RBNode < E > )cur.left).parent = p;
cur.left = p;
p.parent = cur;
if (g != null )
{
if (g.left == p)g.left = cur;
else g.right = cur;
}
else root = cur;
cur.parent = g;
return cur;
}
private final RBNode < E > rotate_from_left(RBNode < E > p) {
RBNode < E > co
分享到：
发表评论
-
Java实现通用线程池
2009-10-12 16:17 1033URL: http://blog.csdn.net/polar ... -
java 内存溢出分析
2009-10-09 15:44 1198内存溢出是指应用系统中存在无法回收的内存或使用的内存过多，最终 ... -
Java的内存泄漏
2009-10-09 13:27 801Java 的一个重要优点就 ... -
dom4j操作xml基础--Visitor访问模式解析XML
2009-07-03 17:15 1323http://www.blogjava.net/bulktre ... -
Dom4j的全面解析
2009-07-03 17:03 983作者：冰云 icecloud(AT)sin ... -
关于java使用javacomm20-win32实践总结
2009-06-21 23:34 723由于这几天要通过java调 ... -
20非常有用的Java程序片段 (下)
2009-05-26 14:29 107717. 把 Array 转换成 Map vi ... -
20非常有用的Java程序片段 (中)
2009-05-26 14:08 88112. 单实例Singleton 示例 请先阅读这篇文章 ... -
20非常有用的Java程序片段 (上)
2009-05-26 14:02 941下面是20个非常有用的Java程序片段，希望能对你有用。 1 ... -
java实现 冒泡排序 插入排序 选择排序
2009-03-16 00:47 1064package test.sort; public clas ... -
排序算法复习（Java实现）(二）： 归并排序，堆排序，桶式排序，基数排序
2009-03-16 00:40 1142转自：http://www.blogjava.net/java ... -
排序算法复习（Java实现）(一）： 插入，冒泡，选择，Shell,快速排序
2009-03-16 00:37 881转自：http://www.blogjava.net/java ... -
Java 深层理解 父类引用指向子类对象
2009-03-10 11:44 2637从对象的内存角度来理解试试. 假设现在有一个父类Father, ... -
java native method
2009-03-02 20:40 953一. 什么是Native Method 简单地讲，一个Na ... -
java 简介--学习笔记
2009-02-22 22:26 731一 java 特点 1 、简单 Java 设计 ... -
String理解
2009-02-21 00:44 836要理解 java中String的运作方式，必须明确一点：Str ... -
Java的时间处理
2009-02-21 00:42 8791. Java计算时间依靠1970 ...
相关推荐
红黑树java实现，代码能实现，详细。
红黑树是一种数据结构，是树的一种，用java实现红黑树，包括主要程序和测试程序。
红黑树的增删查的Java实现，注解详细，可配合该博客以参考学习：http://blog.csdn.net/oLanMoMo/article/details/50686267
红黑树实现java代码，供大家参考，具体详解请参见我的博客http://blog.csdn.net/clamclam/article/details/49545477
用java实现的红黑树，参照《算法导论》第三版实现。OrdRow.java--这个为节点的定义；OrdDataSet.java为红黑树的实现
JAVA实现的红黑树，可以实现插入删除查找功能，使用了泛型
本资源是红黑树的插入算法的java实现，有需要的可以下了看看
java实现的红黑树，希望对初学者提供帮助
红黑树 红黑树_基于Java实现的红黑树数据结构
Java写的红黑树，按照《算法导论》上的算法写的，包括建树、删除节点、插入节点、计算黑高、打印等，只包括源码，需要自己建工程
描述了红黑树的基本结构 以及与二叉树的性能比较
Java-红-黑-树 Java 1.7 中红黑树的实现 此代码扩展自 Mark Allen Weiss 在和维基百科（特别是移除操作）
通过Java实现红黑树及其可视化 对于节点的定义，包含节点的数值、节点的颜色、节点的父节点、节点的左右叶子结点 通过Java实现红黑树，包括红黑树的插入操作、删除操作、维护红黑树性质的操作以及常用的方法函数...
使用java语言编程实现了平衡二叉树、二叉树、二叉搜索树、红黑树四种树相关的数据结构，还实现了多种排序算法。并且是在J2EE下实现的。
算法导论中红黑树的实现。包括插入，删除，旋转。 能够实现红黑树的基本操作
NULL 博文链接：https://709002341.iteye.com/blog/2259886
描述： 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋、右旋等），删除，搜索（指定Key值节点）。 另外，红黑树实现计算树黑高的算法。 1).插入测试，输入 8，11，17，15，6，1，22，25，27...
java 实现红黑树的增删改查
红黑树、二叉平衡树、二叉排序树的java实现，做了泛型封装，可以装任何对象，其中还附带工具类，可以友好一点地打印树，还有各种遍历树方法的递归实现和非递归实现。
红黑树 使用Java语言实现的rbtree红黑树