Binary Search Tree vs Sorted List

Question

Consider an unbalanced binary search tree and an ordered vector list. Which of the two structures is best suited to perform a search for any element.

Answer 1

The most effective algorithm for finding any element in both cases is the same: binary search. It has average complexity O(log n).

The problem is that in unbalanced binary trees, the worst-case scenario is O(n). For example, imagine that I am looking for 5 in the tree below:

1
 \
  2
   \
    3
     \
      4
       \
        5

The algorithm will go through all the elements of the tree find the 5. Already with ordered lists, the worst case remains O(log n). Having the same items as an example:

[1,2,3,4,5]

The algorithm will only go through 3, 4 and 5 until it finds the result. This way it is preferable to use an ordered list.

Answer 2

ABB tree. The tree complexity is O(log n) and the ordered list complexity is O(n), so the search in an ABB tree is more efficient than the search in the list.