5.2.4　层次结构重平衡

在地理要素插入、删除及修改操作中,为了降低更新代价,仅在顶点层次结构的局部进行更新操作。但多次更新操作后,树的平衡性可能会被破坏,近似查询性能会受到影响。因此,需要对严重不平衡的子树进行重树平衡,以降低树的高度,使得二叉树的存储与查询操作更为高效,二叉树的重平衡操作如图5-6所示,实线灰色三角形表示平衡前的子树,虚线灰色三角形平衡后的子树。

图5-6　树重平衡操作(https://www.daowen.com)

表5-4为顶点层次结构的重平衡算法。根据预先设置的平衡度参数来计算更新后的二叉树的平衡度,若该平衡度不满足预先设置的阈值,则进行子树层次结构的重平衡。

表5-4　顶点层次结构重平衡算法