如果我们简单地需要定位一个查找元素，第一选择是基于散列的查找。一些因素可能会促使我们选择二叉查找树。
·数据规模位置，并且程序必须能够处理任何规模的数据。
·数据集是高度动态的，在程序运行时候会有大量的插入和删除操作。
·程序需要按照升序或者降序来遍历元素。
一旦我们决定使用二叉查找树，我们必须做出如下的决定。
·如果我们需要从任何指定节点起有序遍历数据集，那么在节点的结构中必须包括指向父节点的指针。
·如果数据是动态的，我们必须平衡树。
在大多数应用程序中，我们需要平衡树结构来避免出现偏置，偏置树的某些分支可能会比其他分支长或者短很多，在最坏情况下，会导致图5-9那样的退化树。两个流行的平衡树可以使用。一个是AVL树，由Adel'son-Vel'skii和Landis于1962年提出。一棵AVL树遵循如下的平衡性质：任何一个节点的子树的高度都不可能比其他节点的子树的高度大1。
最近更加频繁使用的平衡树叫做红黑树。红黑树是一个近似平衡的。使用红黑树能够保证任何一个分支的长度都不会超过其他的分支长度的两倍。一个红黑树满足如下条件（Cormen等，2001）：
·每一个节点被标记为红色或者黑色。
·根节点是黑色的。
·每一个叶子节点值为空，并且是黑色的。
·所有的红色节点都有两个黑色子节点。
·从一个节点到其子树的叶子节点的每条路径包含了同样数目的黑色节点。
在图5-10中，由于篇幅的关系，我们并不会给出空值的叶子节点。当你仔细看图时，你能够想象图中每一个叶子节点实际上有两个黑色子节点，每一个都是空值。
图5-10所示的是一颗有效的红黑树，它包含7个不同的整数，按照如下的顺序插入：13，26，43，17，25，15，16。
图 5-10 红黑树样例现在我们希望加入一个键值是14的节点。按照如上所述的性质，14将会被作为13的右子节点。红黑树插入算法将会修改这棵树，如图5-11所示，我们将在下一节“解决方案”中描述这个过程。