Menu
I want know what is the best : Array OR Binary search tree in ( insert , delete , find max and min ) and how can I Improve both of them ?
943
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. A tree is a group of nodes starting from the root node.
In a balanced tree, every leaf (a node at the end of a branch) is around the same distance away from the root as any other leaf. In this case, the binary search tree algorithm is as efficient as the binary search. In an unbalanced tree, one or more leaves is much further away from the root than another leaf.
Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search.
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
An array allows random access to each element in it. so you get insert, delete and look for a specific element in O(1), and max/min, delete in O(n). [you can also make max/min O(1) and delete O(n) instead]. If you are keeping your array sorted, it will cause insert/delete to be O(n), but you will gain O(logn) find, and O(1) min/max.
A BST is sorted by definition, and for a regular [unbalanced] BST, you get O(n) worst case behavior. For balanced BST, you get O(logn) insert/delete/find. You can get O(1) min/max any how for both.
Arrays are also usually faster to iterate [assuming order of iteration is not important] since you gain better cache performance. Also, unlike BST - which has unbounded size by nature, an array requires reallocation and copying the data when your array is full.
Improving a BST can be done by making it balanced - like AVL or red-black-trees.
Which is better? it depends on the application. Usually when you are planning to insert data and keep it sorted, BST will be prefered. If random access or iteration is the main purpose: you usually use an array.
75
Performance comparison of Arrays and Binary search trees:
Array Binary search tree
Unsorted Sorted Average Worst case
Space O(n) O(n) O(n) O(n)
Search O(n) O(log n) * O(log n) O(n)
Max/Min O(n) O(1) O(1) ** O(1) **
Insert O(1) O(n) O(log n) O(n)
Delete O(1) O(n) O(log n) O(n)
* assuming binary search
** requires extra pointers to min and max, otherwise it's O(log n)
42
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
