2.7.3　二叉树、二叉查找树、平衡二叉树、红黑树和B树

二叉树及其衍生的所有算法都是以“父节点有且只有至多两个子节点”为规则的。二叉查找树就是在二叉树上建立的查找树，主要目标是快速查找，它在构造时的特点为，左边的子节点一定比父节点小，右边的子节点一定比父节点大。算法的方式与二分查找算法类似，不同之处在于二分查找树构建出来的树形结构，由于原始数据的排列不同，有可能导致深度很大的二叉树犹如直线连接的节点，因此它是一个不稳定的查找方式，搜索的速度由原始数据的排列方式决定，若排列的顺序不好，则速度就不快，因此二叉树的稳定性并不高。

平衡二叉树很好地解决了二叉查找树和二叉树的不平衡问题，它的规则是父节点的左、右两棵树的深度差的绝对值不能超过1，所有节点都遵循这个规则，包括节点下的左、右两棵子树叶同样遵循这个规则。二叉树的深度问题解决了，在查找时的效率就更加稳定，如果能一直保持O(lgN)的时间复杂度，那将有很好的算法效率。

红黑树就是实现平衡二叉树的算法，它们是在插入和删除节点操作时通过特定的操作保持二叉查找树的平衡，从而使得二叉查找时获得较高的查找效率。它虽然复杂，但它的最坏情况运行时间也是良好的，并且在实践中是高效的，它能够在O(lgN)时间复杂度内执行查找、插入和删除操作，这里的N为二叉树中元素的数目。

红黑树的数据结构特点是在各节点上多了一个颜色值，颜色为红色或黑色。通过对任何一条从根到叶子路径上各节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。红黑树的具体算法和程序步骤在此不介绍，有兴趣的读者可查阅相关资料。

红黑树虽然高效、稳定，但在实际项目中运用得较少。一方面，红黑树通常会封装在自定义的底层容器算法中，例如，我们通常会重新封装Map、Dictionary容器，将红黑树放入容器中，让编写业务逻辑的读者在不需要关心底层算法的情况下高效使用容器。另一方面，红黑树算法的复杂度高，一般程序员都要费点心思去研究，因此通常不会放在明显的位置上使用，这也是红黑树一般会放入容器里使用的原因之一，它更适合容器类外壳。再有一方面，查找可以用“快速排序”+“二分查找”代替，效率虽差但简单实用，使用优化后的快速排序效率，在查找效率上会优于红黑树，如果逻辑中查找的次数远大于插入与删除的次数，则可以考虑使用“快速排序”+“二分查找”代替这种方式进行查找。

B树大家听得也比较多，它主要是为磁盘存储设备而设计的一种平衡查找树。它与红黑树的不同在于，B树是建立在查找树上的多叉树，它的一个节点上有多个值且父节点可以拥有两个以上的节点，同时必须保持平衡树的层次结构，即树的深度值不得超过lgN的深度（N为节点个数）。这种数据结构犹如在红黑树之上建立多叉的方式，其比较方式由单一值比较改为多值比较。在B树结构里，一个节点里的信息是一个数组，它们是有序的，因此可用二分查找算法查找数据，若没有找到准确值，则继续往下搜索子节点的数据。B树在游戏项目中很少用到，但它在文件信息存储结构上能发挥巨大作用，这也是它被开发出来的原因之一，其他如B+树和B*树都是从B树衍生而来的。