左右值树常规操作的逻辑

2011年07月04日星期一 17:07

一、计算A节点的子节点数。

$num = ($AR - $AL -1)/2;

二、查找A节点的所有子节点。

select * from tree where L > $AL and R < $AR order by L asc;

三、查找A节点的所有父节点。

select * from tree where L < $AL and R > $AR order by L desc;

四、增加节点。需要为要增加的节点腾出左右值的空间。然后将新节点插入数据库。在哪里增加？这就需要参照物，有下面四种情况。

1. 在A节点下增加子节点B，B作为第一个子节点。

update tree set L = L + 2 where L > $AL;

update tree set R = R + 2 where R > $AL;

insert into tree (name, L, R) values('B', $AL+1, $AL+2);

2. 在A节点下增加子节点B，B作为最后一个子节点。

update tree set L = L + 2 where L >= $AR;

update tree set R = R + 2 where R >= $AR;

insert into tree (name, L, R) values('B', $AR-1, $AR);

3. 在A节点后面增加节点B, B作为A的兄弟节点。

update tree set L = L + 2 where L > $AR;

update tree set R = R + 2 where R > $AR;

insert into tree (name, L, R) values('B', $AR+1, $AR+2);

4. 在A节点前面增加节点B, B作为A的兄弟节点。

update tree set L = L + 2 where L >= $AL;

update tree set R = R + 2 where R >= $AL;

insert into tree (name, L, R) values('B', $AL, $AR);

五、删除A节点。先要计出该节点及其所有子节点所占的左右值空间，将这些节点删掉，然后更新其它节点的左右值。

$num = $AR - $AL + 1;

delete from tree where L >= $AL and R <= $AR;

update tree set R = R - $num where R > $AR;

update tree set L = L - $num where L > $AR;

六、移动节点。移动节点单纯用左右值去解决太过复杂，建议表结构中使用父节点的字段，移动的时候，更改父节点的值后，再重构整个tree的左右值。