From oleg@pobox.com Mon Sep 22 14:01:36 1997 Date: Mon, 22 Sep 1997 13:05:11 -0600 From: oleg@pobox.com Subject: Treaps in Scheme Newsgroups: comp.lang.scheme Message-Id: <874948065.32656@dejanews.com> Reply-To: oleg@pobox.com Keywords: dictionary, search tree, hash table, container, Scheme, Java, sorting, complexity Summary: announcing Scheme implementation of Treaps, ordered search trees X-Article-Creation-Date: Mon Sep 22 17:07:47 1997 GMT Content-Length: 3336 Status: RO [This is a courtesy copy of an article posted to Usenet via Deja News] This is to cry out loud about a Scheme implementation of Treaps, an ordered dictionary data structure, based on randomized search trees by Seidel and Aragon: R. Seidel and C. R. Aragon. Randomized Search Trees. Algorithmica, 16(4/5):464-497, 1996. Treap offers functionality of a general purpose sorting routine, priority queue, hash table, stack, or standard queue. 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 O(log n) _amortized_ time. The code is inspired by a Stefan Nilsson's article "Treaps in Java" (Dr.Dobb's Journal, July 1997, p.40-44) and by 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. Some differences stem from the fact that Scheme simply is a different language than Java, and I tried to take as much advantage of Scheme features as possible. For instance, treap traversal is implemented as an for-each-like iterat-OR in Scheme (while it was done through much messier enumeration in Java). Furthermore, there are some deeper differences: it appears that insertion and deletion algorithms described in the article (and implemented in the Java code) could be optimized. This Scheme code takes, on average, half as many assignments and priority comparisons to insert or delete associations from a treap. See the code's title comments for extensive discussion. The code is available from http://pobox.com/~oleg/ftp/Scheme/treap.scm http://pobox.com/~oleg/ftp/Scheme/vtreap.scm See http://pobox.com/~oleg/ftp/Scheme/myenv.scm for definitions of ++, --! etc. macros and 'cout', 'cerr' procedures I use in my Scheme code. Please see http://pobox.com/~oleg/ftp/Scheme/ for descriptions. The treap.scm file is the code itself. It contains 240 lines of title comments, which try to explain, well, everything. The second file, vtreap.scm, is validation/verification code: it checks to make sure _all_ treaps methods work and make sense, e.g., that delete! really deletes an association and fails (or defaults) if applied repeatedly; that put! really adds a new association if it didn't exist, or replaces the existing one; that get-min and delete-min! return the same result, but the second has the side effect, etc. This treaps package was developed using Gambit 2.5; yet there is very little, if any, of Gambit-specific in the source code. I will really appreciate any comments, questions and suggestions. -------------------==== Posted via Deja News ====----------------------- http://www.dejanews.com/ Search, Read, Post to Usenet