CODEWITHSUNDEEP
algorithmsearchdata-structuresbinary-treecomplexity-theory
Nethre
Nethre

Reputation: 73

Cost search operation in a Binary tree?

How much does it cost the search operation in a Binary tree? Is it O(n)?

Upvotes: 1

Views: 3750

Answers (5)

Xiangpeng
Xiangpeng

Reputation: 44

According to the book "An Introduction to the Analysis of Algorithms" of Robert Sedgewick, if this binary tree is construct by random permutation of size N, then average successful search is 2H_N − 3 + 2H_N /N = 2ln(N)+O(1), and average of an unsuccessful search is 2H_{N+1} − 2 = 2ln(N)+O(1).

Upvotes: 0

Ammara Umer
Ammara Umer

Reputation: 1

yes It will be O(n) because you have no sorting condintion in this tree like binary search tree, so u have to traverse full tree, just like array

Upvotes: 0

Algorist
Algorist

Reputation: 492

Yes, it is O(n), since it is Binary Tree and NOT binary search tree.

Since it is not possible to judge to which way (Left or Right) to branch in a "Binary tree", we have to search the entire tree in the worst case.

Upvotes: 2

Yavar
Yavar

Reputation: 11933

Average Case for searching an element: O(log n)

Worst Case: O(n)

You can check out for balanced trees (AVL, Red Black) if you need better (logarithmic) worst case running complexities.

Upvotes: 1

Kirill Polishchuk
Kirill Polishchuk

Reputation: 56182

        Average     Worst case
Space   O(n)        O(n)
Search  O(log n)    O(n)
Insert  O(log n)    O(n)
Delete  O(log n)    O(n)

Upvotes: 3

Related Questions