我们使用符号表这个词来描写叙述一张抽象的表格。我们会将信息（值）存储在当中，然后依照指定的键来搜索并获取这些信息。键和值的详细意义取决于不同的应用。
符号表中可能会保存非常多键和非常多信息，因此实现一张高效的符号表也是一项非常有挑战性的任务。
我们会用三种经典的数据类型来实现高效的符号表：二叉查找数、红黑树、散列表。
我们使用有序数组存储键，经典的二分查找可以依据数组的索引大大降低每次查找所需的比較次数。
在查找时，我们先将被查找的键和子数组的中间键比較。假设被查找的键小于中间键，我们就在左子数组中继续查找。假设大于我们就在右子数组中继续查找。否则中间键就是我们要找的键。
普通情况下二分查找都比顺序查找快的多，它也是众多实际应用程序的最佳选择。对于一个静态表（不同意插入）来说。将其在初始化时就排序是值得的。
当然，二分查找也不适合非常多应用。现代应用须要同一时候可以支持高效的查找和插入两种操作的符号表实现。
也就是说，我们须要在构造庞大的符号表的同一时候可以随意插入（或许还有删除）键值对，同一时候也要可以完毕查找操作。
要支持高效的插入操作，我们似乎须要一种链式结构。当单链接的链表是无法使用二分查找的。由于二分查找的高效来自于可以高速通过索引取得不论什么子数组的中间元素。为了将二分查找的效率和链表的灵活性结合起来，我们须要更加复杂的数据结构。
可以同一时候拥有两者的就是二叉查找树。
二叉查找树
一颗二叉查找树（BST）是一颗二叉树，当中每一个节点都含有一个可比較的键（以及相关联的值）且每一个结点的键都大于其左子树中的随意结点的键而小于右子树的随意结点的键。
一颗二叉查找树代表了一组键（及其对应的值）的集合。而同一个集合能够用多颗不同的二叉查找树表示。
假设我们将一颗二叉查找树的全部键投影到一条直线上，保证一个结点的左子树中的键出如今它的右边，右子树中的键出如今它的右边。那么我们一定能够得到一条有序的键列。
查找
在二叉查找树中查找一个键的递归算法：
假设树是空的。则查找未命中。
假设被查找的键和根结点的键相等。查找命中。
否则我们就在适当的子树中继续查找。假设被查找的键较小就选择左子树。较大就选择右子树。
在二叉查找树中。随着我们不断向下查找，当前结点所表示的子树的大小也在减小（理想情况下是减半）
插入
查找代码差点儿和二分查找的一样简单，这样的简洁性是二叉查找树的重要特性之中的一个。
而二叉查找树的还有一个更重要的特性就是插入的实现难度和查找差点儿相同。
当查找一个不存在于树中的结点并结束于一条空链接时，我们须要做的就是将链接指向一个含有被查找的键的新结点。假设被查找的键小于根结点的键。我们会继续在左子树中插入该键。否则在右子树中插入该键。
分析
使用二叉查找树的算法的执行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。
在最好的情况下，一颗含有N个结点的树是全然平衡的。每条空链接和根结点的距离都为~lgN。在最坏的情况下。搜索路径上可能有N个结点。但在普通情况下树的形状和最好情况更接近。