CODEWITHSUNDEEP
treebinary-treeheightceilsegment-tree
khlrrr
khlrrr

Reputation: 1

Why the height of segment tree is O(logn)

I don't get why the height of a segment tree is O(logn). https://dzone.com/articles/binary-trees-part-1 Based on the article above, the maximum height of a full binary tree with n nodes is (n-1)/2 (->c.f: Case A: When the tree has a leaf node on left side and the right subtree continues to grow). Initially, since the segment tree is also full binary tree, I thought that the height of a segment tree should be O(n) because the height of the tree will not grow faster than the number of nodes does due to cases like Case A. But I realized that cases like Case A are not feasible, but rather segment tree is much more likely to look like balanced tree in real cases. <-Is this the reason why we say that the height of segment tree is O(logn)?

Also, I understand that height of the segment tree, denoted as h is the ceil of logn, but I don't get how this leads to the conclusion that h is O(logn).

Upvotes: 0

Views: 40

Answers (1)

trincot
trincot

Reputation: 349908

segment tree is much more likely to look like balanced tree in real cases

Yes, a segment tree is balanced. To construct it, you start with sorting all involved data points, as you need to get the elementary segments from that. Then you build a tree from it. As you are in complete control of the creation, and you have the sorted data points, the best shape is of course a balanced tree, and this is assumed. See also Wikipedia - segment tree

Upvotes: 0

Related Questions