By No machine-readable author provided. Dcoetzee assumed (based on copyright claims). [Public domain], via Wikimedia Commons
What is the use case and benefit of a binary search? Binary searches allow you to efficiently search through memory. Suppose for example you store your memory in a sorted list? You will need a way to search through this sorted list to locate specific items. One benefit of binary search is that you have efficiency and as a measure you can run a binary search in O(log N).
Searching and sorting are extremely common tasks in any program. For example if you're simply counting cards then you might want to track in memory all the cards you have seen before and to have an algorithm do this would require a loop to pick up each card, a scan to memory to save each card to a list, and what if you only want to scan each card no more than once?
If you search an unordered list starting at the first item in the last to the last item in the list looking for a match then you typically get run time efficency of O(N). So does this prove? The better the algorithms you choose while while formulating your program the better performance you get. Binary search sorts by continuously dividing the data in half and this is key to understanding it conceptually while some other sorting algorithms go from top to bottom down a list which is less efficient than scanning from the middle.
Of course there is to it than that very brief explanation but what about implementing? Without going into code here is what typically goes into implementing any sort but in particular binary sort:
Example pseudocode:
low = 0
high = N - 1
while (low <= high) {
// invariants: value > A[i] for all i < low
value < A[i] for all i > high
mid = (low + high) / 2
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid
}
return not_found // value would be inserted at index "low"
}
Or in C++
template <class T>
int binSearch(const T arr[], int len, T what) {
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > what)
high = mid - 1;
else if (arr[mid] < what)
low = mid + 1;
else
return mid;
}
return -1; // indicate not found
}
For Binary Search Trees you have many options. A common option is the Red Black Tree with code example below:
class rbnode(object):
"""
A node in a red black tree. See Cormen, Leiserson, Rivest, Stein 2nd edition pg 273.
"""
def __init__(self, key):
"Construct."
self._key = key
self._red = False
self._left = None
self._right = None
self._p = None
key = property(fget=lambda self: self._key, doc="The node's key")
red = property(fget=lambda self: self._red, doc="Is the node red?")
left = property(fget=lambda self: self._left, doc="The node's left child")
right = property(fget=lambda self: self._right, doc="The node's right child")
p = property(fget=lambda self: self._p, doc="The node's parent")
def __str__(self):
"String representation."
return str(self.key)
def __repr__(self):
"String representation."
return str(self.key)
class rbtree(object):
"""
A red black tree. See Cormen, Leiserson, Rivest, Stein 2nd edition pg 273.
"""
def __init__(self, create_node=rbnode):
"Construct."
self._nil = create_node(key=None)
"Our nil node, used for all leaves."
self._root = self.nil
"The root of the tree."
self._create_node = create_node
"A callable that creates a node."
root = property(fget=lambda self: self._root, doc="The tree's root node")
nil = property(fget=lambda self: self._nil, doc="The tree's nil node")
def search(self, key, x=None):
"""
Search the subtree rooted at x (or the root if not given) iteratively for the key.
@return: self.nil if it cannot find it.
"""
if None == x:
x = self.root
while x != self.nil and key != x.key:
if key < x.key:
x = x.left
else:
x = x.right
return x
def minimum(self, x=None):
"""
@return: The minimum value in the subtree rooted at x.
"""
if None == x:
x = self.root
while x.left != self.nil:
x = x.left
return x
def maximum(self, x=None):
"""
@return: The maximum value in the subtree rooted at x.
"""
if None == x:
x = self.root
while x.right != self.nil:
x = x.right
return x
def insert_key(self, key):
"Insert the key into the tree."
self.insert_node(self._create_node(key=key))
def insert_node(self, z):
"Insert node z into the tree."
y = self.nil
x = self.root
while x != self.nil:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z._p = y
if y == self.nil:
self._root = z
elif z.key < y.key:
y._left = z
else:
y._right = z
z._left = self.nil
z._right = self.nil
z._red = True
self._insert_fixup(z)
def _insert_fixup(self, z):
"Restore red-black properties after insert."
while z.p.red:
if z.p == z.p.p.left:
y = z.p.p.right
if y.red:
z.p._red = False
y._red = False
z.p.p._red = True
z = z.p.p
else:
if z == z.p.right:
z = z.p
self._left_rotate(z)
z.p._red = False
z.p.p._red = True
self._right_rotate(z.p.p)
else:
y = z.p.p.left
if y.red:
z.p._red = False
y._red = False
z.p.p._red = True
z = z.p.p
else:
if z == z.p.left:
z = z.p
self._right_rotate(z)
z.p._red = False
z.p.p._red = True
self._left_rotate(z.p.p)
self.root._red = False
def _left_rotate(self, x):
"Left rotate x."
y = x.right
x._right = y.left
if y.left != self.nil:
y.left._p = x
y._p = x.p
if x.p == self.nil:
self._root = y
elif x == x.p.left:
x.p._left = y
else:
x.p._right = y
y._left = x
x._p = y
def _right_rotate(self, y):
"Left rotate y."
x = y.left
y._left = x.right
if x.right != self.nil:
x.right._p = y
x._p = y.p
if y.p == self.nil:
self._root = x
elif y == y.p.right:
y.p._right = x
else:
y.p._left = x
x._right = y
y._p = x
def check_invariants(self):
"@return: True iff satisfies all criteria to be red-black tree."
def is_red_black_node(node):
"@return: num_black"
# check has _left and _right or neither
if (node.left and not node.right) or (node.right and not node.left):
return 0, False
# check leaves are black
if not node.left and not node.right and node.red:
return 0, False
# if node is red, check children are black
if node.red and node.left and node.right:
if node.left.red or node.right.red:
return 0, False
# descend tree and check black counts are balanced
if node.left and node.right:
# check children's parents are correct
if self.nil != node.left and node != node.left.p:
return 0, False
if self.nil != node.right and node != node.right.p:
return 0, False
# check children are ok
left_counts, left_ok = is_red_black_node(node.left)
if not left_ok:
return 0, False
right_counts, right_ok = is_red_black_node(node.right)
if not right_ok:
return 0, False
# check children's counts are ok
if left_counts != right_counts:
return 0, False
return left_counts, True
else:
return 0, True
num_black, is_ok = is_red_black_node(self.root)
return is_ok and not self.root._red
def write_tree_as_dot(t, f, show_nil=False):
"Write the tree in the dot language format to f."
def node_id(node):
return 'N%d' % id(node)
def node_color(node):
if node.red:
return "red"
else:
return "black"
def visit_node(node):
"Visit a node."
print >> f, " %s [label=\"%s\", color=\"%s\"];" % (node_id(node), node, node_color(node))
if node.left:
if node.left != t.nil or show_nil:
visit_node(node.left)
print >> f, " %s -> %s ;" % (node_id(node), node_id(node.left))
if node.right:
if node.right != t.nil or show_nil:
visit_node(node.right)
print >> f, " %s -> %s ;" % (node_id(node), node_id(node.right))
print >> f, "// Created by rbtree.write_dot()"
print >> f, "digraph red_black_tree {"
visit_node(t.root)
print >> f, "}"
def test_tree(t, keys):
"Insert keys one by one checking invariants and membership as we go."
assert t.check_invariants()
for i, key in enumerate(keys):
for key2 in keys[:i]:
assert t.nil != t.search(key2)
for key2 in keys[i:]:
assert (t.nil == t.search(key2)) ^ (key2 in keys[:i])
t.insert_key(key)
assert t.check_invariants()
if '__main__' == __name__:
import os, sys, numpy.random as R
def write_tree(t, filename):
"Write the tree as an SVG file."
f = open('%s.dot' % filename, 'w')
write_tree_as_dot(t, f)
f.close()
os.system('dot %s.dot -Tsvg -o %s.svg' % (filename, filename))
# test the rbtree
R.seed(2)
size=50
keys = R.randint(-50, 50, size=size)
t = rbtree()
test_tree(t, keys)
write_tree(t, 'tree')
Or the AVL Tree in C++:
#include
#include
/* AVL node */
template <class T>
class AVLnode {
public:
T key;
int balance;
AVLnode *left, *right, *parent;
AVLnode(T k, AVLnode *p) : key(k), balance(0), parent(p),
left(NULL), right(NULL) {}
~AVLnode() {
delete left;
delete right;
}
};
/* AVL tree */
template <class T>
class AVLtree {
public:
AVLtree(void);
~AVLtree(void);
bool insert(T key);
void deleteKey(const T key);
void printBalance();
private:
AVLnode<T> *root;
AVLnode<T>* rotateLeft ( AVLnode<T> *a );
AVLnode<T>* rotateRight ( AVLnode<T> *a );
AVLnode<T>* rotateLeftThenRight ( AVLnode<T> *n );
AVLnode<T>* rotateRightThenLeft ( AVLnode<T> *n );
void rebalance ( AVLnode<T> *n );
int height ( AVLnode<T> *n );
void setBalance ( AVLnode<T> *n );
void printBalance ( AVLnode<T> *n );
void clearNode ( AVLnode<T> *n );
};
/* AVL class definition */
template <class T>
void AVLtree<T>::rebalance(AVLnode<T> *n) {
setBalance(n);
if (n->balance == -2) {
if (height(n->left->left) >= height(n->left->right))
n = rotateRight(n);
else
n = rotateLeftThenRight(n);
}
else if (n->balance == 2) {
if (height(n->right->right) >= height(n->right->left))
n = rotateLeft(n);
else
n = rotateRightThenLeft(n);
}
if (n->parent != NULL) {
rebalance(n->parent);
}
else {
root = n;
}
}
template <class T>
AVLnode<T>* AVLtree<T>::rotateLeft(AVLnode<T> *a) {
AVLnode<T> *b = a->right;
b->parent = a->parent;
a->right = b->left;
if (a->right != NULL)
a->right->parent = a;
b->left = a;
a->parent = b;
if (b->parent != NULL) {
if (b->parent->right == a) {
b->parent->right = b;
}
else {
b->parent->left = b;
}
}
setBalance(a);
setBalance(b);
return b;
}
template <class T>
AVLnode<T>* AVLtree<T>::rotateRight(AVLnode<T> *a) {
AVLnode<T> *b = a->left;
b->parent = a->parent;
a->left = b->right;
if (a->left != NULL)
a->left->parent = a;
b->right = a;
a->parent = b;
if (b->parent != NULL) {
if (b->parent->right == a) {
b->parent->right = b;
}
else {
b->parent->left = b;
}
}
setBalance(a);
setBalance(b);
return b;
}
template <class T>
AVLnode<T>* AVLtree<T>::rotateLeftThenRight(AVLnode<T> *n) {
n->left = rotateLeft(n->left);
return rotateRight(n);
}
template <class T>
AVLnode<T>* AVLtree<T>::rotateRightThenLeft(AVLnode<T> *n) {
n->right = rotateRight(n->right);
return rotateLeft(n);
}
template <class T>
int AVLtree<T>::height(AVLnode<T> *n) {
if (n == NULL)
return -1;
return 1 + std::max(height(n->left), height(n->right));
}
template <class T>
void AVLtree<T>::setBalance(AVLnode<T> *n) {
n->balance = height(n->right) - height(n->left);
}
template <class T>
void AVLtree<T>::printBalance(AVLnode<T> *n) {
if (n != NULL) {
printBalance(n->left);
std::cout << n->balance << " ";
printBalance(n->right);
}
}
template <class T>
AVLtree<T>::AVLtree(void) : root(NULL) {}
template <class T>
AVLtree<T>::~AVLtree(void) {
delete root;
}
template <class T>
bool AVLtree<T>::insert(T key) {
if (root == NULL) {
root = new AVLnode<T>(key, NULL);
}
else {
AVLnode<T>
*n = root,
*parent;
while (true) {
if (n->key == key)
return false;
parent = n;
bool goLeft = n->key > key;
n = goLeft ? n->left : n->right;
if (n == NULL) {
if (goLeft) {
parent->left = new AVLnode<T>(key, parent);
}
else {
parent->right = new AVLnode<T>(key, parent);
}
rebalance(parent);
break;
}
}
}
return true;
}
template <class T>
void AVLtree<T>::deleteKey(const T delKey) {
if (root == NULL)
return;
AVLnode<T>
*n = root,
*parent = root,
*delNode = NULL,
*child = root;
while (child != NULL) {
parent = n;
n = child;
child = delKey >= n->key ? n->right : n->left;
if (delKey == n->key)
delNode = n;
}
if (delNode != NULL) {
delNode->key = n->key;
child = n->left != NULL ? n->left : n->right;
if (root->key == delKey) {
root = child;
}
else {
if (parent->left == n) {
parent->left = child;
}
else {
parent->right = child;
}
rebalance(parent);
}
}
}
template <class T>
void AVLtree<T>::printBalance() {
printBalance(root);
std::cout << std::endl;
}
int main(void)
{
AVLtree<int> t;
std::cout << "Inserting integer values 1 to 10" << std::endl;
for (int i = 1; i <= 10; ++i)
t.insert(i);
std::cout << "Printing balance: ";
t.printBalance();
}
There may be more efficient ways of writing this code, but the code examples above show you how to implement a binary search tree.