大O（H）与大O（LOGN）在树上 [英] Big O(h) vs. Big O(logn) in trees

问题描述

我有时间复杂树操作的问题。
据说，在BSTS（数据结构，霍洛维茨等）时间的插入，删除，搜索，发现复杂分钟，MAXS，继任者和predecessor节点是邻（H）而AVLS使得 O（LOGN）。
我完全不明白有什么区别。随着 H = [LOGN] +1 记住，那么为什么我们说 0（H）和其他地方 O（LOGN）？

I have a question on time complex in trees operations.
It's said that (Data Structures, Horowitz et al) time complexity for insertion, deletion, search, finding mins-maxs, successor and predecessor nodes in BSTs is of O(h) while those of AVLs makes O(logn).
I don't exactly understand what the difference is. With h=[logn]+1 in mind, so why do we say O(h) and somewhere else O(logn)?

推荐答案

^ h 是树的高度。它始终是欧米茄（LOGN） [不是渐近小则 LOGN 。它可以是非常接近 LOGN 完全树（那么你真的得到 H = LOGN + 1 ，但在树衰减到一个链（每个节点都只有一个儿子），它是 O（N）。

h is the height of the tree. It is always Omega(logn) [not asymptotically smaller then logn]. It can be very close to logn in complete tree (then you really get h=logn+1, but in a tree that decayed to a chain (each node has only one son) it is O(n).

有关平衡树， H = O（LOGN）（事实​​上它是西塔（LOGN）） ，等等这些的任何 0（H）算法实际上是 O（LOGN）。

For balanced trees, h=O(logn) (and in fact it is Theta(logn)), so any O(h) algorithm on those is actually O(logn).

的自平衡搜索树（和AVL是其中之一）的想法是prevent其中树衰变到一个链（或某处接近）的情况下，和它的（在平衡树）设有可确保我们 O（LOGN）的高度。

The idea of self balancing search trees (and AVL is one of them) is to prevent the cases where the tree decays to a chain (or somewhere close to it), and its (the balanced tree) features ensures us O(logn) height.

编辑：
要理解这个问题，更好地考虑在未来两棵树（和原谅我的可怕的ASCII艺术家）：

To understand this issue better consider the next two trees (and forgive me for being terrible ascii artist):

          tree 1                                tree 2
            7
           /
          6
         /
        5                                         4
       /                                      /       \
      4                                      2         6
     /                                    /    \     /   \
    3                                    1      3   5     7
   /
  2
 /
1

两者都是有效的二叉搜索树，并在这两个搜索元素（比如 1 ）将 0（H）。但在第一， 0（H）其实就是 O（N），而在第二个是 O（LOGN）

Both are valid Binary search trees, and in both searching for an element (say 1) will be O(h). But in the first, O(h) is actually O(n), while in the second it is O(logn)

这篇关于大O（H）与大O（LOGN）在树上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！