是否存在动态构建叶子存储值的平衡BST的算法？

背景说明 #

• de Berg等人在2008年出版的《Computational Geometry》一书中，将范围搜索算法的底层数据结构描述为一种平衡BST：树的叶子节点存储点集P中的点，内部节点存储分割值以引导搜索路径。
• 维基百科范围树页面引用该观点，明确指出：

  n个点的一维范围树是一棵二叉搜索树
  每个非叶子节点存储其左子树的最大值

• 当前公开的在线示例多采用静态构建方式：先排序点集，再通过递归配对节点生成树。

核心问题解答 #

是否存在动态构建算法？ #

存在支持动态插入额外值的一维范围树构建算法。这类算法基于**平衡二叉搜索树（如AVL树、红黑树）**扩展而来，核心是在每个非叶子节点维护「左子树最大值」这一附加信息：

• 插入新节点时，按照平衡BST的标准插入流程调整树结构；
• 同步更新插入路径上所有祖先节点的左子树最大值，确保该附加信息始终准确。

算法出处 #

这类动态范围树的实现思路有明确的学术来源：

1. Bentley, J. L. 在1979年发表的论文 Multidimensional binary search trees used for associative searching 中，首次提出了动态范围树的框架，明确了在平衡BST基础上维护子树极值以支持动态插入和范围查询的核心方法。
2. de Berg等人在《Computational Geometry》（2008版）的相关章节中，也补充说明了动态范围树的实现方案，其逻辑与Bentley的原始思路一致，进一步验证了该方法的可行性。

内容的提问来源于stack exchange，提问作者aas