Binary Search Tree
March 5, 2010
Binary search trees are a simple and commonly-used data structure. A binary search tree is a hierarchical data structure in which each node stores a key, a value, and pointers to two children. Each node has one parent, except the node at the root of the tree, which has no parents. At each node, the key is greater than or equal to the keys of all nodes in its left child and less than or equal to the keys of all nodes in its right child. Any node may be null; a null node has no key, no value, and no children. A sample binary search tree is shown at the right.
Traversing the tree is fairly simple. Start at the root, comparing the key at the current node to the key being sought. If the target key is less than the current key, repeat the search at the left child; likewise, if the target key is greater than the current key, repeat the search at the right child. If the target key and current key are the same, you’ve found the desired node; if you reach a null node, the target key is not present in the tree. The insert and delete operations maintain the in-order property at each node.
Your task is to write functions that manipulate binary search trees; you should include lookup, insert, delete, and enlist functions in your library. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] Praxis – Binary Search Tree By Remco Niemeijer In today’s Programming Praxis exercise we have to implement a Binary Search Tree. Let’s get started, […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/05/programming-praxis-binary-search-tree/ for a version with comments):
import Control.Monad import System.Random data BTree k v = Node k v (BTree k v) (BTree k v) | Empty find :: (k -> k -> Ordering) -> k -> BTree k v -> Maybe v find _ _ Empty = Nothing find cmp k (Node k' v' l r) = case cmp k k' of EQ -> Just v' LT -> find cmp k l GT -> find cmp k r insert :: (k -> k -> Ordering) -> k -> v -> BTree k v -> BTree k v insert _ k v Empty = Node k v Empty Empty insert cmp k v (Node k' v' l r) = case cmp k k' of EQ -> Node k v l r LT -> Node k' v' (insert cmp k v l) r GT -> Node k' v' l (insert cmp k v r) delete :: (k -> k -> Ordering) -> k -> BTree k v -> IO (BTree k v) delete _ _ Empty = return Empty delete cmp k t@(Node k' v' l r) = case cmp k k' of EQ -> fmap (flip deroot t . (== 0)) $ randomRIO (0,1 :: Int) LT -> fmap (flip (Node k' v') r) $ delete cmp k l GT -> fmap ( Node k' v' l) $ delete cmp k r deroot :: Bool -> BTree k v -> BTree k v deroot _ Empty = Empty deroot _ (Node _ _ l Empty) = l deroot _ (Node _ _ Empty r) = r deroot True (Node k v l (Node rk rv rl rr)) = Node rk rv (deroot False $ Node k v l rl) rr deroot _ (Node k v (Node lk lv ll lr) r) = Node lk lv ll (deroot True $ Node k v lr r) toList :: BTree k v -> [(k, v)] toList Empty = [] toList (Node k v l r) = toList l ++ (k, v) : toList rMy solution in Java is here http://codingjunkie.net/?p=268
I got rid of my Java solution and re-did it in Ruby http://codingjunkie.net/?p=295
My implementation in c
http://codepad.org/jnMTN32g
# – A presorted list of numbers to search through.
# – The item to search for in the list.
proc binSrch {lst x} {
set len [llength $lst]
if {$len == 0} {
return -1
} else {
set pivotIndex [expr {$len / 2}]
set pivotValue [lindex $lst $pivotIndex]
if {$pivotValue == $x} {
return $pivotIndex
} elseif {$pivotValue -1 ? $recursive + $pivotIndex + 1 : -1}]
} elseif {$pivotValue > $x} {
set recursive [binSrch [lrange $lst 0 $pivotIndex-1] $x]
return [expr {$recursive > -1 ? $recursive : -1}]
}
}
}
[…] binary search and merge sort are good examples. Slowly, you learn more complicated things like creating and modifying a binary search tree. However, after learning these things, you eventually get a job building applications and you […]
[…] binary search and merge sort are good examples. Slowly, you learn more complicated things like creating and modifying a binary search tree. However, after learning these things, you eventually get a job building applications and you […]
[…] ordenamiento por mezcla son buenos ejemplos. Lentamente, aprendes cosas más complicadas del tipo crear y editar un árbol de búsquedas dictómicas. Sin embargo, tras aprender estas cosas, al final consigues un puesto de trabajo desarrollando […]