Binary search tree and binary search (Binary search tree)

3

As far as I understand, the binary search tree algorithm works at the end of the day, just like the binary search algorithm, with just a few changes, correct?

Being more direct: the binary search tree is the implementation of the binary search algorithm in a tree structure, right?

    
asked by anonymous 16.03.2018 / 22:00

2 answers

3

Almost this.

The concept of binary search is the idea of dividing search space successively into halves until you only have the element you were looking for or conclude that it is not in the set of searched elements. To make it right, it is assumed that this search space has the elements properly ordered so that by breaking it in the middle, you know in which remaining half continue the search.

However, the concept of binary search does not talk about the implementation itself. It could be files, arrays, lists, playing cards in a person's hand or even a sequence of stones sorted by size on a table.

The binary search tree is a particular implementation in particular. The binary tree is a very versatile and efficient data structure (as long as they are at least reasonably balanced trees) to store data that later allows them to be searched through binary search.

However, it is not that the binary tree is a modification of the binary search algorithm. In fact it is a strategy to be used to attack a problem. If your problem depends on fetching data quickly and these can be sorted by some criterion, one way to achieve this is by organizing them into a binary tree so that you can do the binary search.

    
16.03.2018 / 22:14
2

It does not work with some changes. You can apply the binary search algorithm to any data structure that is ordered .

But each data structure will have its own implementation to navigate the structure, so the binary search algorithm in one vector has one implementation, the tree has another.

    
16.03.2018 / 22:10