浏览 10785 次
|
锁定老帖子 主题：二叉树和红黑树的java实现
精华帖 (1) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-02-05
最后修改：2011-02-05
二叉查找树代码大致如下：
二叉树节点类：
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:很久以前自己写的代码了，这里整理了一下，搬到博客来，其中功能不是很完整，比如二叉树就没有写删除功能。 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-02-11
二叉树的插入算法貌似有问题.我download下来,试了一下,打印的树是错的
|
| 返回顶楼 | |
|
发表时间：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) ) ) 结果是正确的啊，可能是打印的树形不太好吧，说明一下 每一个节点值+逗号，然后换行，然后左节点+逗号，然后换行，然后右节点。如果该节点为某一节点的子节点，那么它前方带有左括弧，它的右子节点带有右括弧。 唉，等有时间了，我加下代码注释，另外改进下代码吧，看着真囧。 |
| 返回顶楼 | |
|
发表时间：2011-02-26
貌似JDK源码里有这些实现吧。。。
|
| 返回顶楼 | |
|
发表时间：2011-02-28
测试结果如下： (1, Nil, (13, (2, Nil, (6, (4, Nil, Nil) , (8, Nil, (11, (9, Nil, Nil) , Nil) ) ) ) , (17, Nil, Nil) ) ) 优雅.... |
| 返回顶楼 | |
|
发表时间：2011-09-22
TreeMap 就是基于红黑树的实现
|
| 返回顶楼 | |
