youtube bst 公开课
bst
bst(binary search tree) vs bt(binary tree)
以一个node来说，bst一定是(node左边所有)< node < (node右边所有)， bt 的话没要求
bst例子
好。bst在racket的定义
;; Data definitions:
(define-struct node (key val l r))
;; BST (Binary Search Tree) is one of:
;; - false
;; - (make-node Integer String BST BST)
;; interp. false means no BST, or empty BST
;; key is the node key
;; val is the node val
;; l and r are left and right subtrees
(define BST0 false)
(define BST1 (make-node 1 "abc" false false))
(define BST4 (make-node 4 "dcj" false (make-node 7 "ruf" false false)))
(define BST3 (make-node 3 "ilk" BST1 BST4))
#;
(define (fn-for-bst bst)
(cond [(false? bst) (...)]
[else
(... (node-key bst) ;Integer
(node-val bst) ;String
(fn-for-bst (node-l bst))
(fn-for-bst (node-r bst)))]))
用一题看一下template是怎么运行的
;; BST Integer -> String or false
;; search bst for key k and produce its val, false if k not found
(check-expect (key-search BST4 7) "ruf")
(check-expect (key-search BST4 14) false)
;(define (key-search bst k) "") ;stub
;; Template from BST with additional atomic parameter
(define (key-search bst k)
(cond [(false? bst) false]
[else
(cond [(= k (node-key bst)) (node-val bst)]
[(< k (node-key bst)) (key-search (node-l bst) k)]
[else (key-search (node-r bst) k)])]))
以第一个check-expect 为例子
(check-expect (key-search BST4 7) "ruf")
假设是找key = 14的话，一直会走到底遇到false，这时候就会produce false
因为base case [(false? bst) false]