二分查找树：交互设计应用

第七章探讨查找树，特别是二分查找树这种数据结构。二分查找树结合了列表和向量的优点，高效实现了有序词典ADT的各项操作。

7.1 二分查找树

7.1.1 定义

二分查找树（Binary search tree）T，要么为空，要么满足以下条件：

  1. 以节点 r = (key, value) 为根。
  2. 左子树和右子树也都是二分查找树。
  3. 左子树所有节点的关键码不大于根节点的关键码 key。
  4. 右子树所有节点的关键码不小于根节点的关键码 key。

注意： 与有序词典结构一致，二分查找树允许节点关键码重复。