本文主要是介绍【JAVA入门】Day28 - 数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【JAVA入门】Day28 - 数据结构
文章目录
- 【JAVA入门】Day28 - 数据结构
- 一、栈
- 二、队列
- 三、数组
- 3.1 ArrayList
- 四、链表
- 4.1 LinkedList
- 五、二叉树
- 5.1 二叉查找树
- 5.2 二叉树的遍历方式
- 5.3 平衡二叉树
- 5.4 平衡二叉树的旋转
- 5.5 平衡二叉树需要旋转的几种情况
- 六、红黑树
- 6.1 红黑规则
- 6.2 红黑树添加节点的规则
数据结构就是计算机存储、组织数据的方式。它是指数据相互之间以何种方式排列在一起。数据结构是为了更加方便地管理和使用数据，需要结合具体的业务场景来进行选择。精心选择的数据结构可以给业务带来更高的运行或存储效率。
常见的数据结构我们讲八种：
- ① 栈
- ② 队列
- ③ 数组
- ④ 链表
- ⑤ 二叉树
- ⑥ 二叉查找树
- ⑦ 平衡二叉树
- ⑧ 红黑树
围绕三个问题，我们可以轻易学习：
1.每种数据结构长什么样子？
2.如何添加数据？
3.如何删除数据？
学好数据结构是计算机进修的一大基础，下面我们从第一种开始讲起。
一、栈
栈的特点：后进先出，先进后出。
数据进入栈模型的过程称为：压 / 进栈。
我们以 A B C D 的顺序压栈，得到的结果如下图所示。
此时的栈顶元素为 D，栈底元素为 A。
数据离开栈模型的过程称为：弹 / 出栈。
此时栈顶元素先出栈，所以只能按照 D C B A 的顺序依次出栈。
在 Java 的内存结构当中，有一块区域被称为栈内存，也是利用了栈的原理。
二、队列
队列的特点是：先进先出，后进后出。
A B C D 按顺序进入队列，会先从后端（队尾）依次进入，我们称之为入队列。随后，会按 A B C D 的顺序从前端（队头）依次出去，我们称之为出队列。
三、数组
数组也是一种数据结构，相关操作我们讲了很多了，不需要多讲。
我们只需要知道，查询数据时，是通过数组的地址值和索引直接定位的，查询任意数据耗时相同（因为元素在内存中是连续存储的）。
数组的删除效率是非常低的，删除一个数据之后，要同时把后面每一个数据都前移。
数组的添加效率也是非常低的，除非你在数组 0 索引前或最后索引后添加，否则中间插入元素需要把添加位置后的每个数据都往后移动，再插入元素。
由此可见，数组是一种查询快，增删慢的数据模型。
3.1 ArrayList
之前讲的 ArrayList 底层就是数组集合。
四、链表
链表与数组刚好相反，它是一种查询慢，增删快的数据模型。
链表中的每一个元素，我们有专业的名词来描述：结点（Node）。每一个结点都是一个独立的对象，它会有自身的存储位置（地址值），在结点内部，它还会存储具体的数据，同时也存储下一个结点的地址值。
在链表中，第一个创建出来的结点，我们称为头结点，头结点里有自己的地址值，然后下一个结点地址值暂时记录为空。
此时如果要添加一个数据A，我们就要新开辟一个新空间，存储数据A，然后将下一个结点地址值记录为空。
然后我们只需要把前一个结点的“指向下一个结点地址值”的数据修改为新结点的地址值，即可完成两个结点之间的链接。
从而我们可以创建一条完整的链表，内部的每一个结点都是一个独立的对象，在内存中是不连续的。
因此，链表在查询时，无论查询哪个数据，都要从头结点开始找。
但是，链表的增删是非常快的，每次增删不需要移动元素。当插入新结点时，只需要令上一个结点指向它，它的下一个结点指向原来的下一个结点，即可完成插入；删除也是一样的道理只需要断链把结点孤立出来，再清除它的内存空间即可。
而且，链表还有双向的改进链表等，通过加入“上一个结点”的地址值，可以提高查找效率。
4.1 LinkedList
LinkedList 在底层其实就是一个双向链表，它的特点是查询慢，增删快，但是如果操作的是首位元素，速度也是极快的。Java 给 LinkedList API 提供了很多独有方法，用于链表操作。
| 特有方法 | 说明 |
|---|---|
| public void addFirst(E e) | 在该列表开头插入指定的元素 |
| public void addLast(E e) | 将指定的元素追加到此列表的末尾 |
| public E getFirst() | 返回此列表中的第一个元素 |
| public E getLast() | 返回此列表中的最后一个元素 |
| public E removeFirst() | 从此列表中删除并返回第一个元素 |
| public E removeLast() | 从此列表中删除并返回最后一个元素 |
五、二叉树
二叉树是一种全新的数据结构。
从根节点，向两边延伸出子节点，一个左子节点，一个右子节点，生生不息，延绵不绝。
在 Java 中，实际上每个节点都是一个单独的对象，其内部存储着自身的值，还存储着父节点地址值、左子节点地址值、右子节点地址值，如果没有左右子节点，地址值就为空。
在树的数据结构中，有一些专有名词需要认识。
- 度：每一个节点的子节点数量。在二叉树中，任意节点的度<=2。
- 树的高度：一棵树的总层数叫做树的高度。
- 根节点：最顶层的节点。
- 左子节点：一个节点左下方的孩子节点。
- 右子节点：一个节点右下方的孩子节点。
- 根节点的左子树：如图所示。
- 根节点的右子树：如图所示。
- 其他节点的左右子树：如图所示。
5.1 二叉查找树
如果一棵树的每一个节点都满足以下规律：它的左子节点的存储的数据比自己小，它的右子节点存储的数据比自己大，我们就把这棵树称为二叉查找树，又叫二叉排序树或二叉搜索树。
二叉查找树在添加节点时一定要遵从以下规则：
1.小的存左边
2.大的存右边
3.一样的不存
在查找时，从根节点开始，依次比较，如果比它小，看左边；比它大，看右边，依次摸索，直到找到或找不到。
5.2 二叉树的遍历方式
二叉树有四种遍历方式：
①前序遍历
②中序遍历
③后序遍历
④层序遍历
前序遍历：从根节点开始，按照当前节点，左子节点，右子节点的顺序遍历。
中序遍历：从根节点开始，按照左子节点，当前节点，右子节点的顺序遍历。
※按照中序遍历的二叉排序树，其获取的数据是从小到大排列的。
后序遍历：从根节点开始，按照左子节点，右子节点，当前节点的顺序遍历。
层序遍历：从根节点开始，一层一层地遍历。
5.3 平衡二叉树
如果严格按照二叉查找树的创建方式，可能会出现这种严重倾斜的情况，这样严重影响了查找的效率。一棵二叉树如果想要提高查找效率，那它的左右分支就应该差不多大，因此，我们需要引入平衡二叉树的概念。
平衡二叉树是在二叉查找树的基础上，又加入了以下规则：任意节点左右子树的高度差不超过1。
5.4 平衡二叉树的旋转
- 平衡二叉树的左旋
平衡二叉树在旋转时，要先确定支点，从添加的节点开始，不断地往父节点找不平衡的节点。
所谓不平衡节点，就是左子树和右子树节点差值超过2的节点，可以轻易地发现图中是 10 节点，而 10 节点的左子树小于右子树，所以要进行左旋。
这种简单左旋，旋转方式如下。
稍微复杂一点的左旋，如下图所示：
确认不平衡支点为 7 节点，左旋后如下：
- 平衡二叉树的右旋
平衡二叉树右旋，简单情况如下：
稍微复杂一点的情况，如下：
5.5 平衡二叉树需要旋转的几种情况
- 左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡时。
或
此时进行右旋即可。
- 左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡时。
此时应该先对子树进行一次左旋，把情况变成左左，再进行整体的右旋。
- 右右：当根节点的右子树的右子树有节点插入，导致二叉树不平衡时。
此时直接整体左旋即可。
- 右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡时。
应该先把局部位置进行右旋。
此时变为右右，整体左旋即可。
六、红黑树
红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。
红黑树自1972年出现，曾被命名为平衡二叉B树，后于1978年被修改命名为红黑树。
红黑树是一种特殊的二叉查找树，它的每一个节点上都有存储位表示节点的颜色。
红黑树的每一个节点可以是红或者黑，红黑树不是高度平衡的，它的平衡是通过红黑规则进行实现的。
6.1 红黑规则
① 每一个节点或者是红色，或者是黑色。
② 根节点必须是黑色。
③ 如果一个节点没有子节点或者父节点，则该节点相应指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的。
④ 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）。
⑤ 对每一个节点而言，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
如果一个节点没有左子节点，也没有右子节点，那么都记为Nil。
然后会在它的两侧生成两个空节点，也就是叶子节点，其内部没有任何数据。
6.2 红黑树添加节点的规则
- 默认颜色：添加的节点默认是红色的，因为红色节点添加效率高。使用红色节点造树，添加三个节点才需要调整一次这棵树。
- 调整的规则如下图：
红黑树的增删改查，效率都是极高的。
这篇关于【JAVA入门】Day28 - 数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
