Binary Search Tree: In-Order Predecessor And Successor

February 12, 2013

We begin with some necessary infrastructure for handing binary search trees; our trees have only keys, not values, but you can add those yourself:

(define (tree key lkid rkid) (vector key lkid rkid))

(define (key tree) (vector-ref tree 0))
(define (lkid tree) (vector-ref tree 1))
(define (rkid tree) (vector-ref tree 2))

(define nil (vector 'nil 'nil 'nil))
(vector-set! nil 1 nil)
(vector-set! nil 2 nil)
(define (nil? tree) (eqv? tree nil))

(define (insert lt? t k)
  (cond ((nil? t) (tree k nil nil))
        ((lt? k (key t)) (tree (key t) (insert lt? (lkid t) k) (rkid t)))
        ((lt? (key t) k) (tree (key t) (lkid t) (insert lt? (rkid t) k)))
  (else t)))

Next we write two functions that are subroutines to the predecessor and successor functions as well as being useful in their own right. The minimum function finds the smallest key in the tree by chasing left sub-trees; the maximum function finds the largest key in the tree by chasing right sub-trees:

(define (minimum t)
  (cond ((nil? t) #f)
        ((nil? (lkid t)) (key t))
        (else (minimum (lkid t)))))

(define (maximum t)
  (cond ((nil? t) #f)
        ((nil? (rkid t)) (key t))
        (else (maximum (rkid t)))))

Now we are ready for the predecessor and successor functions. There are three returns and two recursive calls in each function. The first and fourth cond clauses return the saved tree when the recursion reaches a null node because the target key does not exist. The fifth clause returns the minimum/maximum when the search key is found. The other two clauses recur. Note that one of the clauses resets the saved tree as it recurs; the saved tree is the parent of the leftmost/rightmost non-matching node, and is the return value if the search key is found at a leaf of the tree:

(define (pred lt? t k)
  (define (return t) (if (nil? t) #f (key t)))
  (let loop ((t t) (prev nil))
    (cond ((nil? t) (return prev))
          ((lt? (key t) k) (loop (rkid t) t))
          ((lt? k (key t)) (loop (lkid t) prev))
          ((nil? (lkid t)) (return prev))
          (else (maximum (lkid t))))))

(define (succ lt? t k)
  (define (return t) (if (nil? t) #f (key t)))
  (let loop ((t t) (next nil))
    (cond ((nil? t) (return next))
          ((lt? k (key t)) (loop (lkid t) t))
          ((lt? (key t) k) (loop (rkid t) next))
          ((nil? (rkid t)) (return next))
          (else (minimum (rkid t))))))

You can see the complete code, along with a small set of examples, at http://programmingpraxis.codepad.org/PkWVHKLi.

About these ads

Pages: 1 2

3 Responses to “Binary Search Tree: In-Order Predecessor And Successor”

  1. jpverkamp said

    Here’s a version in Racket: Predecessor and successor in a binary search tree

    I went a slightly different direction than the solution here with a shared function to return the node containing the value we were searching for and the last left and right branch all at once (the ability to return multiple values is always nice). That made the actual predecessor and successor functions somewhat simpler:

    ; get the predecessor to a value
    (define (predecessor tr < val)
      (define-values (l v r) (find-nodes tr < val))
      (cond
        [(tree-left? v)
         (maximum (tree-left v))]
        [(and (not (void? r)) (not (empty? r)))
         (tree-value r)]))
    

    I also included code for using this to implement a sorting algorithm. Dump everything into a tree, find the minimum, then repeatedly call successor until you run out of elements. Am I incorrect in thinking that this is actually still O(n log n), albeit with a higher constant than most? It sorts a million element list only about 3x slower than a naive implementation of quicksort did, but insertion sort (known O(n^2)) didn’t even finish before I got bored.

  2. I finally got around to this challenge. Here’s the code for successor in python.

    class Node:
        def __init__(self, val=None, l=None, r=None):
            self.l = l
            self.r = r
            self.val = val
    
    def insert(node, val):
        if node == None:
            return
        elif node.val == val:
            return
        elif node.val > val:
            if node.l is None:
                node.l = Node(val)
            else:
                insert(node.l, val)
        else:
            if node.r is None:
                node.r = Node(val)
            else:
                insert(node.r, val)
    
    def suc(node, val, ancestor=Node(None)):
        '''
        >>> mynode = Node(5)
        >>> for v in "6 12 8 3 2 5 3 4 11 7 1".split():
        ...     insert(mynode,int(v))
        >>> suc(mynode,5)
        6
        >>> suc(mynode,8)
        11
        >>> suc(mynode,11)
        12
        >>> suc(mynode,12)
    
        >>> suc(mynode,2)
        3
        >>> suc(mynode,9)
        11
        >>> suc(mynode,15)
    
        '''
        if node is None:
            return ancestor.val
        if node.val == val:
            if node.r is None:
                return ancestor.val
            else:  # Find leftmost of right node
                node = node.r
                while node.l is not None:
                    node = node.l
                return node.val
        elif node.val > val:
            return suc(node.l, val, node)
        else:
            return suc(node.r, val, ancestor)
    
    

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 600 other followers

%d bloggers like this: