二叉树作为数据结构中的字典
当我们尝试实现抽象数据类型Dictionary时，节点将与值关联。字典基本上是一组键，这些键必须是从总顺序中得出的元素。可能存在与每个键相关联的其他信息，但它不会导致任何概念上的理解。
如果字典是使用树实现的，则每个节点将拥有唯一的键。在这里，对于树中的每个节点u，每个键ul都严格小于uk，而ur中的每个键则严格大于uk。根据此不变式组织的树称为二叉搜索树。
该不变式的主要优点之一是，可以使用有序遍历在线性时间内找到键的排序列表。可以按以下方式递归定义-一棵空树，不执行任何操作，否则先在左子树上递归，取根并报告。然后返回到正确的子树。
我们可以对二进制搜索树进行多种操作。根据树的高度进行搜索。搜索是所有其他操作中更重要的操作。