UBC - CPSC 110 - Binary Search Trees

在一个列表中寻找元素是一个很简单的需求，但在实际生活中，它的数据量往往非常庞大。这时候我们就需要考虑性能这一要求，使用更高效的数据结构来提高查找效率。

这个新的自我引用数据结果就是二叉搜索树。 (Binary Search Tree, BST)

我们将围绕 BST 设计数据定义和函数，所用的知识和往常无异，当然，递归也是会被经常用到的。

学习目标

以下内容涉及到的edX链接均不保证可访问性

在研究 BST 之前，介绍一个定义列表的简便方法，比连着写一串cons更好看。比如说，对于(cons "a" (cons "b" (cons "c" empty)))，我们可以把它写成(list "a" "b" "c")。

Choose Language

记得在 DrRacket 的左下方，将Beginning Student切换为Beginning Student with List Abbreviations。

选择语言

切换后，运行刚刚的cons和list你会得到相同的结果：

1 2	(list "a" "b" "c") (list "a" "b" "c")

那我们之前为什么要费劲写这么多cons？只是为了介绍递归的概念不得不做的事。在熟悉它们后，自然就可以切换到更简单的写法了。

list表达式可以传入多个元素，而不仅仅是两个。同时，构建时里面的表达式也会被计算，比如：

1 2	(list (+ 1 2) (+ 3 4) (+ 5 6)) > (list 3 7 11)

行为不同

和cons不同，它的拼接过程本质不一样。cons在将元素和列表合并的时候，会将元素插入列表的首位。而list会将列表视为一个整体，将列表放到元素之后：

(cons "a" (list "b" "c"))
> (list "a" "b" "c")

(list "a" (list "b" "c"))
> (list "a" (list "b" "c"))

如果想让list达到相同效果，可以使用append表达式：

1 2	(append (list "b" "c") (list "d" "e" "f")) > (list "b" "c" "d" "e" "f")