When is binary tree better than ordered list?

Question

I understand differences between them, but I can't find any situation when binary tree is better. Searching, inserting and so cost more or less the same. Or am I wrong?

Answer 1

Searching takes O(n) in an ordered (linked-)list (as you need to iterate through the entire linked-list to find the correct element), while it takes O(log n) in a (self-balancing) binary (search) tree (BST) (because, at each node, you can either look left or right, effectively splitting the input in roughly half).

While insert and delete can theoretically be performed in O(1) in a linked-list, you need to search for the correct position to insert or find the element to delete first, so these operations will also take O(n), as opposed to a BST, where they take O(log n).

What's the difference between O(n) and O(log n)?

Well, we can just substitute a value or two for n and see what we get. For n = 1 000 000, log n = 19.93. From this it's not too difficult to see that log n is much less than n. So, except for very small data sets, O(log n) is greatly preferred above O(n).

Technical notes:

"list" might be ambiguous - it's mostly used to refer to a linked-list, but, in some cases, it's used to refer to an array. I assumed linked-list. For an array, the analysis is somewhat different, but we still get O(n) for insert and delete.

It needs to be a binary search tree, otherwise we're really comparing apples and oranges - a plain binary tree is an unordered data structure. The BST also needs to be self-balancing, otherwise you can get a very unbalanced tree (in the worst case, making it look like a linked-list), leading to O(n) operations.

I didn't mention update as it can just be implemented as a delete followed by an insert.

So, is an ordered linked-list ever useful?

It definitely is of limited use, but it does outperform a BST is some cases.

Consider if you mainly use the list as a queue or a stack (you mainly remove from or insert at the front or the back, which are O(1) operations, where-as these operations are O(log n) in a BST).

Answer 2

Balanced binary tree has Insert/Search/Update/Delete O(logN), ordered list has Insert/Serach/Upade/Delete O(N). The difference is matter of how big is your N compared to corresponding constants. So yes, you are wrong.