排序列表以完成BST数组表示 [英] Sorted list to complete BST array representation

问题描述

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

I'm wondering whether there is a mapping between a sorted array (e.g., [1, 2, 3, 4, 5, 6]) and the representation that one obtains when one constructs a complete binary search tree from this sorted array, and expresses said binary search tree as an array (e.g., [4, 2, 6, 1, 3, 5], see graphic below)?

     4
  2     6
1   3  5

这里有一些更多的上下文：众所周知，可以采用排序后的数组，并从中构造一个完整的二进制搜索树（有一个唯一的表示形式）。递归算法是：找到合适的中间值（这实际上很棘手），将其作为根，然后在左子数组和右子数组上进行
递归。从生成的BST中，可以执行级别顺序遍历（基本上是广度优先搜索）来构造完整BST的数组表示形式。

Here's some more context: It is well known that one can take a sorted array and construct a complete binary search tree from it (there is a unique representation). A recursive algorithm is: find the appropriate mid (this is actually quite tricky), treat it as the root, then recurse on left subarray and right subarray. From the resulting BST, one can perform a level-order traversal (basically breadth first search) to construct the array representation of the complete BST.

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

The reason I ask this is that this mapping is independent of the content of the array: it depends only on its length. Therefore I get the feeling that it should be possible to concisely express both arrays as a function of each other.

有什么想法吗？

推荐答案

树的高度是可预测的 roundUp（log2（nodes））。我们也知道，右子树比左子树从不大- | LS | > = | RS | 。更进一步，我们可以计算出使树完美的节点数： 2 ^（height-1）-arr.length 。这使我们能够预测如何在子树之间分配节点：

The height of the tree is predictable roundUp(log2(nodes)). We know as well, that the right subtree is never greater than the left subtree - |LS| >= |RS|. Further more we can calculate the number of nodes that are missing to make the tree perfect: 2 ^ (height - 1) - arr.length. This allows us to predict how to distribute nodes among subtrees:

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）或null ，其中 LS 和 RS 是左右子树，它们定义为BST还有。 LS 和 RS 都是完整的，至少其中之一必须是完美的。我们可以轻松地预测两者中的哪一个是完美的：在最高级别上适合 m 个节点，但是在数组中我们缺少 x 节点以构建完美的树。因此：

The basic idea is the following: all complete BSTs share one property, regarding the recursive definition of a BST: (LS , R , RS) OR null, where LS and RS are the left and right subtree, which are defined as BSTs aswell. Both LS and RS are complete and at least one of them must be perfect. We can easily predict which of the two is perfect: on the highest level fit m nodes, but in the array we are missing x nodes to build a perfect tree. Thus:

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

We can find the root of a tree using the following rule: Calculate the number of nodes on the left (l) and right (r) subtree that would be placed on the heighest level. Now we can easily remove those nodes from the tree, calculate the root of a perfect BST, and later on add the left and right nodes back into the tree implicitly: 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

注意：
我尚未测试此代码。可能是它仍然包含一些需要修复的算术不足。但是，逻辑是正确的。这仅代表一种将索引从一个数组重新映射到另一个数组的方法。实际的实现可能与我提供的代码有很大不同。

NOTE: I haven't tested this code. Might be that it still contains a few arithmetic insufficiencies that need to be fixed. The logic is correct, though. This should just represent a way of remapping the indices from one array to the other. The actual implementation might look quite a lot different from the code I provided.

第二次讨论之后，下面是完整BST的定义：

After having this discussion for the second time, here's a definition of a complete BST:

在一个完整的二叉树中，每个级别（可能除了最后一个级别）都被完全填充，并且最后一个级别中的所有节点都尽可能地远。

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

来自维基百科

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

Complete BSTs are a subclass of balanced BSTs, with a few additional constraints, that allow a unique mapping of a complete BST to a sorted array and vice versa. Since complete BSTs are only a subclass of balanced BSTs, it won't suffice to build a balanced BST.

编辑：

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

The above algorithm can be altered in the following way to directly build the array:

• 树的根索引为0


• 索引为 n 的节点的左子节点的索引为（n + 1）* 2-1


• 索引为 n 的节点的右子节点的索引为（n + 1）* 2

• the root of the tree has index 0
• the left child of the node with index n has index (n + 1) * 2 - 1
• the right child of the node with index n has index (n + 1) * 2

通常，这些访问操作在基于1的数组上完成，但是我为了方便起见，已对其进行了更改以匹配基于0的数组

Usually these access-operations are done on a 1-based array, but I've altered them to match a 0-based array for convenience

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

Thus we can reimplement buildTree to directly produce an array:

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 不同，我们从不使用以下子数组结果。在任何方法调用中，各个节点的索引都不会改变。

Note that unlike arr, we never use any subarrays of result. The indices of the respective nodes never change, throughout any method-calls.

这篇关于排序列表以完成BST数组表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！