排序列表以完成 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 的定义：

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.

from wikipedia

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

编辑：
上面的算法可以改成下面的方式直接构建数组：

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

通常这些 access-operations 是在基于 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 的任何子数组。在任何 method-calls.

中，各个节点的索引永远不会改变

Answer 2

表达二叉树搜索 (BST) 和直接排序数组之间没有直接表示。排序数组之间的唯一关系是当您运行在 BST 上按顺序遍历并将其存储在数组中时。

Answer 3

这是我想出的。它不是理想的，因为它不是我想要的功能，但它节省了构建树然后从中创建数组的工作。

find_idx(n) {
  if n == 1 { return 0; }

  h = ceil(lg(n+1)) // height of the tree
  f_h = floor(lg(n+1)) // height of the full portion (h or h-1)
  m_n = 2^h - 1 // # of nodes if tree were full
  f_n = 2^f_h -1 // # of nodes of full portion

  return floor(f_n / 2) + min(n - f_n, floor((m_n - f_n) / 2)
}

to_bst_array(array) {
   q = new empty queue
   res = resulting vector

   q.push(array)

   while !q.is_empty() {
     subarray = q.pop()
     idx = find_idx(subarray.len())

     res.push(subarray[idx])

     if subarray.len() > 1 {
       q.push(subarray[..idx]) // slice from 0 to idx
     }

     if subarray.len() > idx + 1 {
       q.push(subarray[idx + 1..]) // slice from idx+1 till end of subarray
     }
   }

   return res
}

Answer 4

这就是我解决这个任务的方法，希望你喜欢！）

def GenerateBBSTArray(a):
    a.sort()
    level = 0
    accum = []
    elements = []
    while len(a) // 2**level > 0:
        accum = [elem for elem in a[len(a) // 2**(level + 1)::(len(a) // 2**level) + 1]]
        elements.extend(accum)
        accum = []
        level += 1
    return elements

排序列表以完成 BST 数组表示

Sorted list to complete BST array representation

sorting

algorithm

binary-search-tree