# 数据结构与算法

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

首先，将 1 亿个 IP 地址按照哈希函数的值分成 1024 个桶，每个桶里面存储的是对应哈希值的 IP 地址。然后，对于每个桶，统计出现次数最多的 IP 地址。最后，将这 1024 个桶中出现次数最多的 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 相同，但统计性能比 AVL 树更高，所以在插入和删除中所做的后期维护操作肯定会比 AVL 树要耗时好多，但是它们的查找效率都是 O(logn)

## 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))，其中 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)。相比之下，红黑树的每个节点只需要存储颜色信息和指向父节点的指针，整体上占用的内存较少。

### 实现复杂度

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

### 并发性能

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

### 应用场景

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