(use eggdoc) (define doc `((eggdoc:begin (name "treap") (description "A sorted dictionary data structure based on randomized search trees.") (author (p "Oleg Kiselyov; packaged for Chicken Scheme by " (url "http://chicken.wiki.br/users/ivan-raikov" "Ivan Raikov"))) (history (version "1.5" "Ported to Chicken 4") (version "1.4" "Build script updated for better cross-platform compatibility") (version "1.3" "License upgrade to GPL v3") (version "1.2" "Added support for chicken-setup -test") (version "1.1" "Added definitions for the dec macros") (version "1.0" "Initial release")) (requires) (usage "(require-extension treap)") (download "treap.egg") (documentation (p "The treap library is an implementation of an ordered dictionary data structure, based on randomized search trees (treaps) by Seidel and Aragon: " (pre "R. Seidel and C. R. Aragon. Randomized Search Trees. Algorithmica, 16(4/5):464-497, 1996.")) (p "This code defines a treap object that implements an ordered dictionary mapping of keys to values. The object responds to a variety of query and update messages, including efficient methods for finding the minimum and maximum keys and their associated values as well as traversing of a treap in an ascending or descending order of keys. Looking up an arbitrary or the min/max keys, and deleting the min/max keys require no more key comparisons than the depth of the treap, which is O(log n) where n is the total number of keys in the treap. Arbitrary key deletion and insertions run in " (tt "O(log n)") (em " amortized") " time.") (p "This code is inspired by a Stefan Nilsson's article " (i "Treaps in Java") " (" (i "Dr.Dobb's Journal") ", July 1997, p.40-44) and by the Java implementation of treaps described in the article. Yet this Scheme code has been developed completely from scratch, using the description of the algorithm given in the article, and insight gained from examining the Java source code. As a matter of fact, treap insertion and deletion algorithms implemented in this code differ from the ones described in the article and implemented in the Java code; this Scheme implementation uses fewer assignments and comparisons (see below for details). Some insight as to a generic tree interface gleaned from " (tt "wttree.scm") " (Weight balanced trees) by Stephen Adams.") (p "A treap is a regular binary search tree, with one extension. The extension is that every node in a tree, beside a key, a value, and references to its left and right children, has an additional constant field, a priority. The value of this field is set (to a random integer number) when the node is constructed, and is not changed afterwards. At any given moment, the priority of every non-leaf node never exceeds the priorities of its children. When a new node is inserted, we check that this invariant holds; otherwise, we perform a right or left rotation that swaps a parent and its kid, keeping the ordering of keys intact; the changes may need to be propagated recursively up. The priority property, and the fact they are chosen at random, makes a treap look like a binary search tree built by a random sequence of insertions. As the article shows, this makes a treap a balanced tree: the expected length of an average search path is roughly " (tt "1.4log2(n)-1") ", and the expected length of the longest search path is about " (tt "4.3log2(n)") ". See Stefan Nilsson's article for more details.") (subsection "Treap procedures" (p "The treap object is created by a make-treap function, " "the only user-visible function defined in this egg: " (procedure "make-treap:: KEY-COMPARE-PROC -> SELECTOR" (p "where KEY-COMPARE-PROC is a user-supplied function " "that takes two keys and returns a negative, positive, or zero number " "depending on how the first key compares to the second. ") (p "The returned selector procedure can take one of the following arguments: " (symbol-table (describe "'get" ("returns a procedure " (tt "LAMBDA KEY . DEFAULT-CLAUSE") " which searches the treap for an association with a given " (tt "KEY") ", and returns a (key . value) pair of the found association. " "If an association with " (tt "KEY") " cannot be located in the treap, " "the PROC returns the result of evaluating the " (tt "DEFAULT-CLAUSE") ". " "If the default clause is omitted, an error is signalled. " (tt "KEY") " must be comparable to the keys in the treap " "by a key-compare predicate (which has been specified " "when the treap was created)")) (describe "'get-min" ("returns a (key . value) pair for an association in the " "treap with the smallest key. If the treap is empty, an error " "is signalled.")) (describe "'delete-min!" ("removes the min key and the corresponding association " "from the treap. Returns a (key . value) pair of the " "removed association. If the treap is empty, an error " "is signalled. ")) (describe "'get-max" ("returns a (key . value) pair for an association in the " "treap with the largest key. If the treap is empty, an error " "is signalled.")) (describe "'delete-max!" ("removes the max key and the corresponding association " "from the treap. Returns a (key . value) pair of the " "removed association. If the treap is empty, an error is signalled.")) (describe "'empty?" ("returns " (tt "#t") " if the treap is empty")) (describe "'size" ("returns the size (the number of associations) in the treap")) (describe "'depth" ("returns the depth of the tree. It requires " "the complete traversal of the tree, so use sparingly")) (describe "'clear!" ("removes all associations from the treap (thus making it empty)")) (describe "'put!" ("returns a procedure " (tt "LAMBDA KEY VALUE") " which, given a " (tt "KEY") " and a " (tt "VALUE") ", adds the corresponding association to the treap. " "If an association with the same " (tt "KEY") " already exists, its value is replaced with the " (tt "VALUE") " (and the old (key . value) association is returned). " "Otherwise, the return value is " (tt "#f") ".")) (describe "'delete!" ("returns a procedure " (tt "LAMBDA KEY . DEFAULT-CLAUSE") " which searches the treap for an association with a given " (tt "KEY") ", deletes it, and returns a (key . value) pair of the found " "and deleted association. If an association with the KEY cannot be located " "in the treap, the " (tt "PROC") " returns the result of evaluating " (tt "DEFAULT-CLAUSE") ". " "If the default clause is omitted, an error is signalled. ")) (describe "'for-each-ascending" ("returns a procedure " (tt "LAMBDA PROC") " that will apply the given procedure PROC to each (key . value) " "association of the treap, from the one with the smallest key " "all the way to the one with the max key, in an ascending order " "of keys. The treap must not be empty.")) (describe "'for-each-descending" ("returns a procedure " (tt "LAMBDA PROC") " that will apply the given " "procedure " (tt "PROC") "to each (key . value) association of the treap, " "in the descending order of keys. The treap must not be empty.")) (describe "'debugprint" ("prints out all the nodes in the treap, for debug purposes"))))))) (subsection "Notes on the algorithm" (p "As the DDJ paper shows, insertion of a node into a treap is a simple recursive algorithm, Example 1 of the paper. This algorithm is implemented in the accompanying source [Java] code as " (pre " private Tree insert(Tree node, Tree tree) { if (tree == null) return node; int comp = node.key.compareTo(tree.key); if (comp < 0) { tree.left = insert(node, tree.left); if (tree.prio > tree.left.prio) tree = tree.rotateRight(); } else if (comp > 0) { tree.right = insert(node, tree.right); if (tree.prio > tree.right.prio) tree = tree.rotateLeft(); } else { keyFound = true; prevValue = tree.value; tree.value = node.value; } return tree; }")) (p "This algorithm, however, is not as efficient as it could be. Suppose we " "try to insert a node which turns out to already exist in the tree, " "at a depth D. The algorithm above would descend into this node in the " "winding phase of the algorithm, replace the node's value, and, in the " "unwinding phase of the recursion, would perform D assignments of the kind " (pre " tree.left = insert(node, tree.left);") "and D comparisons of nodes' priorities. None of these priority checks and " "assignments are actually necessary: as we haven't added any new node, " "the tree structure hasn't changed.") (p "Therefore, the present Scheme code implements a different insertion " "algorithm, which avoids doing unnecessary operations. The idea is simple: " "if we insert a new node into some particular branch of the treap and verify " "that this branch conforms to the treap priority invariant, we are certain " "the invariant holds throughout the entire treap, and no further checks " "(up the tree to the root) are necessary. In more detail: " (ol (li "Starting from the root, we recursively descend until we find " "a node with a given key, or a place a new node can be inserted.") (li "We insert the node and check to see if its priority is less than " "that of its parent. If this is the case, we left- or right-rotate " "the tree to make the old parent a child of the new node, and the " "new node a new root of this particular branch. We return this new " "parent as an indication that further checks up the tree are " "necessary. If the new node conforms to the parent's priority, we " "insert it and return " (tt "#f")) (li "On the way up, we check the priorities again and rotate the tree " "to restore the priority invariant at the current level if needed.") (li "If no changes are made at the current level, we return a flag " (tt "#f") "meaning that no further changes or checks are necessary at the higher levels."))) (p "Thus, if a new node was originally inserted at a level D in the tree (level " "0 being the root) but then migrated up by L levels (because of its priority), " "the original insertion algorithm would perform (D-1) assignments, " "(D-1) priority checks, plus L rotations (at a cost of 2 assignments in the " "treap each). Our algorithm does only (L+1) node priority checks and " "max(2(L-1)+2,1) assignments. ") (p "Note if priorities are really (uniformly) random, L is uniformly distributed " "over [0,D], so the average cost of our algorithm is " (pre " D/2 +1 checks and D assignments") "compared to" (pre " D-1 checks and 2D-1 assignments") "for the original algorithm described in the DDJ paper.") (p "The similar gripe applies to the Java implementation of a node deletion " "algorithm: " (pre " private Tree delete(Ordered key, Tree t) { if (t == null) return null; int comp = key.compareTo(t.key); if (comp < 0) t.left = delete(key, t.left); else if (comp > 0) t.right = delete(key, t.right); else { keyFound = true; prevValue = t.value; t = t.deleteRoot(); } return t; }")) (p "The algorithm as implemented looks fully-recursive. Furthermore, " "deletion of a node at a level D in the treap involves at least D " "assignments, most of them being unnecessary. Indeed, if a node being " "deleted is a leaf, only one change to the tree is needed to detach " "the node. Deleting a node obviously requires a left- or a right-kid " "field of the node's parent be modified (cleared). This change, " "however does NOT need to be propagated up: deleting of a node does " "not violate neither ordering nor priority invariants of the treap; " "all changes are confined to a branch rooted at the parent of the " "deleted node.") (p "This Scheme code implements node deletion algorithm in the optimal " "way, performing only those assignments which are absolutely " "necessary, and replacing full recursions with tail recursions (which " "are simply iterations). Our implementation is also simpler and " "clearer, making use of a helper procedure join! to join two treap " "branches (while keeping both treap invariants intact). The deletion " "algorithm can then be expressed as replacing a node with a join of " "its two kids; compare this explanation to the one given in the DDJ " "paper!"))) (examples (pre #< Sorting of a set of numbers via a treap" (define (++ x) (fx+ 1 x)) (define (-- x) (fx- x 1)) (let ((min-key -1) (max-key 10) (treap (make-treap (lambda (x y) (- x y)))) ;; a hard-wired association between a key and a value (compute-assoc (lambda (key) (cons key (++ key))))) ;; loading a sequence [min-key .. max-key] in ascending order (do ((i min-key (++ i))) ((> i max-key)) ((treap 'put!) i (cdr (compute-assoc i)))) (treap 'debugprint) (print "treap's depth is " (treap 'depth) "\n") ; (assert (equal? ((treap 'get) (++ min-key)) ; (compute-assoc (++ min-key)))) (print ((treap 'get) (++ min-key))) ; (assert (equal? ((treap 'get) (++ min-key) #f) ; (compute-assoc (++ min-key)))) (print ((treap 'get) (++ min-key) 'notfound)) ;; checking traversing in the ascending order (let ((expected-key min-key)) ((treap 'for-each-ascending) (lambda (association) (print (equal? association (compute-assoc expected-key))) (set! expected-key (++ expected-key))))) ;(assert (= expected-key (++ max-key)))) ;; clearing the treap and reloading the same seq in descending order (treap 'clear!) (do ((i max-key (-- i))) ((< i min-key)) ((treap 'put!) i (cdr (compute-assoc i)))) (treap 'debugprint) (print "treap's depth is " (treap 'depth) "\n") ;(assert (equal? (treap 'get-max) ((treap 'get) max-key))) ;(assert (equal? (treap 'delete-max!) (compute-assoc max-key))) ;(assert (not ((treap 'get) max-key #f))) ;(assert (equal? (treap 'get-max) ((treap 'get) (-- max-key)))) ;(assert (= (treap 'size) (+ -2 (++ (- max-key min-key))))) ;; tchecking traversing in the descending order (let ((expected-key max-key)) ((treap 'for-each-descending) (lambda (association) (print (equal? association (compute-assoc expected-key))) (set! expected-key (-- expected-key)))))) ;(assert (= expected-key (-- min-key)))) EOF )) (license "Copyright Oleg Kiselyov. Chicken Scheme support copyright by Ivan Raikov. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the GPL license can be found at .")))) (if (eggdoc->html doc) (void))