# 数据结构与算法

## 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）实现中。
* **红黑树**：适用于对性能要求较高且需要频繁查找的场景，如许多标准库中的集合实现，特别是在需要保持严格平衡时。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gists.lanlance.cn/cs/al.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.