为什么线段树的高度是O(logn)

Question

我不明白为什么线段树的高度是O(logn)。 https://dzone.com/articles/binary-trees-part-1 根据上面的文章，有 n 个节点的满二叉树的最大高度为 (n-1)/2 (->c.f: 情况 A：当树的左侧有叶子节点且右子树继续生长时）。最初，由于线段树也是满二叉树，我认为线段树的高度应该是O(n)，因为像情况A这样的情况，树的高度不会比节点数增长得更快。但我意识到像案例 A 这样的情况是不可行的，而是线段树在实际情况下更有可能看起来像平衡树。 <-Is this the reason why we say that the height of segment tree is O(logn)?

另外，我理解线段树的高度，表示为 h 是 logn 的 ceil，但我不明白这如何得出 h 是 O(logn) 的结论。

Answer 1

在实际情况下，线段树更有可能看起来像平衡树

是的，线段树是平衡的。要构建它，您首先要对所有涉及的数据点进行排序，因为您需要从中获取基本段。然后你用它建造一棵树。由于您完全控制创建，并且您拥有排序的数据点，因此最好的形状当然是“平衡”树，这是假设的。另请参阅维基百科 - 线段树