Treaps

June 26, 2009

Dictionaries are a common data type, which we have used in several exercises (Mark V. Shaney, Word Frequencies, Dodgson’s Doublets, Anagrams). Hash tables are often used as the underlying implementation for dictionaries, and in a previous exercise we developed ternary search tries as another implementation for dictionaries, which are useful when the keys are strings. Today’s exercise examines treaps, which are yet another method for implementing dictionaries.

A treap is essentially a binary search tree, represented as either an empty node, called nil, or a node with a key and a value and pointers to two child nodes, the left child and the right child. Binary search trees obey the rule that all nodes in the left child have keys that are less than the key of the current node, and all nodes in the right child have keys that are greater than the key of the current node. One node is distinguished as the root of the tree; it is the only node visible outside the tree. Obviously, a single set of keys could be represented by many different binary search trees, depending on which key is chosen as the root and the choices made at each level under the root.

The speed of a search depends on the depth at which the key is located in the tree. Trees that have more balance (fewer nodes with nil children) are faster to search than trees that have less balance (more nodes with nil children) because the overall depth of the tree is less. The two extreme cases occur when a tree is perfectly balanced (no internal nil nodes), when a search takes time logarithmic in the size of the tree, and when a tree is perfectly imbalanced (a long chain of nodes each with one nil child), when a search takes time linear in the size of the tree.

Treaps use an ingenious method to assure that the tree is approximately balanced at all times. Each node, in addition to the key, value, and two child nodes, contains a numeric priority, which is randomly assigned at the time the node is created and never changed. Of the many possible trees that could represent a particular set of keys, the one that is chosen obeys the heap-order property, with the priority of each node being greater than the priorities of all of its child nodes. Assuming all keys and priorities are distinct, there will be exactly one tree that satisfies both the tree-order and heap-order properties; it is the same tree that would be created if keys were dynmically inserted into a normal binary search tree in order of the priority field. The genius of this method is that the priorities are independent of the keys, making it extremely unlikely that highly-imbalanced trees could be created, thus keeping search times approximately logarithmic.

As nodes are dynamically inserted into and deleted from the tree, it is sometimes necessary to restructure the tree to maintain both the tree-order and the heap-order properties. The restructurings, known as rotations, come in two varieties, left and right:

[ This image, by Ramasamy, is used under the terms of the GNU Free Documentation License or the Creative Commons Attribution Share-Alike License. ]

In both trees shown above, all the nodes in sub-tree A have keys less than p, all the nodes in sub-tree B have keys between p and q, and all the nodes in sub-tree C have keys greater than q. Transforming the tree so that the root moves from p to q is called a left rotation, and transforming the tree so that the root moves from q to p is called a right rotation; in both cases the root node moves down the tree toward the leaves. Note that both rotations preserve the tree-order property. It is the goal of the insert and delete algorithms to use rotations to maintain the heap-order property.

Your task is to implement the lookup, insert, update, delete and enlist operations on treaps. When you are finished, you are welcome to read or run a suggested solution, or post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

5 Responses to “Treaps”

  1. [...] Praxis – Treaps By Remco Niemeijer Today’s Programming Praxis problem is about Treaps – binary trees that are more or less balanced thanks [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/06/26/programming-praxis-treaps/ for a version with comments):

    import Control.Monad
    import Data.Char
    import qualified Data.List.Key as K
    import System.Random
    
    data Treap k a = Nil | Node Int k a (Treap k a) (Treap k a)
    
    priority :: Treap k a -> Int
    priority Nil = -1
    priority (Node p _ _ _ _) = p
    
    rotLeft :: Treap k a -> Treap k a
    rotLeft (Node p k a l (Node rp rk ra rl rr)) =
        Node rp rk ra (Node p k a l rl) rr
    rotLeft t = t
    
    rotRight :: Treap k a -> Treap k a
    rotRight (Node p k a (Node lp lk la ll lr) r) =
        Node lp lk la ll (Node p k a lr r)
    rotRight t = t
    
    rot :: Treap k a -> Treap k a
    rot Nil = Nil
    rot t@(Node p _ _ l r) | p < priority l = rotRight t
                           | p < priority r = rotLeft t
                           | otherwise      = t
    
    find :: Ord k => k -> Treap k a -> Maybe a
    find _  Nil = Nothing
    find k' (Node _ k a l r) | k' < k    = find k' l
                             | k' > k    = find k' r
                             | otherwise = Just a
    
    update :: Ord k => (a -> a -> a) -> k -> a -> Treap k a -> IO (Treap k a)
    update _ k' a' Nil = fmap (\r -> Node r k' a' Nil Nil) $
                         randomRIO (0, maxBound)
    update f k' a' (Node p k a l r)
        | k' < k    = fmap (\n -> rot $ Node p k a n r) (update f k' a' l)
        | k' > k    = fmap (rot . Node p k a l) (update f k' a' r)
        | otherwise = return $ Node p k' (f a' a) l r
    
    insert :: Ord k => k -> a -> Treap k a -> IO (Treap k a)
    insert = update const
    
    deroot :: Treap k a -> Treap k a
    deroot Nil = Nil
    deroot t@(Node _ _ _ l r)
        | priority l < priority r = d deroot id $ rotLeft t
        | otherwise               = d id deroot $ rotRight t
        where d fl fr = (\(Node p k a l' r') -> Node p k a (fl l') (fr r'))
    
    delete :: Ord k => k -> Treap k a -> Treap k a
    delete _ Nil = Nil
    delete k' t@(Node p k a l r)
        | k' < k    = Node p k a (delete k' l) r
        | k' > k    = Node p k a l (delete k' r)
        | otherwise = deroot t
    
    toList :: Treap k a -> [(k, a)]
    toList Nil = []
    toList (Node _ k a l r) = toList l ++ [(k, a)] ++ toList r
    
    main :: IO ()
    main = mapM_ print =<< wordFreqs 25 =<< readFile "bible.txt"
    
    wordFreqs :: Int -> String -> IO [(String, Int)]
    wordFreqs n = fmap (take n . reverse . K.sort snd . toList) .
                  foldM (\a w -> update (+) w 1 a) Nil .
                  map (filter isAlpha) . words
    
  3. veer said

    Attempt in clojure , using pseudocode from http://sims.berkeley.edu/~aragon/pubs/rst96.pdf

    pastebin link http://clojure.pastebin.com/f20e92d3a

     
    (defstruct treaps :key :prio :value :left :right)
    
    (defn less? [a b] (neg? (compare a b)))
    (defn greater? [a b] (pos? (compare a b)))
    (defn eql? [a b] (zero? (compare a b)))
    
    (defn insert [k p v treap]
      (cond
        (nil? treap) (struct-map treaps :key k :prio p :value v)
        (less? k (:key treap))
        (let [tr (assoc treap :left (insert k p v (:left treap)))]
          (if (> (:prio (:left tr)) (:prio tr)) (rotate-right tr) tr))
        (greater? k (:key treap))
        (let [tr (assoc treap :right (insert k p v (:right treap)))]
          (if (> (:prio (:right tr)) (:prio tr)) (rotate-left tr) tr))
        :else  treap))
    
    
    (defn delete [k treap]
      (cond
        (nil? treap) nil
        (less? k (:key treap)) (assoc treap :left (delete k (:left treap)))
        (greater? k (:key treap)) (assoc treap :right (delete k (:right treap)))
        :else (root-delete treap)))
    
    (defn root-delete [treap]  
      (cond    
        (and (nil? (:left treap)) (nil? (:right treap))) nil
        (nil? (:left treap)) (:right  treap)
        (nil? (:right treap)) (:left  treap)
        :else (if (> (:prio (:left treap)) (:prio (:right treap))) 
    	    (let [tr (rotate-right treap)]
    	      (assoc tr :right (root-delete (:right tr))))
    	    (let [tr (rotate-left treap)]
    	      (assoc tr :left (root-delete (:left tr)))))))
    
    
    (defn look-up [k treap]
      (cond
        (nil? treap) nil
        (less? k (:key treap)) (look-up k (:left treap))
        (greater? k (:key treap)) (look-up k (:right treap))
        :else (:value treap)))
    
    
    (defn enlist [treap]
      (if (nil? treap) '()
          (concat (enlist (:left treap)) 
    	      (list (str (:key treap)) (:prio treap)) 
    	      (enlist (:right treap)))))
    
    
    (defn update [k v treap]
      (cond
        (nil? treap) nil
        (less? k (:key treap)) (assoc treap :left (update k v (:left treap)))
        (greater? k (:key treap)) (assoc treap :right (update k v (:right treap)))
        :else (assoc treap :value v)))
    
          			    
    (defn rotate-right [a-tree]
      (assoc (:left a-tree) :right (assoc a-tree :left (:right (:left a-tree)))))
       
    (defn rotate-left [a-tree]
      (assoc (:right a-tree) :left (assoc a-tree :right (:left (:right a-tree)))))
    
    
    (def lst '((80 \v) (60 \g) (63 \z) (37 \a) (57 \s) (47 \x)
    	   (31 \d) (53 \k) (39 \u) (22 \w) (36 \y)
    	   (15 \j) (48 \p) (21 \t) (17 \m) (34 \q) ))
    
    (def tree (reduce 
    	   (fn [a b] (insert (second b) (first b) (first b) a)) nil lst))
    
    (def tree2 (reduce 
    	   (fn [a b] (insert (second b) (rand) (first b) a)) nil lst))
    
    (= (delete \l (insert \l 69 69 tree)) tree)
    (= (delete \l (insert \l (rand) "L" tree2)) tree2)
    
    
  4. Scott Pedersen said

    Finally finished. It took me a while to get everything working since I went all out and implemented the full IDictionary interface. It was fun to get all of the code to work properly, but there’s clearly some optimization work needed to make the thing useful. My implementation’s performance compares unfavorably to the .Net framework’s built in System.Collections.Generic.Dictionary in all of my tests.

    http://inscrutable.pastebin.com/f3fabfc9a

  5. Vikas Tandi said

    My implementation in C

    #include <stdlib.h>
    #include <time.h>
    
    typedef struct treapNode
    {
    	int					key;
    	int					priority;
    	struct	treapNode*	left;
    	struct	treapNode*	right;
    }treap;
    
    static treap* sentinel;
    
    static treap* create_node(int key);
    static treap* right_rotation(treap *p);
    static treap* left_rotation(treap *p);
    
    treap* treap_init()
    {
    	sentinel = (treap*)malloc(sizeof(*sentinel));
    	if(sentinel == NULL)
    		return NULL;
    
    	sentinel->key = 0;
    	sentinel->priority = INT_MIN;
    	sentinel->left = sentinel->right = NULL;
    	srand((unsigned int)time(NULL));
    	return sentinel;
    }
    
    treap* treap_search(treap *p, int key)
    {
    	if(p == sentinel)
    		return NULL;
    	else if(key == p->key)
    		return p;
    	else if(key < p->key)
    		return treap_search(p->left, key);
    	else
    		return treap_search(p->right, key);
    }
    
    treap* treap_insert(treap *p, int key)
    {
    	if(p == sentinel)
    	{
    		p = create_node(key);
    		if(p == NULL)
    			return NULL;
    	}
    	else if(key < p->key)
    	{
    		p->left = treap_insert(p->left, key);
    		if(p->priority < p->left->priority)
    			p = right_rotation(p);
    	}
    	else
    	{
    		p->right = treap_insert(p->right, key);
    		if(p->priority < p->right->priority)
    			p = left_rotation(p);
    	}
    	return p;
    }
    
    treap* treap_remove(treap *p, int key)
    {
    	if(key < p->key)
    		p->left = treap_remove(p->left, key);
    	else if(key > p->key)
    		p->right = treap_remove(p->right, key);
    	else
    	{
    		if(p->left == sentinel && p->right == sentinel)
    		{
    			free(p);
    			return sentinel;
    		}
    
    		if(p->left->priority > p->right->priority)
    		{
    			p = right_rotation(p);
    			p->right = treap_remove(p->right, key);
    		}
    		else
    		{
    			p = left_rotation(p);
    			p->left = treap_remove(p->left, key);
    		}
    	}
    	return p;
    }
    
    static treap* create_node(int key)
    {
    	treap *p;
    
    	p = (treap*)malloc(sizeof(*p));
    	if(p == NULL)
    		return NULL;
    
    	p->priority = rand();
    	p->key = key;
    	p->left = p->right = sentinel;
    	return p;
    }
    
    static treap* right_rotation(treap *p)
    {
    	treap *s;
    
    	s = p->left;
    	p->left = s->right;
    	s->right = p;
    	return s;
    }
    
    static treap* left_rotation(treap *p)
    {
    	treap *s;
    
    	s = p->right;
    	p->right = s->left;
    	s->left = p;
    	return s;
    }
    

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

%d bloggers like this: