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.

About these ads

Pages: 1 2

8 Responses to “Binary Search Tree”

  1. [...] 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, [...]

  2. Remco Niemeijer said

    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 r
    
  3. Bill B said

    I got rid of my Java solution and re-did it in Ruby http://codingjunkie.net/?p=295

  4. Vikas Tandi said

    My implementation in c
    http://codepad.org/jnMTN32g

  5. Robert said

    # – 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}]
    }
    }
    }

  6. [...] 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 [...]

  7. [...] 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 [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: