3.1.2　基于B-DP算法的顶点层次结构

3.1.2　基于B-DP算法的顶点层次结构

在一些情况下,DP算法与VW算法等线简化算法在计算过程中依据一定的规则选点,构建得到的顶点二叉树可能会形成近似链,即部分子树深度远大于其他子树,使得操作的时间复杂度为线性O(n)。基于这种二叉树进行近似查询时需要遍历较深层次的树节点,增加了算法的时间复杂度。平衡二叉搜索树(Balanced Binary Tree)的高度可以良好的维持在O(log n),各操作的时间复杂度为O(log n),因此,可以认为如果构建平衡的二叉树能够有效降低时间复杂度。

因此,本节面向平衡二叉树在近似查询效率的优越性,提出平衡的DP算法(Balanced Douglas-Peukcer,B-DP)增加二叉搜索树的平衡性。B-DP算法以DP算法为基础,引入树平衡控制参数以保证树的平衡性,在选点过程中以子线段中的近似中间顶点作为线对象分割点,并将最大误差值作为近似中间顶点的误差值以保证能保留线的结构特性。B-DP算法能够在保持顶点层次结构的同时,有效地控制树的平衡性,降低算法的时间复杂度。

表3-1　基于B-DP算法的二叉树构建算法

(https://www.daowen.com)

可以看出,B-DP算法将选择距离最大的点更改为近似中间顶点。根据近似中间顶点的选择范围可知,B-DP算法生成的二叉树是一种平衡度可控的二叉树,可以通过调节中α取值,划定近似中间顶点的取点范围。除了在顶点选择策略与顶点距离值的取舍上有所不同之外,其他均与DP算法保持一致。

以图1-1(a)中线对象为例,α取0.2,基于B-DP算法生成的二叉树如图3-5所示,同图3-2、图3-4相比,该二叉树为平衡二叉树,对于顶点数量较多的线对象,效果会更明显。

图3-5　基于B-DP算法构建顶点二叉树