5.2.3　序列修改

图5-5为序列修改示意图,假设线对象的原始顶点序列为(P 0,P 1,…,P n),修改操作是将新序列(V 0,V 1,…,V m)替换掉原序列中的(P k,P k+1,…,P k+l),实线灰色三角形表示删除的子树,虚线灰色三角形新插入的子树。序列修改操作包括两步,首先删除原序列中的子序列(P k,P k+1,…,P k+l),然后在顶点P k-1与P k+l+1之间插入新序列(V 0,V 1,…,V m)。节点P j为被替换的序列的首尾顶点即P k和P k+l在树中的最低公共祖先节点,将P j的子树对应的序列P s,P s+1,…,P k,P k+1,…,P k+l,…,P t中的相关顶点替换为(V 0,V 1,…,V m),即生成新的序列P s,P s+1,…,P k-1,V 0,V 1,…,V m,P k+l+1,…,P t,将此序列生成新的子树,然后将此子树挂接到原树节点P j位置即可。

图5-5　序列的修改操作(https://www.daowen.com)

表5-3为顶点层次结构的修改算法。序列修改算法的主要步骤是首先取出被替换序列的首顶点和尾顶点,然后获得两个节点在顶点层次结构中的最低公共祖先,将最低公共祖先的子树取出形成一段顶点序列,在这些顶点序列中删去待删除的序列中的顶点(P k,P k+1,…,P k+l),替换上新加入的顶点(V 0,V 1,…,V m),然后在新序列上构建子树,再将子树挂接到最低公共祖先的父节点上。若删除完成后,二叉树层次结构平衡度不满足预先设置的阈值,则根据规则进行子树重平衡操作。

表5-3　层次结构中序列修改算法