首页 文章

最坏情况二叉树 - 确定“排序”

提问于
浏览
3

在最坏的情况下,从已知列表创建二叉树将是O(n2),但是平均情况是O(n logn) . 最坏情况和平均情况之间的差异取决于树在创建后的不 balancer 程度 . 如果 maxDepth == n ,那么这是最糟糕的情况,如果 maxDepth == log(n) 那么这是最好的情况 . 在构建树之前了解 maxDepth 可以很好地了解创建树的运行时间 .

Max Depth

有没有办法在O(n)时间内确定最大深度(或近似值)?我想不出办法做到这一点 . 相反,我选择尝试找到初始列表的“已排序” .

Sorted-ness

在二叉树的最坏情况示例中,排序列表最终在功能上等同于链表 . 列表排序越多,二叉树的性能越差 . 我找不到任何可以给出列表的“排序因子”的东西 . 我试过的算法适用于我需要的东西,但感觉不对“*” .

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 .

Questions

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

“sorted-ness”是列表的可确定属性吗?可以在O(n)时间内确定还是需要更大的时间复杂度空间?

Disclaimer

我知道自 balancer 二叉树(Red-Black,AVL),但出于这个问题的目的,它们是无趣的 . 它们与上述任何一个问题无关,而是与这两个问题的起源背景信息有关 .

1 回答

  • 1

    它当然可以在时间O(n log n)内完成 . 我对线性决策树模型中的O(n)持怀疑态度,但我没有任何证据 .

    保留从现有键之间的间隔到新节点插入深度的有序映射 . 对于每个点的顺序,找到它的间隔并在深度加1分成两个 .

    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
                 / \
                *   *
    

相关问题