当数组需要保持有序时，添加和删除元素的计算量都是很大的。BST与有序数组相似，里面的值（key）是有序存储的。
BST可以搜索某个key、找到最小和最大的元素、找到某个要搜索key（不需要在BST中）的前驱和后继、按顺序列出一定范围内的key。
然而，不像有序数组，从BST中添加和删除key是高效的。
BST是一种二叉树，里面的节点存储的key是可比较的，例如整型和字符串。
存储在节点中的key需要遵从BST的法则，某个节点中存储的key需要大于等于左子树中的所有节点的key，需要小于等于右子树中的所有节点的key。
key的查找，插入和删除时间复杂度与树的高度成正比，最差情况为O(n)，当BST的插入和删除是以非常白痴的方式实现的。
然而，有一些插入和删除的实现方式可以保证树的高度是O(nlogn)。这要求在树的节点存储和更新额外的数据。红黑树就是一种高度平衡的BST，被广泛的用在数据结构库中。
BST的原型代码：
template<typename T>
struct BSTNode {
T data;
unique_ptr<BSTNode<T>> left, right;
};
搜索是BST的最基础的应用。和哈希表不同，BST可以找到最小和最大的元素，找到下一个最大/最小元素。对于库里实现的BST，这些操作，与查找，删除的时间复杂度都是O(logn)。BST和哈希表都用了O(n)的空间，在实际中，BST用的空间会稍微多一点。
