[入门] D语言的红黑树的添加和删除操作，谁能教教我怎么从上倒下一次遍历完成的算法
 |
myyxm
2007-12-29
module dstl.drbtree;
private import std.stdio;
private import dstl.dfreelist;
private enum rb { red = 0 , block}
private enum lr { left = 0,right = 1,none = 2}
public class rbTreeNode(T)
{
T value;
private rbTreeNode!(T) left,right,parent;
private rb color;
public void set(T v,rbTreeNode!(T) l = null,rbTreeNode!(T) r = null,rbTreeNode!(T) p = null,rb c = rb.red)
{
value = v;left = l;right =r;parent = p;color = c;
}
public void set(rbTreeNode!(T) l = null,rbTreeNode!(T) r = null,rbTreeNode!(T) p = null,rb c = rb.red)
{
left = l;right =r;parent = p;color = c;
}
public this()
{
}
mixin freelist!(rbTreeNode!(T));
}
public class rbTree(T)
{
private alias rbTreeNode!(T) rbnode;
private rbnode m_head,nullnode;
public this(T value)
{
nullnode = rbnode.alloc();
nullnode.set(null,null,null,rb.block);
m_head = rbnode.alloc();
m_head.set(value,nullnode,nullnode,null,rb.block);
nullnode.parent = m_head;
}
public void list(rbTreeNode!(T) node = null)
{
static int i=0;
if(node is null)
node = m_head;
++i;
if(node !is nullnode)
{
if(node.parent is null)
node.parent = nullnode;
writefln("i:%d,node.value:%d,node.color:%d\tnode.left:%d,node.right:%d,node.parent:%d",i,node.value,node.color,node.left.value,node.right.value,node.parent.value);
if(node.parent is nullnode)
node.parent = null;
}
else
return;
list(node.left);
list(node.right);
}
public void insert(T value)
{
nullnode.set(null,null,null,rb.block);
debug
{
writefln("root value:%d",m_head.value);
writefln("insert value:%d",value);
}
//寻找插入地方
rbnode node = m_head;
rbnode currect = null;
while(node !is nullnode)
{
currect = node;
if(node.value > value)
node = node.left;
else if(node.value < value)
node = node.right;
else
return;
}
//当前位置为空,表明树是空的.
if(currect is null)
{
m_head = rbnode.alloc();
m_head.set(value,nullnode,nullnode,null,rb.block);
return;
}
node = rbnode.alloc();
node.set(value,nullnode,nullnode,currect,rb.red);
if(currect.value > value)
currect.left = node;
else
currect.right = node;
while(node.parent.color is rb.red)
{
//父亲和叔叔都是红色
if(node.parent.parent.left.color is node.parent.parent.right.color)
{
node.parent.parent.left.color = node.parent.parent.right.color = rb.block;
node.parent.parent.color = rb.red;
node = node.parent.parent;
}
//开始旋转
else
{
//父亲是爷爷的左子树
if(node.parent is node.parent.parent.left)
{
debug
{
writefln("...father is grand left,node value:%d,father value:%d,grand value:%d",node.value,node.parent.value,node.parent.parent.value);
}
if(node is node.parent.right)
{
rotateLeft(node.parent);
node = node.left;
debug
{
writefln(".....father is grand left,and node is father right,node value:%d,father value:%d,grand value:%d",node.value,node.parent.value,node.parent.parent.value);
}
}
rotateRight(node.parent.parent);
}
else if(node.parent is node.parent.parent.right)
{
debug
{
writefln("...father is grand right,node value:%d,father value:%d,grand value:%d",node.value,node.parent.value,node.parent.parent.value);
}
if(node is node.parent.left)
{
this.rotateRight(node.parent);
node = node.right;
debug
{
writefln(".....father is grand right,and node is father left,node value:%d,father value:%d,grand value:%d",node.value,node.parent.value,node.parent.parent.value);
}
}
rotateLeft(node.parent.parent);
}
node = node.parent;
node.left.color = node.right.color = rb.block;
node.color = rb.red;
debug
{
writefln("...flip end,node value:%d,left value:%d,right value:%d",node.value,node.left.value,node.right.value);
}
}
if(node is m_head)
{
node.color = rb.block;
break;
}
}
}
public void remove(T value)
{
//查询删除的位置
nullnode.set(null,null,null,rb.block);
rbnode delnode = m_head;
rbnode x;
rbnode currect = null;
while(delnode !is nullnode)
{
if(delnode.value > value)
delnode = delnode.left;
else if(delnode.value < value)
delnode = delnode.right;
else
break;
}
if(delnode is nullnode)
throw new Exception("delete error");
//如果当前节点有左右孩子
currect = delnode;
if(currect.left !is nullnode && currect.right ! is nullnode)
{
delnode = currect.right;
while(delnode.left !is nullnode)
delnode = delnode.left;
currect.value = delnode.value;
currect = delnode;
}
//寻找结束，删除delnode，并且保留替换的节点
if(currect.left !is nullnode)
{
if(currect is currect.parent.left)
currect.parent.left = currect.left;
else
currect.parent.right = currect.left;
currect.left.parent = currect.parent;
delnode = currect.left;
}
else if(currect.right !is nullnode)
{
if(currect is currect.parent.left)
currect.parent.left = currect.right;
else
currect.parent.right = currect.right;
currect.right.parent = currect.parent;
delnode = currect.right;
}
else
{
if(currect is currect.parent.left)
currect.parent.left = nullnode;
else
currect.parent.right = nullnode;
delnode = nullnode;
delnode.parent = currect.parent;
//writefln("currect.value:%d,currect.parent.value:%d",currect.value,currect.parent.value);
}
//writefln("delnode.parent:%d\t delnode.value:%d,delnode.color:%d",delnode.parent.value,delnode.value,delnode.color);
/*
currect 为删除的节点
delnode 为替代的节点
翻转颜色，恢复红黑树性质
*/
if(currect.color is rb.block)
{
while(1)
{
if(delnode.color is rb.red || delnode is m_head)
{
delnode.color = rb.block;
break;
}
//代替节点为父节点的左子树
if(delnode is delnode.parent.left)
{
debug
{
writefln("delnode is delnode.parent.left");
writefln("delnode.color: %d\tdelnode.value:%d",delnode.color,delnode.value);
writefln("delnode.parent.color:%d\tdelnode.parent.value:%d",delnode.parent.color,delnode.parent.value);
writefln("delnode.parent.right.color:%d\tdelnode.parent.left.value:%d",delnode.parent.right.color,delnode.parent.right.value);
writefln("delnode.parent.right.left.color:%d\tdelnode.parent.right.left.value:%d",delnode.parent.right.left.color,delnode.parent.right.left.value);
writefln("delnode.parent.right.right.color:%d\tdelnode.parent.right.right.value:%d",delnode.parent.right.right.color,delnode.parent.right.right.value);
}
//case 1:兄弟节点为红色
if(delnode.parent.right.color is rb.red)
{
//调整颜色
delnode.parent.color = rb.red;
delnode.parent.right.color = rb.block;
//对父亲节点进行做旋转
rotateLeft(delnode.parent);
}
//case 2,3,4:兄弟节点是黑色
if(delnode.parent.right.color is rb.block)
{
//case 2：子侄节点都是黑色
if(delnode.parent.right.left.color is rb.block && delnode.parent.right.right.color is rb.block)
{
delnode.parent.right.color = rb.red;
delnode = delnode.parent;
continue;
}
//case 3:
if(delnode.parent.right.left.color is rb.red && delnode.parent.right.right.color is rb.block)
{
delnode.parent.right.left.color = rb.block;
delnode.parent.right.color = rb.red;
rotateRight(delnode.parent.right);
}
if(delnode.parent.right.right.color is rb.red && delnode.parent.right.left.color is rb.block)
{
delnode.parent.right.right.color = rb.block;
delnode.parent.right.color = rb.red;
rotateLeft(delnode.parent);
break;
}
}
}
if(delnode is delnode.parent.right)
{
debug
{
writefln("delnode is delnode.parent.right");
writefln("delnode.color: %d\tdelnode.value:%d",delnode.color,delnode.value);
writefln("delnode.parent.color:%d\tdelnode.parent.value:%d",delnode.parent.color,delnode.parent.value);
writefln("delnode.parent.left.color:%d\tdelnode.parent.left.value:%d",delnode.parent.left.color,delnode.parent.left.value);
writefln("delnode.parent.left.left.color:%d\tdelnode.parent.left.left.value:%d",delnode.parent.left.left.color,delnode.parent.left.left.value);
writefln("delnode.parent.left.right.color:%d\tdelnode.parent.left.right.value:%d",delnode.parent.left.right.color,delnode.parent.left.right.value);
}
//case 1:
if(delnode.parent.left.color is rb.red)
{
delnode.parent.left.color = rb.block;
delnode.parent.color = rb.red;
rotateRight(delnode.parent);
}
//case 2,3,4:
if(delnode.parent.left.color is rb.block)
{
//case 2:
if(delnode.parent.left.left.color is rb.block && delnode.parent.left.right.color is rb.block)
{
delnode.parent.left.color = rb.red;
delnode = delnode.parent;
continue;
}
//case 3:
if(delnode.parent.left.right.color is rb.red && delnode.parent.left.left.color is rb.block)
{
//writefln("run case 2");
delnode.parent.left.right.color = rb.block;
delnode.parent.left.color = rb.red;
rotateLeft(delnode.parent.left);
//writefln("run case 2");
}
//case 4:
if(delnode.parent.left.left.color is rb.red && delnode.parent.left.right.color is rb.block)
{
delnode.parent.left.left.color = rb.block;
delnode.parent.left.color = rb.red;
rotateRight(delnode.parent);
//writefln("run case 4");
break;
}
}
}
}
}
rbnode.release(currect);
}
/*
x x
/ /
node n
/ \ -> / \
a n node c
/ \ / \
b c a b
不改变node的指向
*/
public void rotateLeft(rbnode node)
{
rbnode n = node.right;
node.right = n.left;
node.right.parent = node;
n.left = node;
n.parent = node.parent;
node.parent = n;
if(n.parent !is null)
{
if(n.parent.left is node)
n.parent.left = n;
else
n.parent.right = n;
}
else
m_head = n;
}
/*
x x
\ \
node -> n
/ \ / \
n a b node
/ \ / \
b c c a
不改变node的指向
*/
public void rotateRight(rbnode node)
{
rbnode n = node.left;
node.left = n.right;
node.left.parent = node;
n.right = node;
//writefln("n value:%d",n.value);
n.parent = node.parent;
if(node is null)
writefln("node is null");
node.parent = n;
if(n.parent !is null)
{
if(n.parent.left is node)
n.parent.left = n;
else
n.parent.right = n;
}
else
{
m_head = n;
}
}
}
//测试
rbTreeNode!(int) node = rbTreeNode!(int).alloc();
node.set(1,node,node,node);
rbTree!(int) rb = new rbTree!(int)(100);
rb.insert(50);
rb.insert(77);
rb.insert(7);
rb.insert(66);
rb.insert(122);
rb.insert(18);
rb.insert(32);
rb.insert(246);
rb.remove(66);
rb.insert(66);
rb.insert(98);
rb.list();
getch();
return 0;
输出：
root value:100
insert value:50
root value:100
insert value:77
...father is grand left,node value:77,father value:50,grand value:100
.....father is grand left,and node is father right,node value:50,father value:77
,grand value:100
...flip end,node value:77,left value:50,right value:100
root value:77
insert value:7
root value:77
insert value:66
root value:77
insert value:122
root value:77
insert value:18
root value:77
insert value:32
...father is grand right,node value:32,father value:18,grand value:7
...flip end,node value:18,left value:7,right value:32
...father is grand left,node value:18,father value:50,grand value:77
...flip end,node value:50,left value:18,right value:77
root value:50
insert value:246
...father is grand right,node value:246,father value:122,grand value:100
...flip end,node value:122,left value:100,right value:246
delnode is delnode.parent.left
delnode.color: 1 delnode.value:0
delnode.parent.color:1 delnode.parent.value:77
delnode.parent.right.color:0 delnode.parent.left.value:122
delnode.parent.right.left.color:1 delnode.parent.right.left.value:100
delnode.parent.right.right.color:1 delnode.parent.right.right.value:246
root value:50
insert value:66
i:1,node.value:50,node.color:1 node.left:18,node.right:122,node.parent:0
i:2,node.value:18,node.color:1 node.left:7,node.right:32,node.parent:50
i:3,node.value:7,node.color:1 node.left:0,node.right:0,node.parent:18
i:6,node.value:32,node.color:1 node.left:0,node.right:0,node.parent:18
i:9,node.value:122,node.color:1 node.left:77,node.right:246,node.parent:50
i:10,node.value:77,node.color:1 node.left:66,node.right:100,node.parent:122
i:11,node.value:66,node.color:0 node.left:0,node.right:0,node.parent:77
i:14,node.value:100,node.color:0 node.left:0,node.right:0,node.parent:77
i:17,node.value:246,node.color:1 node.left:0,node.right:0,node.parent:122
please input any key to end ........
E:\dprjects\dstl>dstl
root value:100
insert value:50
root value:100
insert value:77
...father is grand left,node value:77,father value:50,grand value:100
.....father is grand left,and node is father right,node value:50,father value:77
,grand value:100
...flip end,node value:77,left value:50,right value:100
root value:77
insert value:7
root value:77
insert value:66
root value:77
insert value:122
root value:77
insert value:18
root value:77
insert value:32
...father is grand right,node value:32,father value:18,grand value:7
...flip end,node value:18,left value:7,right value:32
...father is grand left,node value:18,father value:50,grand value:77
...flip end,node value:50,left value:18,right value:77
root value:50
insert value:246
...father is grand right,node value:246,father value:122,grand value:100
...flip end,node value:122,left value:100,right value:246
delnode is delnode.parent.left
delnode.color: 1 delnode.value:0
delnode.parent.color:1 delnode.parent.value:77
delnode.parent.right.color:0 delnode.parent.left.value:122
delnode.parent.right.left.color:1 delnode.parent.right.left.value:100
delnode.parent.right.right.color:1 delnode.parent.right.right.value:246
root value:50
insert value:66
root value:50
insert value:98
i:1,node.value:50,node.color:1 node.left:18,node.right:122,node.parent:0
i:2,node.value:18,node.color:1 node.left:7,node.right:32,node.parent:50
i:3,node.value:7,node.color:1 node.left:0,node.right:0,node.parent:18
i:6,node.value:32,node.color:1 node.left:0,node.right:0,node.parent:18
i:9,node.value:122,node.color:1 node.left:77,node.right:246,node.parent:50
i:10,node.value:77,node.color:0 node.left:66,node.right:100,node.parent:122
i:11,node.value:66,node.color:1 node.left:0,node.right:0,node.parent:77
i:14,node.value:100,node.color:1 node.left:98,node.right:0,node.parent:77
i:15,node.value:98,node.color:0 node.left:0,node.right:0,node.parent:100
i:19,node.value:246,node.color:1 node.left:0,node.right:0,node.parent:122
算法来源：http://www.linuxforum.net/forum/showflat.php?Cat=&Board=linuxK&Number=639737&page=0&view=collapsed&sb=5&o=7&fpart=
|
 |
oldrev
2007-12-29
参考这个：
http://www.dsource.org/projects/arclib/browser/trunk/arclib/arc/templates/redblacktree.d |
