5.2.2　序列删除

假设线对象的原始顶点序列为(P 0,P 1,…,P n),若将(P k,P k+1,…,P k+m)从原序列中删除,则此操作的更新域为以P j为根节点的子树,P j为被删除序列的首尾顶点即P k和P k+m在树中的最低公共祖先节点。设以P j为根结点的子树所对应的顶点序列为P s,P s+1,…,P k,P k+1,…,P k+m,…,P t,P j在树中的高度为l,则以其为根节点的子树所对应的顶点序列的长度为O(2h-l),其中h＝O(log n)即原序列树的高度。序列删除操作的步骤如下:将P j子树在删除掉顶点之后进行重建,即将序列P s,P s+1,…,P k-1,P k+m+1,…,P t生成一棵子树,然后将其挂接到P j顶点的位置。计算复杂度为O(2h-l(h-l))。图5-4为序列删除示意图,其中P k和P k+m为待删除序列的首尾顶点。三角形表示子树,虚线三角形表示删除的子树。

图5-4　顶点序列的删除(https://www.daowen.com)

表5-2为顶点层次结构的删除算法。序列删除算法的主要步骤是首先取出删除序列的首顶点和尾顶点,然后获得两个结点在顶点层次结构中的最低公共祖先,将最低公共祖先的子树取出形成一段顶点序列,在这些顶点序列中删去待删除的序列中的顶点,然后在新序列上构建子树,再将子树挂接到最低公共祖先的父节点上。

表5-2　层次结构中序列删除算法