5.2.1　序列插入

假设线对象的原始顶点序列为(P 0,P 1,…,P n),新序列为(V 0,V 1,…,V m),若更新操作是将新序列插入到原始序列的顶点P i和P i+1之间,则此插入操作的更新域为(P i,P i+1)。序列插入操作的步骤如下:(1)首先将新序列(P i,V 0,V 1,…,V m,P i+1)构造为一棵子树;(2)然后找出P i和P i+1两点所对应的结点中距离根结点更远的点P i+1,将子树作为P i+1的左子树;(3)在将新生成的子树插入到新位置之前,该新子树从原序列的根节点开始的所有父节点,都需要重新计算{V 0,V 1,…,V m}中的顶点到每个树节点对应的简化线段的距离,如果这些距离大于原有的误差值,则每个树节点所关联的误差值应该更新为新值。整个更新过程中,将(P i,V 0,V 1,…,V m,P i+1)变为层次结构的计算复杂度为O(m log m),原序列的树节点的误差计算的复杂度为O(m log n),更新写入的复杂度为O(m+log n)。

由于顶点层次结构需要保持平衡,因此插入之后,树的平衡性会被改变。可以对原始层次结构设立层次结构重建阈值,当插入之后的新的树高度超过此阈值,则会引发层次结构的重建。图5-3为新序列的插入情况,其中P a、P b和P c表示插入过程中需要重新计算误差值的顶点,即顶点{V 0,V 1,…,V m}到每个顶点所对应的简化线段的距离;P i和P i+1表示新序列的首尾顶点的直接前驱和直接后继节点,即V 0在更新后的序列中的直接前驱P i,及V m的直接后继节点P i+1;新序列的波浪连接线表示两结点间省略了中间节点,三角形表示子树,虚线三角形表示新序列(V 0,V 1,…,V m)所形成的子树。

图5-3　顶点序列的插入(https://www.daowen.com)

表5-1为顶点层次结构的插入算法。序列插入算法的主要步骤是首先取出插入位置前后的两个顶点,将其作为待插入序列的首尾顶点,生成新的子树,然后将新的子树的根节点作为插入位置前后的两个顶点中离根节点更远的顶点的子结点插入到顶点层次结构中。在插入的过程中,计算新插入的子树中的节点到其从插入节点起所有祖先节点所对应基准线的距离,并以此更新祖先节点的误差值。若插入完成后,二叉树平衡度不满足预先设置的阈值,则根据规则进行子树重平衡操作。

表5-1　层次结构中序列插入更新算法