Why are binary search trees?

Question

I read the binary search tree and thought, why do we need BST? All that I know can be achieved with simple sorted arrays. E.g. - To build a BST with n elements, we require n*O(log n)time, i.e. O(nlog n), and search time O(log n). But this thing can also be achieved using an array. We can have a sorted array (it takes O(nlog n)time), and the search time in this case is also O(log n)i.binary algo. Then why do we need a different data structure? Are there any other uses / uses of BST that make them so special?

- Ravi

Answer 1

Arrays are great if you talk about a record once, read many types of interactions. This is when you start inserting, replacing, and deleting, in which the BST really begins to shine compared to the array. Since they are based on a node and not on the basis of a continuous piece of memory, the cost of moving an item to or from a collection is fast, while preserving the sorted nature of the collection.

Think about it as you will have a difference in insertion between linked lists and arrays. This is a simplification, but it emphasizes the advantage that I mentioned above.

Answer 2

Imagine you have an array with a million elements.

You want to insert an item at location 5.

, , .

, ; O (nlog n), 1 000 000 * 6 = 6 000 000 .

, .

O (log n) = 6 + , 10 .

, 6 000 000 , . . ? - O (log n) - , !

, -another-element.

! ? n memcpy lot? memcpy 4mbytes?

...

Answer 3

?

Answer 4

In graphical programming, if you have an extended object (that is, that represents an interval in each dimension, not just a point), you can add them to the lowest level of the binary tree (usually an octet), where they fit completely.

And if you have not previously computed the tree / sorted list, then the random input time O (n) in the list can be excessively slow. The insertion time in the tree on the other hand is only O (log (n)).