数据结构八股
跳表
跳表的本质是在一个有序链表上加入多层索引，来优化快速查找
跳表的搜索，是从第一个元素的最上面索引开始
搜索1然后搜索第一层的13然后进入下一层索引，直至找到目标元素
红黑树
红黑树是一种自平衡的二叉搜索树，它在插入和删除操作后能够通过旋转和重新着色来保持树的平衡。具有以下特点：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL节点）是黑色。
- 如果一个节点是红色，则其子节点必须是黑色。
- 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
| 特性 | 红黑树 | B树 | B+树 |
|---|---|---|---|
| 节点容量 | 每个节点存1个键值对 | 每个节点存多个键值对 | 非叶节点存多个键，仅叶节点存值 |
| 分支数 | 二分叉（二叉树） | 多分叉（多路树） | 多分叉，叶节点额外链表连接 |
| 数据存储位置 | 所有节点均存数据 | 所有节点均存数据 | 数据仅存于叶节点 |
| 平衡维护方式 | 颜色标记与旋转 | 节点分裂/合并 | 节点分裂/合并 |
| 查找稳定性 | 查到即返回 | 查到即返回 | 必须查至叶节点 |
堆
堆是一个完全二叉树（即除了最后一层，其他层都满，最后一层从左往右连续填充），其节点满足如下性质：
-
最大堆（Max Heap）：任意节点的值都 ≥ 其子节点（根节点是最大值）
-
最小堆（Min Heap）：任意节点的值都 ≤ 其子节点（根节点是最小值）
LRU（最近最少使用算法）
LRU 是一种缓存淘汰算法，当缓存空间已满时，优先淘汰最长时间未被访问的数据。实现的方式是哈希表+双向链表结合。
具体实现步骤如下：
- 使用哈希表存储数据的键值对，键为缓存的键，值为对应的节点。
- 使用双向链表存储数据节点，链表头部为最近访问的节点，链表尾部为最久未访问的节点。
- 当数据被访问时，如果数据存在于缓存中，则将对应节点移动到链表头部；如果数据不存在于缓存中，则将数据添加到缓存中，同时创建一个新节点并插入到链表头部。
- 当缓存空间已满时，需要淘汰最久未访问的节点，即链表尾部的节点。
