5

For each of these operations would a balanced binary search tree complete the task in a faster big oh time than a balanced binary tree?

  1. Finding the smallest item in the tree.

I think balanced BST would have a faster big oh time than a balanced Binary Tree since you can just keep traversing left and find the smallest item. I think it would be O(log n).

  1. Creating a list of all elements in the tree that are smaller than some value v.

For 2 could someone offer me an explanation about which one would have a faster big oh time?

Improve this question
1
  • feel free for any queries. Commented Mar 30, 2017 at 14:43

2 Answers 2

Reset to default
8

You also have to take into account best, average and worst case scenarios in time complexity performance, keeping in mind what the value of n represents:

1. Balanced Binary Search Tree representation

           25             // Level 1
        20    36          // Level 2
      10 22  30 40        // Level 3
  .. .. .. .. .. .. .. 
.. .. .. .. .. .. .. ..   // Level n

2. Binary Search Tree representation

           10           // Level 1
          9  11         // Level 2
         8 . . 20       // Level 3
        7 . . 15 24   
       6 . . . . . . .  // Level n

Finding the smallest item in the tree.

This is a search operation.

1) The time complexity in here is O(log n), even in worst case scenario, because the tree is balanced. The minimum value is 10.

2) The time complexity here in the worst case scenario is O(n). The minimum value is 6. You can picture from the representation that the root's left tree (branch) behaves like a linked list. This is because the tree is unbalanced. [1]

Creating a list of all elements in the tree that are smaller than some value v.

This would be an insertion operation.

1) This would be O(log n), because as the tree is traversed it is balanced so you don't get 2)'s scenario.

2) This would be O(n), because in the worst case scenario your insertion will resemble insertion of a linked list.

In conclusion: A Balanced Binary Search Tree guarantees O(log n) in all cases of search, insertion and deletion of nodes, where as a typical BST does not.

Citations

Best, worst and average case [1]

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

The "Asymptotic analysis" is all about the worst case my friend.
by the way, how can you classify creating a list of all the elements less than v as insertion operation.
It's about all cases my friend and check your sources, because some of your analyses are wrong. Might want to edit them.
please specify the mistake
Picture a BST and insert in this order {10,9,8,7,6,5,4,3,2,1}...that is the worst case scenario for a BST insertion. It's O(n), same as a linked list.
|
1

Creating a list of all elements in the tree that are smaller than some value v.

Well, in Big O notation both balanced binary search tree and balanced binary tree would perform the same and time would be O(N), which is linear time complexity.

For the Balanced Binary Search tree, we would do an inorder traversal and keep adding all the keys to the list until we encounter the node with key v(inorder traversal of BST leads to ascending ordering of keys). Now worst case occurs when v is the largest key that is present in the BST, therefore, time complexity is O(N).

For a balanced binary tree, its as good as traversing the entire tree and adding all the keys to the list that are less than v. So time complexity here also is O(N).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.