> For the complete documentation index, see [llms.txt](https://gists.lanlance.cn/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gists.lanlance.cn/cs/al.md).

# 数据结构与算法

## 1. 1 亿个 IP 地址，如何去取 Top3

首先，将 1 亿个 IP 地址按照哈希函数的值分成 1024 个桶，每个桶里面存储的是对应哈希值的 IP 地址。然后，对于每个桶，用哈希表统计桶内每个 IP 的出现次数，并取出该桶内出现次数最多的若干个 IP 作为候选（注意：不能只取每个桶的 Top1，因为全局 Top3 可能集中在同一个桶内，那样会漏掉真正的 Top3）。最后，将所有桶取出的候选 IP 按出现次数合并排序，取出前三个即可。

## 2. 七大排序时间复杂度与稳定性

七大排序算法的时间复杂度和稳定性如下：

| 排序算法 |       时间复杂度      | 稳定性 |
| :--: | :--------------: | :-: |
| 冒泡排序 |      O(n^2)      |  稳定 |
| 选择排序 |      O(n^2)      | 不稳定 |
| 插入排序 |      O(n^2)      |  稳定 |
| 希尔排序 | O(nlogn)\~O(n^2) | 不稳定 |
| 快速排序 | O(nlogn)\~O(n^2) | 不稳定 |
| 归并排序 |     O(nlogn)     |  稳定 |
|  堆排序 |     O(nlogn)     | 不稳定 |

## 3. 快速排序、归并排序、堆排序

* 快速排序：快速排序是一种基于分治思想的高效排序算法。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
* 归并排序：归并排序是一种基于分治思想的高效排序算法。它的基本思想是将待排元素分成大小大致相等的两个子集合，分别对这两个子集合进行递归处理，直到子集合中只有一个元素为止，然后将两个子集合合并成一个有序序列。
* 堆排序：堆排序是一种基于堆结构的高效排序算法。它的基本思想是将待排元素构造成一个堆，然后依次取出堆顶元素（最大或最小），再将剩余元素重新构造成一个堆，重复上述操作直到所有元素都被取出。

## 4. 令牌桶算法原理

令牌桶算法是一种流量整形算法，它可以平滑地限制数据的传输速率，同时允许一定的突发流量。令牌桶算法的原理是系统会以一个恒定的速率往桶里放入令牌，桶有容量上限（超过则丢弃新令牌），而如果请求需要被处理，则需要先从桶里获取一个令牌；桶里有令牌时请求可以被立即处理（突发时桶内积攒的令牌可以一次性消耗），当桶里没有令牌可取时，请求则需要排队等待或被丢弃（依实现而定）。

## 5. 红黑树、avl 的复杂度

红黑树和 AVL 树都是常用的平衡二叉树，它们查找、插入、删除的时间复杂度都是 O(logn)。AVL 树是严格平衡的（任意节点的左右子树高度差不超过 1），树更矮，因此查找效率略高于红黑树；红黑树是近似平衡（平衡条件更宽松），插入和删除时所需的旋转和重新着色次数比 AVL 树更少（AVL 插入/删除后可能需要 O(logn) 次旋转，而红黑树平均只需常数次），因此维护成本更低，在频繁插入和删除的场景下统计性能更好。（注：上述为传统主流观点；2024 年基准研究 arXiv:2406.05162 表明，在某些工作负载下 AVL 树的插入/删除反而更快，两派结论均有实验支撑。）

## 6. 红黑树简介

红黑树是一种自平衡的二叉搜索树，它在计算机科学中被广泛应用。它的名称来自于树中节点的颜色，每个节点要么是红色，要么是黑色。红黑树具有以下特性：

1. 根节点是黑色的。
2. 每个叶子节点 (NIL 节点，空节点) 都是黑色的。
3. 如果一个节点是红色的，则它的两个子节点都是黑色的。
4. 从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点。
5. 由上述性质可推出平衡保证：从任意节点到其叶子节点的所有简单路径中，最长路径的长度不超过最短路径的两倍（每条路径上黑色节点数量相同，且红色节点不能连续出现，因此最长路径上的红色节点数至多等于黑色节点数）。

这些特性保证了红黑树的平衡性，使得它的高度始终保持在可接受的范围内。红黑树的高度是 O(logn)，其中 n 是树中节点的数量。

红黑树的自平衡性是通过在插入和删除操作后进行调整来实现的。插入和删除操作可能会破坏红黑树的特性，但通过一系列的旋转和重新着色操作，可以保持红黑树的平衡性。

红黑树在许多领域都有广泛的应用，特别是在需要高效地进行插入、删除和搜索操作的场景中。它的时间复杂度在平均和最坏情况下都是 O(log n)，使得它成为一种非常有效的数据结构。

## 7. 哈希查找时间复杂度

哈希查找的时间复杂度通常被认为是 O(1)。这是因为哈希表利用哈希函数将键映射到数组的特定位置，使得对于任意给定的键，可以通过哈希函数快速计算出其对应的存储位置。在平均情况下，哈希表的搜索、插入和删除操作的时间复杂度都是 O(1)。然而，在最坏情况下，如果发生大量的哈希冲突，哈希表的性能会退化成 O(n)。

## 8. 快排为什么不稳定

当快速排序中的枢纽元与其他元素进行交换时，可能会改变相同键值的元素的相对顺序。例如，如果有两个相同的元素 A 和 B，且 A 在 B 的前面，但在排序过程中，A 被移动到了 B 的后面，那么相同键值的元素的相对顺序就发生了改变。这就是快速排序不稳定的一个例子。

## 9. 红黑树属性

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点颜色：根节点必须是黑色。
3. 叶子节点颜色：叶子节点 (NIL 节点或空节点) 都是黑色。
4. 颜色约束：红色节点的子节点必须是黑色。换句话说，不能有两个连续的红色节点。
5. 黑高度：从任意节点（不包含该节点本身）到其每个叶子节点的路径上，黑色节点的数量都相同，这个数量称为该节点的黑高度。

## 10. 跳表原理

跳表基于链表实现，通过在原始链表的基础上建立多层索引来加速查找操作。跳表的原理是通过每两个节点抽出一个节点，建立索引层，从而减少查找路径，降低查找时间复杂度。具体原理如下：

1. 遍历有序链表时，需要从头节点开始逐个节点遍历，直到找到目标节点。这种遍历方式的时间复杂度是 O(n)。
2. 跳表的思想是每两个节点抽出一个节点，建立第一层索引。第一层索引的节点个数是原始链表节点个数的一半。
3. 在第一层索引的基础上，再每两个节点抽出一个节点，建立第二层索引。第二层索引的节点个数是第一层索引节点个数的一半。
4. 以此类推，建立多层索引，直到达到某个条件（如节点个数小于等于 2）为止。
5. 当需要查找数据时，从最高层索引开始，逐层向下查找，直到找到目标节点或者找不到为止。
6. 在每一层索引中，通过比较节点的值，确定下一步的查找方向，可以快速缩小查找范围。
7. 如果在某一层索引中找到目标节点，则返回该节点；如果在最底层索引中仍然找不到目标节点，则表示数据不存在。

跳表的查询时间复杂度平均为 O(log⁡(n))（期望复杂度；随机化结果最差时可能退化为 O(n)），其中 n 是原始链表的节点个数。跳表的插入和删除操作也可以通过类似的方式进行实现，时间复杂度也是 O(log⁡(n))。跳表的优势在于可以在不使用平衡树的情况下，实现高效的查找、插入和删除操作。

## 11. 有哪些常见的二叉树

1. **满二叉树**：
   * 每个非叶子节点都有两个子节点，且所有叶子节点都在同一层。（注：" 满二叉树 " 存在两种定义，另一种定义为 " 每个节点要么没有子节点、要么有两个子节点 "，不要求叶子节点在同一层；两种定义在不同教材中均有使用。）
2. **完全二叉树**：
   * 除了最后一层外，每层的节点数都达到最大，且最后一层的节点集中在最左边。
3. **二叉搜索树（Binary Search Tree, BST）**：
   * 对于每个节点，左子树的所有节点值小于该节点，右子树的所有节点值大于该节点。中序遍历该树会得到一个有序序列。
4. **平衡二叉树**：
   * 也称为 AVL 树，要求每个节点的左右子树高度差不超过 1，确保树的高度保持在对数级别，从而提高查找效率。
5. **红黑树**：
   * 一种自平衡的二叉搜索树，每个节点有颜色属性（红或黑），并遵循特定的性质以保持树的平衡。
6. **哈夫曼树**：
   * 一种带权路径长度最小的二叉树，通常用于数据压缩。

## 12. 跳表和红黑树的优劣对比

### 时间复杂度

* **查询**：跳表和红黑树的平均时间复杂度均为 O(log⁡n)，但在最坏情况下，跳表的查询复杂度可能达到 O(n)，而红黑树则保持在 O(log⁡n)。
* **插入和删除**：跳表的插入和删除操作相对简单，通常只涉及指针的调整，时间复杂度为 O(log⁡n)。红黑树的插入和删除则需要进行复杂的平衡调整，旋转和着色操作，因此实现较为复杂，但时间复杂度同样为 O(log⁡n)。

### 空间复杂度

跳表的空间复杂度较高，因为它需要额外的指针来维护多层结构，通常为 O(n)。相比之下，红黑树的每个节点只需要存储颜色信息和指向父节点的指针，整体上占用的内存较少。（注：这一对比存在争议：跳表每个节点平均约需 2 个前向指针，而红黑树每个节点需要 left/right/parent 共 3 个指针外加颜色位，实际两者内存开销差异不大，甚至红黑树可能更高，具体取决于实现。）

### 实现复杂度

* **跳表**：实现较为简单，易于理解和调试，尤其适合快速开发和原型设计。跳表的结构类似于链表，插入和删除操作相对直接。
* **红黑树**：实现复杂，需要处理多种情况以保持树的平衡，涉及旋转和颜色调整，增加了开发和维护的难度。

### 并发性能

在并发环境下，跳表的更新操作相对较少，锁的竞争较低，因此在多线程环境中表现良好。而红黑树在并发操作时，由于其复杂的平衡调整，可能会导致更多的锁竞争。

### 应用场景

* **跳表**：由于其简单性和良好的性能，跳表常用于需要快速插入、删除和查找的场景，如 Redis 的有序集合（zset）实现中。
* **红黑树**：适用于对性能要求较高且需要频繁查找的场景，如许多标准库中的集合实现，特别是在需要保持严格平衡时。