algorithm - 最坏情况二叉树 - 确定 "Sorted-ness"

Question

在最坏的情况下，从已知列表创建二叉树的时间复杂度为 O(n²)，但平均情况为 O(n logn)。最坏情况和平均情况之间的差异取决于树在创建后的不平衡程度。如果 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;
}

*“正确”- 该算法并非基于任何可靠的证据或概念。它基于模糊数据以查看 3 组是否按半排序顺序排序。选择 3 是因为它比 1 和 2 都大。

问题

有没有办法在 O(n) 时间内根据给定列表确定 future 二叉树的最大深度(或近似值)？

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

免责声明

我知道自平衡二叉树(红黑、AVL)，但就这个问题而言，它们并不有趣。它们与上述任何一个问题都不相关，而是解决这两个问题起源的背景信息。

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 的答案(包括空节点)。这是树(* 表示 null):

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