8.6 壬子
bst-simple.dfy
datatype bst = Lf
| Node(key: string, Value: int, left: bst, right: bst)
/*
A three element tree:
"j",6
/ \
"i",7 "k",-2
*/
const t3: bst := Node("j", 6, Node("i", 7, Lf, Lf), Node("k", -2, Lf, Lf))
function build2(k1: string, k2: string, v1: int, v2: int): bst
//complete!
根 左子树 右子树
if k1 < k2 then Node(k2, v2, Node(k1, v1, Lf, Lf), Lf)
没有分号;
else Node(k1, v1, Node(k2, v2, Lf, Lf), Lf);万一 k1 = k2 呢? 只保留一个名字，因为只有一个根
else if k1 > k2 then Node(k1, v1, Node(k2, v2, Lf, Lf), Lf)
else Node(k1, v1, Lf, Lf)8.14 庚申
-
bst = Lf 是什么?
-
Node 咋这样定义? left 原来是 Node
-
为什么写成 ("i", 7, Lf, Lf)?
-
题目里的函数 function build2(k1 ...) 里的 k1, k2, v1, v2 是啥? key 和 value 吧
-
bst = Lf 是什么?
datatype bst = Lf | Node(key: string, value: int, left: bst, right: bst)一个 bst 类型的值, 要么是 Lf, 或者是 Node(四样东西)
| 是或者，隔开几种这个类型的造法。
列表世界: Nil = 空列表, "到此为止"。Cons(元素, 一条列表) = 加头机, 2个坑
树世界: Lf = 空树, "到此为止"。 Node(key, value, 树, 树) = 造节点机, 4个坑。
Lf 就是树版的 Nil, 名字取自 Leaf(叶)。一棵什么都没有的空树, 同时充当一切递归"到底了"的标志。
- Node 咋这样定义?
key: 字符串, 查字典用的词条名, value, 整数, 词条内容。left 和 right 的类型是 bst 本身, (四个坑各司其职), 这和 Cons 第二个坑只吃列表是同一个设计。类型自己引用自己, 套娃由此而来。
唯一的区别：
①列表每层只嵌一个内层套娃 tl。列表是单链
②树每层嵌两个(left, right)。树是分叉。- 为什么写成 ("i", 7, Lf, Lf)?
四个坑挨个填: key 填 "i", value 填 7, left 填 Lf, right 填 Lf。两个 Lf 的意思: 这个节点左边没有孩子, 右边也没有孩子。它是树梢上的末端节点。就像 Cons(2, Nil) 里的 Nil 宣告"2后面没了"。这里两个 Lf 宣告"i下面没了"。坑必须填满, 没有孩子也不能空着, 拿 Lf 堵上。
const t3: bst := Node("j", 6, Node("i", 7, Lf, Lf), Node("k", -2, Lf, Lf))
↑ ↑ ↑ ↑
坑1 坑2 坑3(整棵左子树) 坑4(整棵右子树)根是"j",6; 第3个坑装的不是一个元素, 是一整棵树。和 Cons 逗号后面装的是"剩下的整条列表"一个道理; 括号套括号 = 树杈套树杈
- function build2(k1 ...)里的 k1, k2, v1, v2 是啥?
function build2(k1: string, k2: string, v1: int, v2: int): bstbuild2 的任务是收两个词条(词条一: k1配v1; 词条二: k2配v2), 造一棵装着它俩的合法小树。参数名里的数字只是配对编号, 没有别的玄机。
5. 为什么是 Node(k2, v2, Node(k1, v1, Lf, Lf), Lf)
↑ ↑ ↑ ↑
坑1 坑2 坑3: 左孩子位置 坑4: 右边没人
根的key 根的value 装了一棵小树, (k1词条)
k2, v2 ← k2 当根
/ \
k1, v1 空 ← k1 蹲在左下方
/ \
空 空- 为什么 k2 当根, k1 蹲左边?
因为 k1 < k2, k1 比较小, BST 的家规: 每个节点, 比它小的住左边, 比它大的住右边。k1 小, 所以 k1 必须住 k2 的左边。
这棵树当字典用的, 查词全靠"小往左, 大往右"来砍半抄近路。树要是乱摆, 查找就会走错方向。明明存了却找不到。
- 为什么 Cons 叫加头机?
因为它干的活就是"给列表加一个头"。
5 →
Cons → [5,3,9] ← 新列表, 5 排最前。
[3,9] →一个元素 + 一个旧列表 ⇒ 一条新列表
两个进料口: 一个吃单个元素, 一个吃一条完整列表; 一个出料口: 吐出新列表, 新来的元素站在头部。它只会往前加, 不会往尾巴上接。想造 [5,3,9] 就要从尾巴倒着造, 先有 Nil, 加9, 加3, 最后加5。这就是为什么 Cons 写法里最先看到的5反而是最后一个装上去的零件。
Cons(5, Cons(3, Cons(9, Nil)))
↑ ↑
最后装 最先装。只能从头加是整套体系的一致性所在: match 拆的时候也只能从头拆 Cons(y, ys) 撬出来的永远是头和剩余。一头进一头出, 加和拆是同一扇门。
树那边 Node 是拿两棵子树当左右手, 在上方造一个新的根。列表往前长, 树往上长
小树甲: 小树乙:
"i", 7 "k", -2
/ \ / \
Lf Lf Lf Lf然后执行 Node("j", 6, 小树甲, 小树乙), 产出:
"j", 6 ← 新造的节点, 坐在最顶上
/ \
"i", 7 "k", -2 ← 两棵旧树挂在它下面。
/ \ / \
Lf Lf Lf Lf
``