最坏情况下的二叉树 - 确定“有序性”

Question

在最坏的情况下，从已知列表创建二叉树的复杂度将是O(n²)，但平均情况是O(n log n)。最坏情况和平均情况之间的差异取决于创建后树的平衡程度。如果maxDepth == n，则为最坏情况，如果maxDepth == log(n)，则为最佳情况。在构建树之前知道maxDepth会给予许多有关创建树的运行时间的洞察力。

最大深度

是否有一种方法可以在O(n)时间内确定最大深度（或近似值）？我想不出一种方法来做到这一点。相反，我选择尝试找到初始列表的“排序程度”。

排序程度

在二叉树的最坏情况示例中，排序列表最终将功能上等同于链接列表。列表排序程度越高，二叉树的性能越差。我找不到任何可以给出列表“排序因子”的东西。我尝试过的算法适用于我所需的内容，但感觉不太“对”。

public double sortFactor(int[] ar) {
    //assume lists are larger than 10000 elements
    int prevSum = ar[0] + ar[1] + ar[2];
    int numIncreasing = 0;
    for(int i=3; i < ar.length-3; i+=3) {
        int sum = ar[i] + ar[i+1] + ar[2];
        if (sum > prevSum) {
            numIncreasing++;
        }
        prevSum = sum;
    }
    int totalSets = ar.length/3;
    double sortFactor = (double) numIncreasing / (double) totalSets;
    return sortFactor;
}

*“right” - 这个算法并没有基于任何坚实的证据或概念。它是基于对数据进行模糊测试，以查看是否按半排序顺序排序为组的3。选择3是因为它比1和2都要大。

问题

有没有一种方法可以在O(n)时间内根据给定列表确定未来二叉树的最大深度（或近似值）？

“已排序性”是否是列表的可确定属性？它能否在O(n)时间内确定，还是需要更大的时间复杂度空间？

免责声明

我知道自平衡二叉树（红黑树，AVL），但是对于这个问题，它们不太有趣。它们与上述两个问题无关，而是解决了那两个问题的背景信息。

- Scott

---

列表的“有序性”可以近似为对其进行排序所需的交换次数，并且可以在O(nlogn)时间内计算。但是，除了已排序的列表外，还有其他列表会导致最坏情况高度。例如，考虑列表[10, 9, 8, 7, 6, 1, 2, 3, 4 ,5]。你需要一个更通用的熵度量。 - kfx

你是如何创建二叉树的？如果没有这个背景，你的问题就没有意义。 - comingstorm

@kfx：出于好奇，你能在不实际排序的情况下做到这一点吗？我可以看到它适用于初始分区，但之后呢？ - 500 - Internal Server Error

@kfx，巧合的是，我遇到了这些问题，因为我正在尝试确定需要多少次交换，并且创建二叉树是解决平均时间为O(n logn)，但最坏情况下为O(n^2)的问题的一种方法。我相信使用归并排序并保留一些计数器将能够以O(n logn)的最坏/平均/最佳方式完成它，但我一心想坚持使用二叉树来解决这个问题。 - Scott

吹毛求疵一下：“二叉树”并不意味着“二叉搜索树”。它只是指每个节点限制为两个子节点的树。有很多基于二叉树的数据结构不维护BST不变量。 - user2357112

Answer 1

“在时间复杂度为O(n log n)的情况下，这当然是可以完成的。对于线性决策树模型中的O(n)，我持怀疑态度，但我没有任何证据。”

“保留一个已存在键之间区间到新节点插入深度的有序映射。按顺序对每个点，找到其区间并在深度加一处分成两个部分。”

“以下是在3、1、4、5、9上执行的示例：”

(-inf, inf): 0

insert 3

(-inf, 3): 1
(3, inf): 1

insert 1

(-inf, 1): 2
(1, 3): 2
(3, inf): 1

insert 4

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, inf): 2

insert 5

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, 5): 3
(5, inf): 3

insert 9

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, 5): 3
(5, 9): 4
(9, inf): 4

对于深度为4（包括空节点）的答案。以下是树形结构（*代表空节点）：

      3
     / \
    /   \
   /     \
  1       4
 / \     / \
*   *   *   5
           / \
          *   9
             / \
            *   *

- David Eisenstat