1.1 数据结构

1.数据结构概述

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

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

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

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

2.栈

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

​ 数据进入到栈模型中叫：压栈/进栈

​ 数据离开到栈模型中叫：弹栈/出栈

image-20221210163543807

3.队列

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

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

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

image-20221210164304062

4.数组

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

  • 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同。（元素在内存中是连续存储的）
  • 删除效率低：要将原始数据删除，同时后面每个数据前移。
  • 添加效率极低：添加位置后的每个数据后移，再添加元素

image-20221210165235563

5.链表

​ 链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址。
​ 链表查询慢，无论查询哪个数据都要从头开始找。

​ 链表增删快

image-20221210165852839

image-20221210170548621

6.树

image-20221210172134798

6.1 二叉查找树

​ 二叉查找树，又称二叉排序树或者二叉搜索树。

特点：

  • 每一个节点上最多有两个子节点
  • 任意节点左子树上的值都小于当前节点
  • 岁任意节点右子树上的值都大于当前节点

image-20221210172634439

image-20221210172917347

二叉树遍历方式

  1. 前序遍历
    • 从根结点开始，然后按照当前结点，左子结点，右子结点的顺序遍历
  2. 中序遍历
    • 从最左边的子节点开始，然后按照左子结点，当前结点，右子结点的顺序遍历
  3. 后序遍历
    • 从最左边的子节点开始，然后按照左子结点，右子结点，当前结点的顺序遍历
  4. 层序遍历
    • 从根节点开始一层一层的遍历
6.3 平衡二叉树(左旋)

​ 任意节点左右节点树高度不超过1

  • 确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
  • 以不平衡的点作为支点
  • 把支点左旋降级，变成左子节点
  • 晋升原来的右子节点

image-20221211104451268

6.3 平衡二叉树(右旋)
  • 确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
  • 以不平衡的点作为支点
  • 把支点右旋降级，变成右子节点
  • 引晋升原来的左子节点

image-20221211105618418

image-20221211105800905

7.红黑树

  • 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。
  • 1972年出现，当时被称之为平衡二叉B树。后来，1978年被修改为如今的”红黑树”。
  • 它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，
  • 每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过”红黑规则”进行实现的

image-20221212100901253

7.1红黑规则

① 每一个节点或是红色的，或者是黑色的

② 根节点必须是黑色

③如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的

④ 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)

③ 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点;

image-20221212101423432