Menu
What is the use of data structure Binary Search Tree, if vector (in sorted order) can support insert,delete and search in log(n) time (using binary search)??
785
asked Dec 16 '15 07:12
A binary tree has a special condition that each node can have a maximum of two children. A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operations are as fast as in a linked list.
If you are doing frequent additions and deletions then a binary search tree (AVL or Red-Black) is faster than a sorted array. Like all linked lists, it is easier to grow a tree than to grow an array (which usually means creating a new array).
Advantages of Binary search tree Searching an element in the Binary search tree is easy as we always have a hint that which subtree has the desired element. As compared to array and linked lists, insertion and deletion operations are faster in BST.
The basic advantage of a tree is that insert and delete in a vector are not O(log(n)) - they are O(n). (They take log(n) comparisons, but n moves.)
The advantage of a vector is that the constant factor can be hugely in their favour (because they tend to be much more cache friendly, and cache misses can cost you a factor of 100 in performance).
Sorted vectors win when
Trees win when
... and don't forget hashed containers which are O(1) search, and unordered vectors+linear search (which are O(n) for everything, but if small enough are actually fastest).
61
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
