Register

# doubt #DSA

• retagged by
667 views

1 Answer

1 1 vote
In BST, the time complexity of search operation (average case) is taken to be O(log n). But in the worst case, i.e the degenerate trees/skewed trees time complexity of search operation is O(n) which can also be attained using array or linked list. So, in order to remove this problem, balanced binary search tree (AVL tree) was introduced in which the time complexity of search operation remains O(log n).
Voting & Accepting an answer helps improve the community
← Previous · # DBMSNext → · DBMS-Normalisation-L...
← Previous in category · What is the worst ca...Next in category → · TIFR CSE 2017 | Part...
Position:
Show:

Related questions

0 0 votes
2 2 answers
910
910 views
vijju532 asked Jun 28, 2018
910 views
self doubt
how does AVL tree requires o(logn) for all the operation i.e search insert and deletewhile other tree (bst,binary) requires o(n) is it due to balancing factor that avl tr...
10 10 votes
1 1 answer
394
394 views
GO Classes asked Jul 28
394 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Tree
Rebalance the following tree so that it becomes a valid AVL tree:What will be the root after rebalancing?$10$ $12$ $16$ $20$
6 6 votes
1 1 answer
229
229 views
GO Classes asked Jul 27
229 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Tree
Insert the following keys into an initially empty AVL tree:$1, 2, 3, 4, 5, 6$What is the root of the final AVL tree?
6 6 votes
1 1 answer
338
338 views
GO Classes asked Jul 24
338 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Deletion & Rotation
Given the following AVL tree, delete node $\text{A}$.How many rotations are required to rebalance the AVL tree after deleting node $A$?(Count each rotation only once, whe...