算法由浅入深（三）

[kekobin]

前言

非线性表（树、堆），可以说是前端程序员的内功，要知其然，知其所以然。

树

树的数据结构就像我们生活中的真实的树，只不过是倒过来的形状。

术语定义

• 节点：树中的每个元素称为节点，如 A、B、C、D、E、F、G、H、I、J。
• 父节点：指向子节点的节点，如 A。
• 子节点：被父节点指向的节点，如 A 的孩子 B、C、D。
• 父子关系：相邻两节点的连线，称为父子关系，如 A 与 B，C 与 H，D 与 J。
• 根节点：没有父节点的节点，如 A。
• 叶子节点：没有子节点的节点，如 E、F、G、H、I、J。
• 兄弟节点：具有相同父节点的多个节点称为兄弟节点，如 B、C、D。
• 节点的高度：节点到叶子节点的最长路径所包含的边数。
• 节点的深度：根节点到节点的路径所包含的边数。
• 节点层数：节点的深度 +1（根节点的层数是 1 ）。
• 树的高度：等于根节点的高度。
• 森林： n 棵互不相交的树的集合。

二叉树分类

• 二叉树
  每个节点最多只有 2 个子节点的树，这两个节点分别是左子节点和右子节点。如上图中的 1、 2、3。
  不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。以此类推，自己想四叉树、八叉树的结构图。
• 满二叉树
  一种特殊的二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。如上图中的 2。
• 完全二叉树
  一种特殊的二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。如上图的 3。
  完全二叉树与不是完全二叉树的区分比较难，所以对比下图看看。
  

堆

堆其实是一种特殊的树。只要满足这两点，它就是一个堆。

• 堆是一个完全二叉树。
  完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
  也可以说：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大顶堆。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小顶堆。

其中图 1 和 图 2 是大顶堆，图 3 是小顶堆，图 4 不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。

二叉查找树（Binary Search Tree）

一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中，叫二叉查找树，也叫二叉搜索树。
二叉查找树是一种有序的树，所以支持快速查找、快速插入、删除一个数据。
下图中， 3 个都是二叉查找树，

平衡二叉查找树

平衡二叉查找树：二叉树中任意一个节点的左右子树的高度相差不能大于 1。
从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树中平衡的意思，其实就是让整棵树左右看起来比较对称、比较平衡，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。

红黑树（Red-Black Tree）

红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

• 根节点是黑色的。
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据。
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

下面两个都是红黑树。

• 散列表：为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关键，这和计算散列值时使用的取余运算有关。数组的长度应该在 100 以上，这是为了让数据在散列表中分布得更加均匀。