数据结构极速版（更快了解java集合框架）

数据结构概述

数据结构是计算机底层存储、组织数据的方式

指数据相互之间是以什么方式排列在一起的

数据结构是为了更加方便的管理和使用数据，需要结合具体的业务场景来进行选择

一般情况下，精心选择的数据结构可以带来更高的运行或者存储效率

常见的数据结构

1.栈

栈的特点：后进先出，先进后出

数据进入栈模型的过程称为：压/进栈

数据离开栈模型的过程称为：弹/出栈

2.队列

队列的特点：先进先出，后进后出

数据从后端进入队列模型的过程称为：入队列

数据从前端离开队列模型的过程称为：出队列

3.数组

数组的特点

查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同（元素在内存中是连续存储的）

删除效率低：要将原始数据删除，同时后面每个数据前移

添加效率极低：添加位置后的每个据节点s后移，再添加元素

数据是一种查询快，增删慢的数据模型

4.链表

链表中的节点是独立的对象，在内存中是不连续的，每个节点包含数据值和下一个节点的地址

链表查询慢，无论查询哪个数据都要从头开始找

链表增删相对快

增加：

删除：

5.二叉树

二叉树是一种树结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。这些子节点不一定是排序的或者有特定的关系。

• 每个节点最多有两个子节点：左子节点和右子节点。
• 子节点的顺序不一定有特定规则。
• 在某些情况下，可能会退化为链表，导致操作的时间复杂度增加。

6.二叉查找树

二叉查找树是一种二叉树，其中每个节点的值大于其左子树中的任何节点的值，小于其右子树中的任何节点的值。这使得在BST中进行搜索、插入和删除操作的平均时间复杂度为O(log n)。

• 每个节点的值大于其左子树中的任何节点的值，小于其右子树中的任何节点的值。
• 这种排序特性使得查找、插入和删除的平均时间复杂度为O(log n)。
• 如果树退化为链表，时间复杂度可能变为O(n)。

7.平衡二叉树

平衡二叉树是一种特殊的二叉查找树，它的左右子树的高度差不超过1。平衡二叉树的目的是确保在最坏情况下的搜索、插入和删除操作的时间复杂度仍然是O(log n)。

• 每个节点的左右子树的高度差不超过1。
• 保持平衡性有助于确保树的高度较小，从而保证了查找、插入和删除操作的时间复杂度稳定在O(log n)。
• 平衡因子的维护可能导致在插入和删除操作时需要进行树的旋转操作，以保持平衡。

8.红黑树

也是一种特殊的二叉查找树，它通过在普通的二叉查找树上增加一些额外的规则和操作来确保树的平衡。红黑树是一种自平衡二叉查找树，它保证了在最坏情况下的时间复杂度为O(log n)。

• 是一种自平衡的二叉查找树。
• 红黑树通过对节点着色和应用一些特定规则来保持平衡。
• 它的平衡性质保证了在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。
• 红黑树相对于平衡二叉树来说，旋转操作更少，因为其自平衡的特性更强，所以在实际应用中更为常见。