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]