二叉树等其他数据结构整理

深度优先周游：先根次序、后根次序、中根次序。

广度优先周游：逐层访问。

 

哈夫曼树(最优二叉树)：叶节点权值之和最小。算法题目常常给若干叶节点，让你构造最优二叉树。只需要从最小的两个叶节点值开始，其父节点为两者之和，并与第三个最小叶节点成为兄弟节点，依次类推，形成最优二叉树。

 

三种经典的数据类型来实现高效的符号表：二叉查找树(B树)、红黑树、散列表。可以看看MYSQL索引的实现，虽然没有用二叉查找树和红黑树，但是用到B+树(多路搜索树)和散列表(hash)。可参考

B+ 的搜索与 B- 树也基本相同，区别是 B+ 树只有达到叶子结点才命中（ B- 树可 以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；（即B+树的子树个数与根节点关键字个数相同，且关键字出现在叶子节点的链表里），所以mysql索引使用中MyISAM使用B+，但索引文件和数据分开的；叶子节点存放物理地址，InnoDB也使用B+，叶子节点直接存放数据，其数据文件本身按B+结构形成的索引文件。

 

二叉查找数：和快速排序几乎一样。二叉查找树的原则是根节点大于左子节点，小于右子节点。

平衡查找树：为了避免动态插入维持平衡的高代价，所以出现三节点或更多节点，而且每个节点允许保存多个键值。

红黑树：平衡二叉查找树，

      性质1. 节点是红色或黑色。

      性质2. 根节点是黑色。

      性质3 每个叶节点（NIL节点，空节点）是黑色的。

      性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

      性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

平衡二叉树（AVL树）：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

 

TreeMap实现采用红黑树却不适用二叉查找树？

其实这个问题就是在问红黑树相对于排序二叉树的优点。我们都知道排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插入节点集本身是大到小排列）；或所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种情况下，排序二叉树就变成了普通链表，其检索效率就会很差。

为了改变排序二叉树存在的不足，红黑树诞生了，它是一个更高效的检索二叉树，因此常常用来实现关联数组。追求的是局部平衡，而不是平衡二叉树的严格平衡。借来一张图展示：