## Treaps

### June 26, 2009

We represent a treap as a tree of nodes, each a five-slot vector with places for the key, priority, value, and the two child nodes; access functions are given below:

`(define (treap k p v l r) (vector k p v l r))`

(define (key t) (vector-ref t 0))

(define (prio t) (vector-ref t 1))

(define (val t) (vector-ref t 2))

(define (lkid t) (vector-ref t 3))

(define (rkid t) (vector-ref t 4))

(define nil (vector 'nil -1 'nil 'nil 'nil))

(define (nil! k) (vector-set! nil 0 k))

(define (nil? t) (eq? t nil))

(define (leaf? t) (and (nil? (lkid t)) (nil? (rkid t))))

(define (leaf-or-nil? t) (eq? (lkid t) (rkid t)))

Rotations are done by building new nodes using the appropriate pieces of the old nodes:

`(define (rot-left t)`

(let ((l (treap (key t) (prio t) (val t) (lkid t) (lkid (rkid t)))))

(treap (key (rkid t)) (prio (rkid t)) (val (rkid t)) l (rkid (rkid t)))))

`(define (rot-right t)`

(let ((r (treap (key t) (prio t) (val t) (rkid (lkid t)) (rkid t))))

(treap (key (lkid t)) (prio (lkid t)) (val (lkid t)) (lkid (lkid t)) r)))

`Lookup`

is exactly the same as a standard binary search tree; the priority field is unused. Starting at the root, `lookup`

compares the key being sought to the current key, branching either left or right depending on the outcome of the comparison. `Lookup`

terminates with failure if it reaches `nil`

, and terminates with success if the compare returns equal.

`(define (lookup lt? t k)`

(cond ((nil? t) #f)

((lt? k (key t)) (lookup lt? (lkid t) k))

((lt? (key t) k) (lookup lt? (rkid t) k))

(else (cons k (val t)))))

`Insert`

works in two phases; a winding phase descends the tree to find the insertion point, in a manner similar to `lookup`

, and an unwinding phase performs rotations to restore the heap-order property:

`(define (insert lt? t k v)`

(cond ((nil? t) (treap k (rand) v nil nil))

((lt? k (key t))

(let ((t (treap (key t) (prio t) (val t) (insert lt? (lkid t) k v) (rkid t))))

(if (< (prio t) (prio (lkid t))) (rot-right t) t)))

((lt? (key t) k)

(let ((t (treap (key t) (prio t) (val t) (lkid t) (insert lt? (rkid t) k v))))

(if (< (prio t) (prio (rkid t))) (rot-left t) t)))

(else (treap k (prio t) v (lkid t) (rkid t)))))

`Delete`

begins by setting the desired key in `nil`

as a sentinel, then searches, rebuilding nodes as it proceeds, until the key being deleted is found (the search will always succeed because of the sentinel). Then, `delete`

calls an auxiliary procedure, `deroot`

, which rotates the current node down until it becomes a leaf, where it is clipped off. `Deroot`

selects rotations based on priority:

`(define (deroot t)`

(cond ((leaf-or-nil? t) nil)

((< (prio (lkid t)) (prio (rkid t)))

(let ((t (rot-left t)))

(treap (key t) (prio t) (val t) (deroot (lkid t)) (rkid t))))

(else (let ((t (rot-right t)))

(treap (key t) (prio t) (val t) (lkid t) (deroot (rkid t)))))))

`(define (delete lt? t k)`

(nil! k)

(let delete ((t t))

(cond ((lt? k (key t))

(treap (key t) (prio t) (val t) (delete (lkid t)) (rkid t)))

((lt? (key t) k)

(treap (key t) (prio t) (val t) (lkid t) (delete (rkid t))))

(else (deroot t)))))

`Update`

is a simple variant on `insert`

:

`(define (update lt? t f k v)`

(cond ((nil? t) (treap k (rand) v nil nil))

((lt? k (key t))

(let ((t (treap (key t) (prio t) (val t) (update lt? (lkid t) k (rand) v) (rkid t))))

(if (< (prio t) (prio (lkid t))) (rot-right t) t)))

((lt? (key t) k)

(let ((t (treap (key t) (prio t) (val t) (lkid t) (update lt? (rkid t) k (rand) v))))

(if (< (prio t) (prio (rkid t))) (rot-left t) t)))

(else (treap k (prio t) (f k (val t)) (lkid t) (rkid t)))))

`Enlist`

traverses the tree in order, calling itself recursively at each node:

`(define (enlist t)`

(if (nil? t) '()

(append (enlist (lkid t)) (list (cons (key t) (val t))) (enlist (rkid t)))))

An example of the use of treaps is given by the earlier word-frequency exercise, which counted the most frequently-used words in the Bible. Here is a restatement of that exercise using treaps:

`(define (word-freq n file-name)`

(define (freq-gt? a b) (> (cdr a) (cdr b)))

(with-input-from-file file-name

(lambda ()

(let loop ((word (read-word)) (freqs nil))

(if (eof-object? word)

(take n (sort freq-gt? (enlist freqs)))

(loop (read-word) (update string<? freqs (lambda (k v) (+ v 1)) word 1)))))))

The result is the same as the prior exercise:

`> (word-freq 25 "bible.txt")`

(("the" . 62588) ("and" . 30875) ("of" . 30183)

("to" . 23023) ("you" . 14887) ("in" . 13357) ("he" . 10495)

("a" . 10150) ("i" . 9078) ("for" . 8983) ("his" . 8424)

("lord" . 8129) ("your" . 7398) ("with" . 7259)

("that" . 7187) ("is" . 7143) ("they" . 7005) ("not" . 6484)

("him" . 6140) ("will" . 6093) ("them" . 5831) ("be" . 5668)

("who" . 5611) ("from" . 5476) ("it" . 5395))

`Rand`

comes from the Standard Prelude. Treaps were invented by Cecilia Aragon and Raimund Seidel, and described in two papers. You can see the code from this exercise at http://programmingpraxis.codepad.org/iFm0jW0A.

[…] 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):

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

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

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