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

Q2：什么是红黑树？
红黑树 是 1972 年发明的，称为对称二叉 B 树，1978 年正式命名红黑树。主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树 类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。与 AVL 树 相比，红黑树不追求所有递归子树的高度差不超过 1，保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件：① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NIL 节点都是黑色的。④ 一条路径上不能出现相邻的两个红色节点。⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。

这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。

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

在插入时，红黑树和 AVL 树都能在至多两次旋转内恢复平衡，在删除时由于红黑树只追求大致平衡，因此红黑树至多三次旋转可以恢复平衡，而 AVL 树最多需要 O(logn) 次。AVL 树在插入和删除时，将向上回溯确定是否需要旋转，这个回溯的时间成本最差为 O(logn)，而红黑树每次向上回溯的步长为 2，回溯成本低。因此面对频繁地插入与删除红黑树更加合适。

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

B+ 树的优点在于：

① 由于 B+ 树在非叶子节点上不含数据信息，因此在内存页中能够存放更多的 key，数据存放得更加紧密，具有更好的空间利用率，访问叶子节点上关联的数据也具有更好的缓存命中率。

② B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而 B 树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有 B+树好。但是 B 树也有优点，由于每个节点都包含 key 和 value，因此经常访问的元素可能离根节点更近，访问也更迅速。

Q5：排序有哪些分类？
排序可以分为内部排序和外部排序，在内存中进行的称为内部排序，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序。

内部排序包括比较排序和非比较排序，比较排序包括插入/选择/交换/归并排序，非比较排序包括计数/基数/桶排序。

插入排序包括直接插入/希尔排序，选择排序包括直接选择/堆排序，交换排序包括冒泡/快速排序。

Q6：直接插入排序的原理？
稳定，平均/最差时间复杂度 O(n²)，元素基本有序时最好时间复杂度 O(n)，空间复杂度 O(1)。

每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

数据结构题目一直是面试官考察的重点。数组和字符串是两种最基本的数据结构。链表应该是面试题中使用频率最高的一种数据结构。如果面试官想加大面试难度，那么
他很有可能会选用与树(尤其是二叉树)想关的面试题。由于栈与递归调用密切相关，队列在图(包括树)的宽度优先遍历中需要用到，需账务这两种数据结构。

算法是面试官喜欢考察的另外一个重点。
查找(特别是二分查找)和排序(特别是快速排序和归并排序)是面试中经常考察的算法，应聘者一定要熟练掌握。
回溯法很适合解决迷宫及其类似的问题。如果面试题是求一哥问题的最优解，那么可以尝试使用动态规划。假如我们在用动态规划分析问题时发现每一步都存在一个能
得到最优解的选择，那么可以尝试使用贪婪算法。另外，应聘者还要掌握分析时间复杂度的方法，理解即使同一思路，基于循环和递归的不同实现，他们的时间复杂度
可能大不相同。很多时候我们会用自上而下的递归思路分析问题，却会基于自下而上的循环实现代码。
位运算是针对二进制数字的运算规则。需掌握二进制的与、或、异或运算及左移、右移操作，就能解决与运算相关的面试题。

不使用新的变量，交换两个变量的值。比如有两个变量a、b，我们希望交换他们的值。有两种不同的方法：
基于加减法：
a = a + b
b = a - b
a = a - b
基于异或运算：
a = a ^ b
b = a ^ b
a = a ^ b

位运算是把数字用二进制表示之后，对每一位上0或者1的运算。
与(&) 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1
或(|) 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1
异或(^) 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0

把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变为0。
很多二进制问题都可以用这种思路解决。

稳定的
冒泡排序（bubble sort）— O(n2)
鸡尾酒排序（cocktail sort,双向的冒泡排序）—O(n2)
插入排序（insertion sort）—O(n2)
桶排序（bucket sort）—O(n);需要O(k)额外空间
计数排序（counting sort）—O(n+k);需要O(n+k)额外空间
归并排序（merge sort）—O(n log n);需要O(n)额外空间
原地归并排序— O（n2）
二叉排序树排序（binary tree sort）— O(n log n)期望时间; O(n2)最坏时间;需要O(n)额外空间
鸽巢排序（pigeonhole sort）—O(n+k);需要O(k)额外空间
基数排序（radix sort）—O(n·k);需要O(n)额外空间
侏儒排序（gnome sort）— O(n2)
图书馆排序（library sort）— O(n log n) with high probability,需要(1+ε)n额外空间
不稳定
选择排序（selection sort）—O(n2)
希尔排序（shell sort）—O(n log n)如果使用最佳的现在版本
组合排序— O(n log n)
堆排序（heap sort）—O(n log n)
平滑排序（smooth sort）— O(n log n)
快速排序（quick sort）—O(n log n)期望时间, O(n2)最坏情况;对于大的、乱数列表一般相信是最快的已知排序
内省排序（introsort）—O(n log n)
耐心排序（patience sort）—O(n log n + k)最坏情况时间，需要额外的O(n + k)空间，也需要找到最长的递增子串行（longest increasing subsequence）
不实用的排序算法
Bogo排序— O(n × n!)，最坏的情况下期望时间为无穷。
Stupid排序—O(n3);递归版本需要O(n2)额外存储器
珠排序（bead sort）— O(n) or O(√n),但需要特别的硬件
Pancake sorting—O(n),但需要特别的硬件
臭皮匠排序（stooge sort）算法简单，但需要约n^2.7的时间