codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; binary search tree: in-order predecessor and successor (define (tree key lkid rkid) (vector key lkid rkid)) (define (key tree) (vector-ref tree 0)) (define (lkid tree) (vector-ref tree 1)) (define (rkid tree) (vector-ref tree 2)) (define nil (vector 'nil 'nil 'nil)) (vector-set! nil 1 nil) (vector-set! nil 2 nil) (define (nil? tree) (eqv? tree nil)) (define (insert lt? t k) (cond ((nil? t) (tree k nil nil)) ((lt? k (key t)) (tree (key t) (insert lt? (lkid t) k) (rkid t))) ((lt? (key t) k) (tree (key t) (lkid t) (insert lt? (rkid t) k))) (else t))) (define (minimum t) (cond ((nil? t) #f) ((nil? (lkid t)) (key t)) (else (minimum (lkid t))))) (define (maximum t) (cond ((nil? t) #f) ((nil? (rkid t)) (key t)) (else (maximum (rkid t))))) (define (pred lt? t k) (define (return t) (if (nil? t) #f (key t))) (let loop ((t t) (prev nil)) (cond ((nil? t) (return prev)) ((lt? (key t) k) (loop (rkid t) t)) ((lt? k (key t)) (loop (lkid t) prev)) ((nil? (lkid t)) (return prev)) (else (maximum (lkid t)))))) (define (succ lt? t k) (define (return t) (if (nil? t) #f (key t))) (let loop ((t t) (next nil)) (cond ((nil? t) (return next)) ((lt? k (key t)) (loop (lkid t) t)) ((lt? (key t) k) (loop (rkid t) next)) ((nil? (rkid t)) (return next)) (else (minimum (rkid t)))))) (define t nil) (set! t (insert < t 3)) (set! t (insert < t 9)) (set! t (insert < t 4)) (set! t (insert < t 1)) (set! t (insert < t 7)) (set! t (insert < t 8)) (set! t (insert < t 2)) (set! t (insert < t 6)) (display t) (newline) (display (minimum t)) (newline) (display (maximum t)) (newline) (display (succ < t 0)) (newline) (display (succ < t 1)) (newline) (display (succ < t 2)) (newline) (display (succ < t 3)) (newline) (display (succ < t 4)) (newline) (display (succ < t 5)) (newline) (display (succ < t 6)) (newline) (display (succ < t 7)) (newline) (display (succ < t 8)) (newline) (display (succ < t 9)) (newline) (display (succ < t 10)) (newline) (display (pred < t 10)) (newline) (display (pred < t 9)) (newline) (display (pred < t 8)) (newline) (display (pred < t 7)) (newline) (display (pred < t 6)) (newline) (display (pred < t 5)) (newline) (display (pred < t 4)) (newline) (display (pred < t 3)) (newline) (display (pred < t 2)) (newline) (display (pred < t 1)) (newline) (display (pred < t 0)) (newline)
Private
[
?
]
Run code
Submit