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.
Programming Praxis 
[…] Praxis – Treaps By Remco Niemeijer Today’s Programming Praxis problem is about Treaps – binary trees that are more or less balanced thanks […]
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) . wordsAttempt 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)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
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; }