数据结构基础小结

概述

什么是算法？

在计算机领域里，算法是一系列程序指令，用于处理特定的运算和逻辑问题。

衡量算法优劣的主要标准是时间复杂度和空间复杂度。

什么是数据结构？

数据结构，对应的英文单词是 data structure，是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

数据结构都有哪些组成方式？

基本数据结构

1. 线性结构

   线性结构是最简单的数据结构，包括数组、链表，以及由它们衍生出来的栈、 队列、哈希表。

2. 树

   树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生出了二叉堆之类的数据结构。

3. 图

   图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。

其他数据结构

除上述所列的几种基本数据结构以外，还有一些其他的千奇百怪的数据结构。它们由基本数据结构变形而来，用于解决某些特定问题，如跳表、哈希链表、位图等

时间复杂度

时间复杂度是对一个算法运行时间长短的量度。它描述了算法运行时间与输入大小之间的关系，记作 T(n)=O(f(n))。

时间复杂度通常用大 O 记号（O表示）来表示，表示算法执行时间的上界。

因为渐进时间复杂度用大写 O 来表示，所以也被称为大 O 表示法。

O(1) < O(logn) < O(n) < O（n²)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大 O 表示法，记作 S(n)=O(f(n))。

线性结构

什么是数组

数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。

• 利用下标查找数组元素的时间复杂度是 O(1)，
• 中间插入、删除数组元素的时间复杂度是 O(n)。

什么是链表

链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。（和数组相反）

• 查找链表节点的时间复杂度是 O(n)，
• 中间插入、删除节点的时间复杂度是 O(1)。

什么是栈

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则（FILO）。

什么是队列

队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作，遵循先入先出的原则（FIFO）。

什么是散列表

散列表也叫哈希表，是存储 Key-Value 映射的集合。对于某一个 Key，散列表可以在接近 O(1) 的时间内进行读写操作。

散列表通过哈希函数实现 Key 和数组下标的转换，通过【开放寻址法】和【链表法】来解决哈希冲突。

1. 开放寻址法：当发生冲突时，它会尝试在哈希表中的其他位置继续寻找可用的位置来存储数据，直到找到一个空闲的位置为止。

   具体来说，开放寻址法通过以下方式处理哈希冲突：

   • 线性探测法：发生冲突时，依次检查下一个位置，直到找到一个空闲位置。
   • 二次探测法：发生冲突时，按照某个固定的二次探测序列依次检查下一个位置，直到找到一个空闲位置。
   • 双重哈希法：使用两个不同的哈希函数来计算下一个探测位置。

   开放寻址法的优点是不需要额外的数据结构来存储冲突的数据，节省了内存空间。但它的缺点是容易产生聚集性冲突，导致哈希表的性能下降。

2. 链表法：它在哈希表的每个桶中维护一个链表（或其他数据结构，如红黑树），当发生冲突时，将冲突的数据存储在该桶的链表中。

   具体来说，链表法通过以下方式处理哈希冲突：

   • 将哈希表的每个桶初始化为一个空链表。
   • 当发生哈希冲突时，将新的数据插入到对应桶的链表中。

   链表法的优点是容易实现，且能够有效地处理较多的哈希冲突。然而，当链表过长时，会影响哈希表的性能，因为查找操作需要在链表上进行线性搜索。

树

什么是树

树是 n 个节点的有限集，有且仅有一个特定的称为根的节点。

当 n>1 时，其余节点可分为 m 个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

什么是二叉树

二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。

二叉树包含【完全二叉树】和【满二叉树】两种特殊形式。

1. 完全二叉树（Complete Binary Tree）：除了最后一层可能不满外，其他层的节点都必须是满的，并且最后一层的节点都尽量靠左排列。

   具体特点如下：

   • 所有叶子节点都集中在二叉树的最后两层。
   • 最后一层的叶子节点都靠左排列。
   • 如果一个节点只有右子树而没有左子树，那么它必定是最后一层的节点。

   完全二叉树在数组中的存储非常高效，因为它的特殊结构允许用数组的形式表示，无需使用额外的指针。

2. 满二叉树（Full Binary Tree）：除了叶子节点外，每个节点都有两个子节点，即每个节点的度数都是 2。

   具体特点如下：

   • 所有非叶子节点都有两个子节点。
   • 所有叶子节点都在同一层上。

   满二叉树的高度是固定的，由节点数决定，且在给定节点数下，它的高度是最小的。但是满二叉树并不常见，一般完全二叉树更为常见。

二叉树的遍历方式有四种，根据遍历节点之间的关系，可以分为以下 4 种方式：

1. 前序遍历（Pre-order Traversal）：先访问根节点，然后按照左子树、右子树的顺序递归遍历。（根左右）
2. 中序遍历（In-order Traversal）：先按照左子树的顺序递归遍历，然后访问根节点，最后按照右子树的顺序递归遍历。（左根右）
3. 后序遍历（Post-order Traversal）：先按照左子树、右子树的顺序递归遍历，然后访问根节点。（左右根）
4. 层序遍历（Level-order Traversal）：从上到下逐层遍历二叉树的节点，同一层节点按照从左到右的顺序访问。（上到下）

另外，从更宏观的角度划分，二叉树的遍历方式可以分为两大类：

1. 深度优先遍历（Depth-First Traversal）：以深度为优先级的遍历方式，即先访问根节点，然后递归遍历左子树和右子树。（根左右）
2. 广度优先遍历（Breadth-First Traversal）：以广度为优先级的遍历方式，即按照层序遍历的顺序逐层遍历二叉树的节点。

深度优先遍历适用于查找、搜索等问题（栈），而广度优先遍历适用于层次遍历和最短路径等问题（队列）。

什么是二叉堆

二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。

• 在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值。
• 在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。

什么是优先队列

优先队列分为最大优先队列和最小优先队列。

• 在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是基于最大堆实现的。
• 在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是基于最小堆实现的

图

什么是图

图是由一组节点（顶点）和连接这些节点的边组成的集合。

节点表示实体，边表示节点之间的关系。

图可以是有向图（Directed Graph），即边有方向性，也可以是无向图（Undirected Graph），边没有方向性。

图的分类

• 简单图：图中没有自环和重复的边。
• 带权图：图的边带有权重，表示节点之间的距离或代价。
• 连通图：任意两个节点之间都有路径连接。
• 有向无环图（DAG）：没有环的有向图，常用于表示任务依赖关系。

图的表示方式

• 邻接矩阵：使用二维数组表示节点之间的连接关系。
• 邻接表：使用链表或数组表示节点的邻居节点。

常见图算法

• 广度优先搜索（BFS）：用于在图中查找最短路径或层次遍历。
• 深度优先搜索（DFS）：用于查找图中的所有路径或判断是否存在环。
• Dijkstra 算法：用于找到带权图中的最短路径。
• Kruskal 算法：用于求最小生成树，适用于带权无向图。
• 拓扑排序：用于有向无环图中的任务调度。

实际应用

• 网络通信：图可用于表示计算机网络中的节点和连接。
• 社交网络：图可用于表示用户之间的关系，进行社交网络分析。
• 路径规划：图可用于地图导航、GPS 定位等。
• 数据库查询优化：用图的拓扑排序来优化数据库查询计划。
• 任务调度：用有向无环图表示任务依赖，实现任务调度和并行处理。

1. BFS - 广度优先搜索（Breadth-First Search）
2. DFS - 深度优先搜索（Depth-First Search）
3. DAG - 有向无环图（Directed Acyclic Graph）
4. GPS - 全球定位系统（Global Positioning System）

红黑树

红黑树是一种自平衡二叉搜索树（通过颜色调整和旋转操作），它在插入和删除节点时能够自动调整结构，保持树的平衡性，从而保证查找、插入和删除操作的时间复杂度稳定在 O(log n)。

红黑树特点：

1. 每个节点都是红色或黑色。
2. 根节点是黑色。
3. 叶子节点（空节点）都是黑色。
4. 红色节点的子节点都是黑色。
   • RED 节点的 parent 都是 BLACK
   • 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
5. 从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点（即相同的黑色高度）。

红黑树的应用：

TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。

为什么要用红黑树？

简单来说红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

布隆过滤器

布隆过滤器（Bloom Filter）是一种空间高效的概率型数据结构，用于快速判断一个元素是否存在于一个集合中。

实际上是一个位数组（通常用二进制位表示），以及一系列哈希函数。

它的主要特点是快速查询、低存储消耗，但可能会产生一定的误判率。

布隆过滤器通常用于以下场景：

1. 缓存加速：在缓存中判断一个数据是否存在，如果不存在，则不需要从数据库或其他存储中加载数据，从而加速数据的查询。
2. 数据库查询优化：可以在数据库查询之前，先通过布隆过滤器快速判断数据是否可能存在，从而减少对数据库的查询负担。
3. 分布式系统：在分布式系统中，可以使用布隆过滤器来快速判断数据是否存在于分布式缓存或分布式数据库中。
4. 防止缓存穿透：当请求的数据在缓存中不存在时，可以使用布隆过滤器先进行判断，如果判断结果为不存在，则可以直接返回，避免对数据库等存储系统的过多查询。

由于误判率的存在，布隆过滤器不适合用于需要绝对精确判断的场景

具体实现步骤如下：

1. 初始化位数组：创建一个位数组，并将所有位初始化为 0。位数组的大小通常根据预期元素数量和期望的误判率来确定。
2. 添加元素：将待添加的元素通过多个哈希函数计算出一系列哈希值，然后将对应位置的位设置为 1。通常会选择多个不同的哈希函数，以增加散列效果。
3. 查询元素：将待查询的元素通过相同的哈希函数计算出一系列哈希值，然后检查对应位置的位。如果所有位置的位都为 1，则表示元素可能存在；如果有任何一位为 0，则表示元素一定不存在。