《数据结构》中的一些会遇到的面试题

（一）AVL 树

AVL 树是平衡二叉查找树，增加和删除节点后通过旋转重新达到平衡，旋转包括左旋和右旋。左旋是以某节点为中心，将它沉入当前左子节点的位置，而让当前的右子节点作为新树的根节点，称为逆时针旋转，右旋同理。

（二）红黑树

每个节点上有一个颜色属性，是红色或黑色。红黑树通过重新着色和左右旋转，高效地实现了平衡调整。

红黑树本质上是二叉查找树，额外引入了 5 个约束条件：① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NIL 节点都是黑色的。④ 一条路径上不能出现相邻的红色节点。⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。这五个条件保证了红黑树增删查的最坏时间复杂度均为 O(log~n~)。红黑树的任何旋转在 3 次之内均可完成。

红黑树的平衡性不如 AVL 树，它维持的只是一种大致的平衡，不严格保证左右子树的高度差不超过 1。节点数相同的情况下，红黑树的高度可能更高，平均查找次数会高于 AVL 树。

在插入时，红黑树和 AVL 树都能在至多两次旋转内恢复平衡，在删除时由于红黑树只追求大致平衡，因此至多三次旋转可以恢复平衡，而 AVL 树最多需要 O(log~n~) 次。面对频繁地插入与删除红黑树更加合适。

（三）B 树

B 树 又叫多路平衡搜索树，一颗 m 叉的 B 树：

• 树中每个节点最多包含 m 个子节点。

• 除根节点与叶子节点外，每个节点至少有 ceil(m/2) 个子节点。

• 所有的叶子节点都在同一层。

• 每个非叶子节点由 n 个 key 与 n+1 个指针组成，其中 ceil(m/2)-1 <= n <= m-1。

B 树和二叉树相比，查询效率更高，因为 B 树的层级结构比二叉树小（深度小，需要遍历的次数少）。

（四）B+ 树

B 树中每个节点同时存储 key 和 data，而 B+ 树中只有叶子节点才存储 data，非叶子节点只存储 key。InnoDB 对 B+ 树进行了优化，在每个叶子节点上增加了一个指向相邻叶子节点的链表指针，形成了带有顺序指针的 B+ 树，提高区间访问的性能。

B+ 树的优点：

• 由于 B+ 树在非叶子节点上不含数据信息，因此在内存中能够存放更多的 key，数据存放得更紧密，利用率更高。

• B+ 树的叶子节点都是相连的，对整棵树的遍历只需要对叶子节点进行一次线性遍历，而 B 树则需要每层递归遍历，相邻元素可能在内存中不相邻，缓存命中率没有 B+ 树好。

• B 树的优点是，由于每个节点都包含 key 和 value，经常访问的元素可能离根节点更近，访问也更迅速。

（五）图

图表示多对多关系，根据边的属性分为有向图和无向图。

存储结构：

• 邻接矩阵：一个一维数组存储图的顶点信息，一个二维数组存储图的边/弧信息。无向图中 1 表示两个顶点连通，0 表示不连通；有向图中 1 表示存在弧，0 表示不存在弧。

• 邻接表：邻接表是一种链式存储结构，结合了数组与链表。将顶点存储在一个一维数组中，同时在顶点信息中存储用于指向第一个邻接点的指针。图中每个顶点的所有邻接点构成了一个线性表，由于邻接点个数不定，所以用单向链表存储。

遍历：

• 广度优先：类似树的层次遍历，在访问某顶点后依次访问该顶点的各个未访问的邻接点。

• 深度优先：类似树的先序遍历，在访问某顶点后，按深度优先访问其邻接点。