6.2.901.900
9 Treap
Treaps are binary search trees in which each node has both a search key
and a priority. Its keys are sorted in inorder and its each node priority
is smaller than the priorities of its children. Because of this, a treap
is a binary search tree for the keys and a heap for its priorities.
This implementation uses random priorities to achieve good average-case
performance.
Provides worst case running time of O(log(n)) for the
operations insert, find-min/max and
delete-min/max.
A treap of type A.
(treap comp a ...) → (Treap A)
|
| comp : (A A -> Boolean) |
| a : A |
Function
treap creates a Treap with the given
inputs.
Example: |
| > (treap < 1 2 3 4 5 6) | - : (Treap Positive-Byte) | #<Treap> |
|
In the above example, the treap obtained will have elements 1 thru’ 6
with < as the comparison function.
Function
empty? checks if the given treap is empty or not.
Examples: |
| > (empty? (treap < 1 2 3 4 5 6)) | - : Boolean | #f | | > (empty? (treap <)) | - : Boolean | #t |
|
Function
insert takes an element and a treap and inserts
the given element into the treap.
Example: |
| > (insert 10 (treap < 1 2 3)) | - : (Treap Positive-Byte) | #<Treap> |
|
In the above example, insert adds the element 10 to
(treap < 1 2 3).
Function
find-min/max takes a treap and gives the
largest or the smallest element in the treap if treap is not empty
else throws an error. The element returned is largest or smallest depends
on the comparison function of the treap.
Examples: |
| > (find-min/max (treap < 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Byte] | 1 | | > (find-min/max (treap > 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Byte] | 6 | | > (find-min/max (treap <)) | find-min/max: given treap is empty |
|
Function
delete-min/max takes a treap and returns the
same treap without the min or max element in the given treap. The element
removed from the treap is max or min depends on the comparison function of the
treap.
Examples: |
| > (delete-min/max (treap < 1 2 3 4 5 6)) | - : (Treap Positive-Byte) | #<Treap> | | > (delete-min/max (treap > 1 2 3 4 5 6)) | - : (Treap Positive-Byte) | #<Treap> | | > (delete-min/max (treap <)) | delete-min/max: given treap is empty |
|
In the above example, (delete-min/max (treap < 1 2 3 4 5 6)),
deletes the element 1(min) from the treap. And
(delete-min/max (treap > 1 2 3 4 5 6)), deletes
the element 6(max) from the treap.
Function
delete deletes the given element from the given treap.
Examples: |
| > (delete 6 (treap < 1 2 3 4 5 6)) | - : (Treap Positive-Byte) | #<Treap> | | > (delete 3 (treap > 1 2 3 4 5 6)) | - : (Treap Positive-Byte) | #<Treap> | | > (delete 10 (treap <)) | eval:15:0: Type Checker: Polymorphic function `delete' could | not be applied to arguments: | Argument 1: | Expected: A | Given: Positive-Byte | Argument 2: | Expected: (Treap A) | Given: (Treap Nothing) | | in: < |
|
In the above example, (delete 6 (treap < 1 2 3 4 5 6)),
deletes the 6 returns (treap < 1 2 3 4 5). And
(delete 3 (treap > 1 2 3 4 5 6)) returns
(treap > 1 2 4 5 6).
Function
treap->list takes a treap and returns a list
which is sorted according to the comparison function of the treap.
Examples: |
| > (treap->list (treap > 1 2 3 4 5 6)) | - : (Listof Positive-Byte) | '(3 6 5 4 1 2) | | > (treap->list (treap < 1 2 3 4 5 6)) | - : (Listof Positive-Byte) | '(1 5 2 3 4 6) |
|
(map comparer func treap1 treap2 ...) → (Treap A)
|
| comparer : (C C -> Boolean) |
| func : (A B ... B -> C) |
| treap1 : (Treap A) |
| treap2 : (Treap B) |
Function
map is similar to
map for lists.
(fold func init treap1 treap2 ...) → C
|
| func : (C A B ... B -> C) |
| init : C |
| treap1 : (Treap A) |
| treap2 : (Treap B) |
fold currently does not produce correct results when the
given function is non-commutative.
Examples: |
| > (fold + 0 (treap < 1 2 3 4 5 6)) | - : Integer [more precisely: Nonnegative-Integer] | 21 | | > (fold * 1 (treap < 1 2 3 4 5 6) (treap < 1 2 3 4 5 6)) | - : Integer [more precisely: Positive-Integer] | 518400 |
|
Examples: |
| > (define trp (treap < 1 2 3 4 5 6)) | | | > (treap->list (filter (λ: ([x : Integer]) (> x 5)) trp)) | - : (Listof Positive-Byte) | '(6) | | > (treap->list (filter (λ: ([x : Integer]) (< x 5)) trp)) | - : (Listof Positive-Byte) | '(2 1 3 4) | | > (treap->list (filter (λ: ([x : Integer]) (<= x 5)) trp)) | - : (Listof Positive-Byte) | '(3 2 1 5 4) |
|
Function
remove is similar to
filter but
remove removes the elements which satisfy the predicate.
Examples: |
| - : (Listof Positive-Byte) | '(4 3 2 1 5) | | - : (Listof Positive-Byte) | '(6 5) | | - : (Listof Positive-Byte) | '(6) |
|
(andmap func treap1 treap2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| treap1 : (Treap A) |
| treap2 : (Treap B) |
(ormap func treap1 treap2 ...) → Boolean
|
| func : (A B ... B -> Boolean) |
| treap1 : (Treap A) |
| treap2 : (Treap B) |
Examples: |
| > (ormap even? (treap < 1 2 3 4 5 6)) | - : Boolean | #t | | > (ormap odd? (treap < 1 2 3 4 5 6)) | - : Boolean | #t | | > (ormap positive? (treap < -1 -2 3 4 -5 6)) | - : Boolean | #t | | > (ormap negative? (treap < 1 -2)) | - : Boolean | #t |
|
(build-treap size func comp) → (Treap A)
|
| size : Natural |
| func : (Natural -> A) |
| comp : (A A -> Boolean) |