Page 215 - 《软件学报》2020年第11期

3530 Journal of Software 软件学报 Vol.31, No.11, November 2020

5. if y 0 ∈Line(L 0 ) then
6. L 0 .insert(y 0 );
7. end if
8. if L 0 ∈PLOP and (VT(y 0 )كmin(L 0 )∨max(L 0 )كVT(y 0 )) then
9. L 0 .insert(y 0 );
10. end if
11. if ׌Front(y 0 ) and ׌Back(y 0 ) then
12. new PLOB=<x 1 ,…,x i ,y 0 ,x j ,…,x m >;
13. put the <x i+1 ,…, x j–1 > as a new insert set; goto Step 1;
14. end if
15. if ׌Front(y 0 ) and !(׌Back(y 0 )) and R U (y 0 )∩L 0 =∅ then
16. new PLOB=<x 1 ,…,x i ,y 0 ,x i+1 ,…,x m >;
17. else if ׌Front(y 0 ) and !(׌Back(y 0 )) and R U (y 0 )∩L 0 ≠∅ then
18. new PLOB=<x 1 ,…,x i ,y 0 >;
19. put the <x i+1 ,…,x m >as a new insert set; goto Step 1;
20. end if
21. if !(׌Front(y 0 )) and ׌Back(y 0 ) then
22. new PLOB=<y 0 ,x j ,…,x m >;
23. put the<x 1 ,…,x j–1 > as a new insert set; goto Step 1;
24. end if
25. if !(Front(y 0 )) and !(׌Back(y 0 )) and R U (y 0 )∩L 0 =∅ then
26. new PLOB={y 0 };
27. else new PLOB<y 0 ,x i+1 ,…,x m >;
28. put the <x 1 ,…,x i > as a new insert set; goto Step 1;
29. end if
例 4:由算法 3 可得,TPindex 在进行插入更新时,会引起 3 种不同情况的变化.在第 1 种情况中,即插入新节点,
而不引起现有线序分枝的变动,新插入的节点 y 0 独立为一个新的线序分枝,如图 5(a)所示.当插入节点 y 0 是[0,4]
时,满足 PLOPكSR Top (y 0 ),此时 y 0 作为一个新的线序分枝;当插入节点是 y 0 是[9,10]时,满足 PLOPكSL Down (y 0 ),同
样将 y 0 作为一个新的线序分枝.在第 2 种情况下,即插入新节点会引起某一个线序分枝的序列增加,如图 5(b)所
示,插入节点 y 0 是[1,10],[7,5],[4,1]时,可以在原有的线序分枝的首元节点和尾元节点执行插入操作并更新原有
的首元节点与尾元节点.在第 3 种情况中,插入的新节点会引起原有分枝的结构的变化或分裂,如图 5(c)、图 5(d)
所示,当插入节点 y 0 是[5,6]时,则将原分枝中[5,7]与[5,5]之间的连接打断,再由 y 0 分别连接[5,7]与[5,5];当插入的
节点 y 0 是[4,6]时,从图 5(d)中可以看到,此时原有的分枝会分裂(即[4,7]与[5,7]之间的连接断开),分裂后的[4,7]节
点根据算法 1 连接到[4,7]节点,成为其所有分枝的新尾元节点;原有分枝中被“截断”的[5,7]和[5,5]则由算法 1 再
重新连接到[5,9]节点之后,构成新的线序分枝.