Associative array/Creation: Difference between revisions
Content added Content deleted
Line 4,314: | Line 4,314: | ||
(export avl-empty?) |
(export avl-empty?) |
||
(export avl-insert) |
(export avl-insert) |
||
(export avl-search) |
|||
(export avl-search-values) |
(export avl-search-values) |
||
(export avl-check-usage) |
(export avl-check-usage) |
||
Line 4,347: | Line 4,346: | ||
"avl-empty? expects an AVL tree as argument") |
"avl-empty? expects an AVL tree as argument") |
||
(not (%bal tree))) |
(not (%bal tree))) |
||
(define (avl-search pred<? tree key) |
|||
;; Return the data matching a key, or #f if the key is not |
|||
;; found. (Note that the data matching the key might be #f.) |
|||
(define (search p) |
|||
(and p |
|||
(let ((k (%key p))) |
|||
(cond ((pred<? key k) (search (%left p))) |
|||
((pred<? k key) (search (%right p))) |
|||
(else (%data p)))))) |
|||
(avl-check-usage |
|||
(procedure? pred<?) |
|||
"avl-search expects a procedure as first argument") |
|||
(and (not (avl-empty? tree)) |
|||
(search tree))) |
|||
(define (avl-search-values pred<? tree key) |
(define (avl-search-values pred<? tree key) |
||
Line 4,530: | Line 4,514: | ||
;; having a hash function that *always* collides. At a nearly |
;; having a hash function that *always* collides. At a nearly |
||
;; opposite extreme are ideal hash trees, which never have |
;; opposite extreme are ideal hash trees, which never have |
||
;; collisions, but which, |
;; collisions, but which, towards that end, require hash values to |
||
;; the fly. |
;; ‘grow’ on the fly. |
||
;; |
;; |
||
;; Perhaps the simplest form of associative array having all three |
;; Perhaps the simplest form of associative array having all three |