Download MIT Scheme Reference Manual

Chapter 11: Associations
141
rb-tree/equal? rb-tree-1 rb-tree-2 datum=?
procedure
Compares rb-tree-1 and rb-tree-2 for equality, returning #t iff they are equal and
#f otherwise. The trees must have been constructed with the same equality and
order predicates (same in the sense of eq?). The keys of the trees are compared
using the key=? predicate used to build the trees, while the datums of the trees are
compared using the equivalence predicate datum=?. The worst-case time required by
this operation is proportional to the number of associations in the tree.
rb-tree/empty? rb-tree
procedure
Returns #t iff rb-tree contains no associations. Otherwise returns #f.
rb-tree/size rb-tree
procedure
Returns the number of associations in rb-tree, an exact non-negative integer. The average and worst-case times required by this operation are proportional to the number
of associations in the tree.
rb-tree/height rb-tree
procedure
Returns the height of rb-tree, an exact non-negative integer. This is the length of the
longest path from a leaf of the tree to the root. The average and worst-case times
required by this operation are proportional to the number of associations in the tree.
The returned value satisfies the following:
(lambda (rb-tree)
(let ((size (rb-tree/size rb-tree))
(lg (lambda (x) (/ (log x) (log 2)))))
(<= (lg size)
(rb-tree/height rb-tree)
(* 2 (lg (+ size 1))))))
rb-tree/copy rb-tree
procedure
Returns a newly allocated copy of rb-tree. The copy is identical to rb-tree in all
respects, except that changes to rb-tree do not affect the copy, and vice versa. The
time required by this operation is proportional to the number of associations in the
tree.
alist->rb-tree alist key=? key<?
procedure
Returns a newly allocated red-black tree that contains the same associations as alist.
This procedure is equivalent to:
(lambda (alist key=? key<?)
(let ((tree (make-rb-tree key=? key<?)))
(for-each (lambda (association)
(rb-tree/insert! tree
(car association)
(cdr association)))
alist)
tree))