Encyclopedia > Binary search tree

  Article Content

Binary search tree

A binary search tree is a binary tree where every node has a value, every node's left subtree has values less than the node's value, and every right subtree has values greater. A new node is added as a leaf. There is a sort algorithm based on binary search trees, and also a search algorithm.

If we write our binary tree nodes as triples (left subtree, node, right subtree), and the null pointer as None, we can build and search them as follows (in Python):

def binary_tree_insert(treenode, value):
    if treenode is None: return (None, value, None)
    left, nodevalue, right = treenode
    if nodevalue > value:
        return (binary_tree_insert(left, value), nodevalue, right)
    else:
        return (left, nodevalue, binary_tree_insert(right, value))

def build_binary_tree(values):
    tree = None
    for v in values:
        tree = binary_tree_insert(tree, v)
    return tree

def search_binary_tree(treenode, value):
    if treenode is None: return None  # failure
    left, nodevalue, right = treenode
    if nodevalue > value:
        return search_binary_tree(left, value)
    elif value > nodevalue:
        return search_binary_tree(right, value)
    else:
        return nodevalue

Note that the worst case of this build_binary_tree routine is O(n2) --- if you feed it a sorted list of values, it chains them into a linked list with no left subtrees. For example, build_binary_tree([1, 2, 3, 4, 5]) yields the tree (None, 1, (None, 2, (None, 3, (None, 4, (None, 5, None))))). There are a variety of schemes for overcoming this flaw with simple binary trees.

Once we have a binary tree in this form, a simple inorder traversal can give us the node values in sorted order:

def traverse_binary_tree(treenode):
    if treenode is None: return []
    else:
        left, value, right = treenode
        return (traverse_binary_tree(left) + [value] + traverse_binary_tree(right))

So the binary tree sort algorithm is just the following:

def treesort(array):
    array[:] = traverse_binary_tree(build_binary_tree(array))

Types of Binary Search Trees

There are many types of binary search trees. AVL trees and Red-Black trees are both forms of balanced binary search trees. A B-tree grows from the bottom up as elements are inserted. A splay tree is a self-adjusting binary search tree. In a treap ("tree heap"), each node also holds a priority and the parent node has higher priority than its children.

External Links



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
242

... century - 4th century Decades: 190s 200s 210s 220s 230s - 240s - 250s 260s 270s 280s 290s Years: 237 238 239 240 241 - 242 - 243 244 245 246 247 Events Patriarch ...

 
 
 
This page was created in 37.8 ms