2

假设我有一个不平衡的 BST。BST 存储在数组中，其中索引 0 处，索引kroot上节点的左右子节点分别位于索引2k和2k + 1上。例如一棵树：

      5                            4
     /                            / \
    3        --balancing-->      2   5
   /\                           / \
  2  4                         1   3
 /
1

将存储在数组中[5, 3, nil, 2, 4, nil, nil, 1, nil, ...]，我想对其进行平衡，以使结果搜索树的最大高度最小（=没有超过存储数据所需的级别）。
例如，它可能是一棵树，其中数组中的值之间没有间隙，并且所有 nil 值都被“推”到后面（注意：这个树定义实际上比我在上一段中的目标更具限制性）。例如上面[4, 2, 5, 1, 3, nil, ...]。
有没有这样的算法？如果没有，是否有类似的算法平衡树至少“好”。

附加信息：
- 算法需要就地，只允许 O(1) 额外内存-这个
问题 中提到了一个算法，但是它依赖于交换指针（数组需要 2^n 大）
- 有一个非常相似的问题，遗憾的是，接受的答案只是关于树木的一般性讨论。（我没有 AVL 平衡树的元数据，是吗？如果我错了，请证明我错了）
- 可接受的答案也可以是没有这样的算法，如果是这种情况，请提供一些参考资料/证明或逻辑假设

4

0 回答 0