Difference between binary search and binary search tree?

Question

What is the difference between binary search and binary search tree?

Are they the same? Reading the internet it seems the second is only for trees (up to 2 children nodes) and binary search doesn't follow this rule. I didn't quite get it.

Answer 1

Binary Search Trees

A node in a binary tree is a data structure that has an element, and a reference to two other binary trees, typically called the left and right subtrees. I.e., a node presents an interface like this:

Node:   element  (an element of some type)   left     (a binary tree, or NULL)   right    (a binary tree, or NULL) 

A binary search tree is a binary tree (i.e., a node, typically called the root) with the property that the left and right subtrees are also binary search trees, and that all the elements of all the nodes in the left subtree are less than the root's element, and all the elements of all the nodes in the right subtree are greater than the root's element. E.g.,

     5     / \    /   \   2     8  / \   / \ 1   3 6   9 

Binary Search

Binary search is an algorithm for finding an element in binary search tree. (It's often expressed as a way of searching an ordered collection, and this is an equivalent description. I'll describe the equivalence afterward.) It's this:

search( element, tree ) {   if ( tree == NULL ) {     return NOT_FOUND   }   else if ( element == tree.element ) {     return FOUND_IT   }   else if ( element < tree.element ) {     return search( element, tree.left )   }   else {     return search( element, tree.right )   } } 

This is typically an efficient method of search because at each step, you can remove half the search space. Of course, if you have a poorly balanced binary search tree, it can be inefficient (it can degrade to linear search). For instance, it has poor performance in a tree like:

3  \   4    \     5      \       6 

Binary Search on Arrays

Binary search is often presented as a search method for sorted arrays. This does not contradict the description above. In fact, it highlights the fact that we don't actually care how a binary search tree is implemented; we just care that we can take an object and do three things with it: get a element, get a left sub-object, and get a right sub-object (subject, of course, to the constraints about the elements in the left being less than the element, and the elements in the right being greater, etc.).

We can do all three things with a sorted array. With a sorted array, the "element" is the middle element of the array, the left sub-object is the subarray to the left of it, and the right sub-object is the subarray to the right of it. E.g., the array

[1 3 4 5 7 8 11] 

corresponds to the tree:

     5     / \    /   \   3     8  / \   / \ 1  4  7   11 

Thus, we can write a binary search method for arrays like this:

search( element, array, begin, end ) {   if ( end <= begin ) {     return NOT_FOUND   }   else {      midpoint = begin+(end-begin)/2     a_element = array[midpoint]     if ( element == midpoint ) {       return FOUND_IT     }     else if ( element < midpoint ) {       return search( element, array, begin, midpoint )     }     else {       return search( element, array, midpoint, end )     }   } } 

Conclusion

As often presented, binary search refers to the array based algorithm presented here, and binary search tree refers to a tree based data structure with certain properties. However, the properties that binary search requires and the properties that binary search trees have make these two sides of the same coin. Being a binary search tree often implies a particular implementation, but really it's a matter of providing certain operations and satisfying certain constraints. Binary search is an algorithm that functions on data structures that have these operations and meet these constraints.