Binary search tree (Binary search Tree) and binary search (Binary search)

Question

From what I understand, the binary search tree algorithm works at the end of the day, in the same way as the binary search algorithm, with only a few changes, correct?

More directly: the binary search tree is the implementation of the binary search algorithm in a tree structure, right?

Answer 1

Almost that.

The concept of binary search is the idea of dividing the 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 wanted elements. To work, it is assumed that this search space has the elements properly ordered so that when breaking it in the middle, you know in which remaining half to continue the search.

However, the concept of binary search says nothing about the implementation itself. It can 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. 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 allows later searching by binary search.

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

Answer 2

It’s not that it works with some changes. You can apply the binary search algorithm to any data structure that is orderly.

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