【JAVA入门】Day28 - 数据结构

【JAVA入门】Day28 - 数据结构

        常见的数据结构我们讲八种：

• ① 栈
• ② 队列
• ③ 数组
• ④ 链表
• ⑤ 二叉树
• ⑥ 二叉查找树
• ⑦ 平衡二叉树
• ⑧ 红黑树

        围绕三个问题，我们可以轻易学习：

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 提供了很多独有方法，用于链表操作。

五、二叉树

        二叉树是一种全新的数据结构。

        从根节点，向两边延伸出子节点，一个左子节点，一个右子节点，生生不息，延绵不绝。
        在 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 红黑树添加节点的规则

• 默认颜色：添加的节点默认是红色的，因为红色节点添加效率高。使用红色节点造树，添加三个节点才需要调整一次这棵树。
• 调整的规则如下图：
  

        红黑树的增删改查，效率都是极高的。