排序列表完成 BST 数组表示

Question

我想知道排序数组（例如，[1, 2, 3, 4, 5, 6]）与从该排序数组构造完整二叉搜索树时获得的表示之间是否存在映射，并且将所述二叉搜索树表示为数组（例如，[4, 2, 6, 1, 3, 5]，见下图）？

     4
  2     6
1   3  5

这里有更多背景信息：众所周知，可以采用一个排序数组并从中构造一个完整的二叉搜索树（有一种独特的表示形式）。递归算法是：找到合适的mid（这实际上是相当棘手的），将其视为根，然后在左子数组和右子数组上递归。从生成的 BST 中，可以执行层序遍历（基本上是广度优先搜索）来构造完整 BST 的数组表示。

我问这个问题的原因是这个映射与数组的内容无关：它只取决于它的长度。因此我觉得应该可以将两个数组简洁地表达为彼此的函数。

有什么想法吗？

Answer 1

树的高度是可以预测的roundUp(log2(nodes))。我们也知道，右子树永远不会大于左子树 - |LS| >= |RS|。此外，我们还可以计算为了使树完美而缺少的节点数：2 ^ (height - 1) - arr.length。这使我们能够预测如何在子树之间分配节点：

findRoot(int[] arr , int maxLeaves , int maxLevelL)
    //maxLeaves is the number of leaves on the maximum-level
    int l = min(maxLevelL / 2 , maxLeaves)
    return (arr.length - maxLeaves) / 2 + l

node buildTree(int[] arr , int maxLeaves , int maxLevelL)
    if maxLevelL == 0
        return null

    node result
    int rootidx = findRoot(arr , maxLeaves)

    result.val = arr[rootidx]

    result.left = buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL / 2)
    result.right = buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL / 2)

    return node

基本思想如下：所有完整的 BST 共享一个属性，关于 BST 的递归定义：(LS , R , RS) OR null，其中LS和RS是左子树和右子树，它们也被定义为 BST。和LS都是RS完整的，并且至少其中之一必须是完美的。我们可以轻松预测两者中哪一个是完美的：在最高级别的拟合m节点上，但在数组中我们缺少x构建完美树的节点。因此：

if m - x == m / 2 then both are complete and the height of RS is height(LS) - 1
if m - x < m / 2 RS is perfect, LS only complete but not perfect
if m - x > m / 2 LS is perfect, RS only complete but not perfect
if m - x == 0 both LS and RS are perfect and of equal height

我们可以使用以下规则找到树的根：计算将放置在最高层的左 ( l) 和右 ( )子树上的节点数。r现在我们可以轻松地从树中删除这些节点，计算完美 BST 的根，然后将左右节点隐式添加回树中：root = (arr.length - (l + r)) / 2 + l

E.g.:
Input:   1  2  3  4  5 
Nodes on maxLevel: 2
maxLevelL: 4

l = 2
r = 0

root_idx = (arr.length - (l + r)) / 2 + l =
     = (5 - 2) / 2 + 2 = 
     = 3

Apply this algorithm recursively to define subtrees:
...

result:
                  4
                /   \
               2     5
             /   \
            1     3

注意：我还没有测试过这段代码。可能它仍然包含一些需要修复的算术缺陷。不过，逻辑是正确的。这应该只是代表一种将索引从一个数组重新映射到另一个数组的方法。实际的实现可能看起来与我提供的代码有很大不同。

经过第二次讨论后，以下是完整 BST 的定义：

在完全二叉树中，除了最后一层之外，每一层都被完全填充，并且最后一层中的所有节点都尽可能远离左侧。

来自维基百科

完整 BST 是平衡 BST 的子类，具有一些附加约束，允许完整 BST 到排序数组的唯一映射，反之亦然。由于完整 BST 只是平衡 BST 的子类，因此不足以构建平衡 BST。

编辑：
可以通过以下方式更改上述算法以直接构建数组：

• 树的根索引为 0
• 有索引的节点的左子节点n有索引(n + 1) * 2 - 1
• 有索引的节点的右子节点n有索引(n + 1) * 2

通常这些访问操作是在基于 1 的数组上完成的，但为了方便起见，我将它们更改为匹配基于 0 的数组

因此我们可以重新实现buildTree直接生成一个数组：

node buildTree(int[] arr , int maxLeaves , int maxLevelL , 
          int[] result , int nodeidx)
    if maxLevelL == 0
        return

    int rootidx = findRoot(arr , maxLeaves)

    //insert value into correct position of result-array
    result[nodeidx] = arr[rootidx]

    //build left subtree
    buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL / 2 , 
              result , (nodeidx + 1) * 2 - 1)

    //build right subtree
    buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL / 2 ,
              result , (nodeidx + 1) * 2)

请注意，与 不同的是arr，我们从不使用 的任何子数组result。在任何方法调用过程中，各个节点的索引都不会改变。