数据结构知识点
首先看数据结构的知识点都有哪些，如下图所示。
- 队列和栈是经常使用的数据结构，需要了解它们的特点。队列是先进先出，栈是后进先出。
- 表，包括很多种，有占用连续空间的数组、用指针链接的单向和双向链表，首尾相接的循环链表、以及散列表，也叫哈希表。
- 图，在特定领域使用的比较多，例如路由算法中会经常使用到，图分为有向图、无向图及带权图，这部分需要掌握图的深度遍历和广度遍历算法，了解最短路径算法。
- 树的内容，树一般用作查找与排序的辅助结构，剩下两个部分都和树有关，一个是二叉树，一个是多叉树。 多叉树包括 B 树族，有 B 树、B+ 树、B* 树，比较适合用来做文件检索；另外一个是字典树，适合进行字符串的多模匹配。 二叉树包括平衡二叉树、红黑树、哈夫曼树，以及堆，适合用于进行数据查找和排序。这部分需要了解二叉树的构建、插入、删除操作的实现，需要掌握二叉树的前序、中序、后序遍历。
算法知识点
来看算法部分的知识点汇总，如下图所示。
算法题的常用解题方法。
复杂度是衡量算法好坏的标准之一，我们需要掌握计算算法时间复杂度和空间复杂度的方法。计算时间复杂度的方法一般是找到执行次数最多的语句，然后计算语句执行次数的数量级，最后用大写 O 来表示结果。
常用的字符串匹配算法，了解不同算法的匹配思路。
排序也是经常考察的知识点，排序算法分为插入、交换、选择、归并、基数五类，其中快速排序和堆排序考察的频率最高，要重点掌握，需要能够手写算法实现。
常用的查找算法，包括二分查找、二叉排序树、B 树、Hash、BloomFilter 等，需要了解它们的适用场景，例如二分查找适合小数量集内存查找，B 树适合文件索引，Hash 常数级的时间复杂度更适合对查找效率要求较高的场合，BloomFilter 适合对大数据集进行数据存在性过滤。
详解二叉搜索树
二叉搜索树
如下图所示，二叉搜索树满足这样的条件，每个节点包含一个值，每个节点至多有两个子树。每个节点左子树节点的值都小于自身的值，每个节点右子树节点的值都大于自身的值。
二叉树的查询时间复杂度是 log(N)，但是随着不断的插入、删除节点，二叉树的树高可能会不断变大，当一个二叉搜索树所有节点都只有左子树或者都只有右子树时，其查找性能就退化成线性的了。
平衡二叉树
平衡二叉树可以解决上面这个问题，平衡二叉树保证每个节点左右子树的高度差的绝对值不超过 1，例如 AVL 树。AVL 树是严格的平衡二叉树，插入或删除数据时可能经常需要旋转来保持平衡，比较适合插入、删除比较少的场景。
红黑树
红黑树是一种更加实用的非严格的平衡二叉树。红黑树更关注局部平衡而非整体平衡，确保没有一条路径会比其他路径长出 2 倍，所以是接近平衡的，但减少了许多不必要的旋转操作，更加实用。前面提到过，Java 8 的 HashMap 中就应用了红黑树来解决散列冲突时的查找问题。TreeMap 也是通过红黑树来保证有序性的。
红黑树除了拥有二叉搜索树的特点外，还有以下规则，如下图所示。
每个节点不是红色就是黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点，如图中的黑色三角。
红色节点的两个子节点都是黑色的。
任意节点到其叶节点的每条路径上，包含相同数量的黑色节点。
详解 B 树
B 树
B 树是一种多叉树，也叫多路搜索树。B 树中每个节点可以存储多个元素，非常适合用在文件索引上，可以有效减少磁盘 IO 次数。B 树中所有结点的最大子节点数称为 B 树的阶，如下图所示是一棵 3 阶 B 树，也叫 2-3 树。
一个 m 阶 B 树有如下特点：
- 非叶节点最多有 m 棵子树；
- 根节点最少有两个子树，非根、非叶节点最少有 m/2 棵子树；
- 非叶子结点中保存的关键字个数，等于该节点子树个数−1，就是说一个节点如果有 3棵子树，那么其中必定包含 2 个关键字；
- 非叶子节点中的关键字大小有序，如上图中左边的节点中 37、51 两个元素就是有序的；
- 节点中每个关键字的左子树中的关键字都小于该关键字，右子树中的关键字都大于该关键字。如上图中关键字 51 的左子树有 42、49，都小于 51，右子树的节点有 59，大于51；
- 所有叶节点都在同一层。
B 树在查找时，从根结点开始，对结点内的有序的关键字序列进行二分查找，如果找到就结束，没有找到就进入查询关键字所属范围的子树进行查找，直到叶节点。
总结一下：
- B 树的关键字分布在整颗树中，一个关键字只出现在一个节点中；
- 搜索可能在非叶节点停止；