codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; lowest common ancestor (define (tree k l r) (vector k l r)) (define (key t) (vector-ref t 0)) (define (lkid t) (vector-ref t 1)) (define (rkid t) (vector-ref t 2)) (define nil (vector 'nil 'nil 'nil)) (define (nil? t) (eq? t nil)) (define (lookup lt? t k) (cond ((nil? t) #f) ((lt? k (key t)) (lookup lt? (lkid t) k)) ((lt? (key t) k) (lookup lt? (rkid t) k)) (else #t))) (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 (tree k (lkid t) (rkid t))))) (define (lca lt? t lo hi) (cond ((and (not (lt? (key t) lo)) (not (lt? hi (key t)))) (key t)) ((lt? (key t) lo) (lca lt? (rkid t) lo hi)) (else (lca lt? (lkid t) lo hi)))) (define t nil) (set! t (insert < t 8)) (set! t (insert < t 3)) (set! t (insert < t 10)) (set! t (insert < t 1)) (set! t (insert < t 6)) (set! t (insert < t 14)) (set! t (insert < t 4)) (set! t (insert < t 7)) (set! t (insert < t 13)) (display (lca < t 4 7)) (newline) ; 6 (display (lca < t 4 10)) (newline) ; 8 (display (lca < t 1 4)) (newline) ; 3 (display (lca < t 1 3)) (newline) ; 3 (display (lca < t 3 6)) (newline) ; 3
Private
[
?
]
Run code
Submit