数据结构
数据结构
数据结构是计算机底层存储、组织数据的方式
是指数据相互之间是以什么方式排列在一起的
数据结构是为了更加方便的管理和使用数据，需要结合具体的业务场景来进行选择
一般情况下，精心选择的数据结构可以带来更高的运行或存储效果
常见的数据结构
- 栈
- 队列
- 数组
- 链表
- 二叉树
- 二叉查找树
- 平衡二叉树
- 红黑树
重点掌握：
- 数据结构的样式
- 如何添加数据
- 如何删除数据
数据结构（栈）
栈的特点：后进先出，先进后出
数据进入栈模型的过程称为：压栈/进栈
数据离开栈模型的过程称为：弹栈/出栈
栈内最后进入的元素（处于顶部的元素）称为栈顶元素
栈内最先进入的元素（处于底部的元素）称为栈底元素
数据结构（队列）
队列的特点：先进先出，后进后出，将数据进入的一端称为后端，数据出去的一端称为前端
数据从后端进入队列模型的过程称为：入队列
数据从前端离开队列模型的过程称为：出队列
数据结构（数组）
- 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同（元素在内存中是连续存储的）
- 删除效率低：要将原始数据删除，同时后面每个数据前移
- 添加效率极低：添加位置后的每个数据后移，再添加元素
数据结构（链表）
链表内的每一个元素都称为结点，每一个结点都是一个对象
结点中，会存储如下内容：
- 存储具体的数据
- 地址值
- 下一个结点的地址（当不存在下一个结点时，地址为空）
链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址
特点：
链表查询慢，无论查询哪个数据都要从头开始找
链表的增删相对快（只需要修改对应结点记录的地址值）
以上就是最基础的单向链表，还有一种链表为双向链表，即结点中存储三个部分：数据、前一个结点的地址、后一个结点的地址
数据结构（树）
示例：
flowchart TD
A((22))
A --> B((18))
A --> C((26))
B --> D((16))
B --> E((20))
D --> F((15))
D --> G((17))
E --> N((19))
E --> O((21))
C --> H((24))
C --> I((28))
H --> J((23))
H --> K((25))
I --> L((27))
I --> M((29))
其中，16可以看作是15、17的父节点，15是16的左子节点，17是16的右子节点
每一个结点都会存储四个值，分别是：
- 数据
- 父节点地址
- 左子节点地址
- 右子节点地址
若是没有父节点地址、子节点地址，记为null
度：每一个节点的子节点数量
树高：树的总层数（示例中，树的高度为4）
根节点：最顶层的结点（示例中，树的根为22）
左子节点：左下方的节点
右子节点：右下方的结点
根节点的左子树：就是根节点的左子节点以及子子节点（示例中，左子树为18、16、20、15、17、19、12）
根节点的右子树：就是根节点的右子节点以及子子节点（示例中，左子树为26、24、28、23、25、27、29）
数据结构（二叉树）
二叉树中，任意节点的度<=2
普通的二叉树
flowchart TD
9((9))
9 --> 7((7))
9 --> R((2))
R --> D((1))
D --> 10((10))
7 --> 3((3))
7 --> 8((8))
3 --> 4((4))
3 --> 6((6))
8 --> 5((5))
排列没有规则
数据结构（二叉查找树）
二叉查找树，又称二叉排序树或者二叉搜索树
特点：
- 每个节点上最多有两个子节点
- 任意节点左子树上的值都小于当前节点
- 任意节点右子树上的值都大于当前节点
flowchart TD 7((7)) 7 --> 4((4)) 4 --> 2((2)) 4 --> 5((5)) 5 --> 6((6)) 2 --> 1((1)) 2 --> 3((3)) 7 --> 10((10)) 10 --> 11((11)) 11 --> 12((12))
规则：小的存左边，大的存右边，一样的不存
数据结构（平衡二叉树）
规则：任意节点左右子树高度差不超过1
示例：
flowchart TD 7((7)) 7 --> 8((8)) 8 --> 9((9)) 9 --> 10((10)) 10 --> 11((11))
假设要查询数据10，效率太低。此时需要平衡二叉树
示例：
flowchart TD 9((9)) 9 --> 8((8)) 8 --> 7((7)) 9 --> 10((10)) 10 --> 11((11))
旋转机制
规则1：左旋
规则2：右旋
触发时机：当添加一个节点后，该树不再是一棵平衡二叉树
左旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
步骤：
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升原来的右子节点
不平衡二叉树示例1：
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 10((10)) 10 --> 11((11)) 11 --> 12((12))
以上图例，不平衡点为10
将10作为左子节点，再晋升11、12
经过左旋后的平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 11((11)) 11 --> 10((10)) 11 --> 12((12))
不平衡二叉树示例2：
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 10((10)) 10 --> 11((11)) 10 --> 9((9)) 11 --> 12((12))
此时，不平衡点就不再是10，而是根节点7
且左旋的步骤也发生了改变：
- 以不平衡点为支点
- 将根节点的右侧往左拉
- 原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
经过左旋后的平衡二叉树：
flowchart TD 10((10)) 10 --> 7((7)) 7 --> 4((4)) 7 --> 9((9)) 10 --> 11((11)) 11 --> 12((12))
右旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
步骤：
- 以不平衡的点作为支点
- 把支点右旋降级，变成右子节点
- 晋升原来的左子节点
使用方法和左旋类似
平衡树需要旋转情况
- 左左
- 左右
- 右右
- 右左
左左
当根节点左子树的左子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 4 --> 2((2)) 4 --> 5((5)) 7 --> 10((10))
左左，在根节点左子树的左子树插入节点，导致不平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 4 --> 2((2)) 4 --> 5((5)) 2 --> 1((1)) 7 --> 10((10))
一次右旋就可以保持平衡：
flowchart TD 4((4)) 4 --> 2((2)) 4 --> 7((7)) 7 --> 5((5)) 7 --> 10((10)) 2 --> 1((1))
左右
当根节点左子树的右子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 4 --> 2((2)) 4 --> 5((5)) 7 --> 10((10))
左右，在根节点左子树的右子树插入节点，导致不平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 4 --> 2((2)) 4 --> 5((5)) 5 --> 6((6)) 7 --> 10((10))
先在局部进行左旋，使其成为左左
flowchart TD 7((7)) 7 --> 5((5)) 5 --> 4((4)) 5 --> 6((6)) 4 --> 2((2)) 7 --> 10((10))
再整体右旋
flowchart TD 5((5)) 5 --> 4((4)) 4 --> 2((2)) 5 --> 7((7)) 7 --> 6((6)) 7 --> 10((10))
右右
当根节点右子树的右子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 10((10)) 10 --> 9((9)) 10 --> 11((11))
右右，在根节点右子树的右子树插入节点，导致不平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 10((10)) 10 --> 9((9)) 10 --> 11((11)) 11 --> 12((12))
一次左旋就可以保持平衡：
flowchart TD 10((10)) 10 --> 7((7)) 7 --> 4((4)) 7 --> 9((9)) 10 --> 11((11)) 11 --> 12((12))
右左
当根节点右子树的左子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 10((10)) 10 --> 9((9)) 10 --> 11((11))
右左，在根节点右子树的左子树插入节点，导致不平衡二叉树：
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 10((10)) 10 --> 9((9)) 9 --> 8((8)) 10 --> 11((11))
局部右旋
flowchart TD 7((7)) 7 --> 4((4)) 7 --> 9((9)) 9 --> 10((10)) 9 --> 8((8)) 10 --> 11((11))
再整体左旋
flowchart TD 9((9)) 9 --> 7((7)) 7 --> 4((4)) 7 --> 8((8)) 9 --> 10((10)) 10 --> 11((11))
总结
左左和右右只需一次旋转就可以保持平衡，而左右和右左需要进行局部旋转，再整体旋转才能保持平衡
二叉树遍历方式
前序遍历：
从根节点开始，然后按照当前节点，左子节点，右子节点的顺序遍历
示例：
flowchart TD 20((20)) 20 --> 18((18)) 18 --> 16((16)) 18 --> 19((19)) 20 --> 23((23)) 23 --> 22((22)) 23 --> 24((24))
遍历获取元素顺序为：20 ➡ 18 ➡ 16 ➡ 19 ➡ 23 ➡ 22 ➡ 24
中序遍历：
从最左边的子节点开始，然后按照左子节点，当前节点，右子节点的顺序遍历
遍历获取元素顺序为：16 ➡ 18 ➡ 19 ➡ 20 ➡ 22 ➡ 23 ➡ 24
后序遍历：
从最左边的子节点开始，然后按照左子节点，右子节点，当前节点的顺序遍历
遍历获取元素顺序为：16 ➡ 19 ➡ 18 ➡ 22 ➡ 24 ➡ 23 ➡ 20
层序遍历：
从根节点开始，一层一层的遍历
遍历获取元素顺序为：20 ➡ 18 ➡ 23 ➡ 16 ➡ 19 ➡ 22 ➡ 24
总结：
- 前序遍历：当前节点，左子节点，右子节点
- 中序遍历：左子节点，当前节点，右子节点
- 后序遍历：左子节点，右子节点，当前节点
- 层序遍历：一层一层的去遍历
二叉树的演变
二叉树 ➡ 二叉查找树 ➡ 平衡二叉树
查找效率：从左往右，从小到大
数据结构（红黑树）
- 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
- 1972年出现，当时被称为平衡二叉B树。直到1978年，被正式修改为如今的
红黑树 - 它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示
节点的颜色 - 每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过
红黑规则进行实现的
红黑规则
- 每一个节点或是黑色的，或者是红色的
- 根节点必须是黑色
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点是黑色的
- 如果某个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
示例：
flowchart TD 13((13)):::black 13 --> 8((8)):::red 13 --> 17((17)):::red 8 --> 1((1)):::black 8 --> 11((11)):::black 1 --> Nil1((Nil)):::black 1 --> 6((6)):::red 11 --> Nil2((Nil)):::black 11 --> Nil3((Nil)):::black 17 --> 15((15)):::black 17 --> 25((25)):::black 15 --> Nil4((Nil)):::black 15 --> Nil5((Nil)):::black 25 --> 22((22)):::red 25 --> Nil6((Nil)):::black 22 --> Nil7((Nil)):::black 22 --> Nil8((Nil)):::black 6 --> Nil9((Nil)):::black 6 --> Nil10((Nil)):::black classDef black fill:#000,color:#fff classDef red fill:red,color:#fff
节点添加规则
默认颜色：添加节点默认是红色的（效率高）
flowchart LR id1[添加节点] id1 --> id2[根] id2 --> id3[直接变成黑色] id1 --> id4[非根] id4 --> id5[父黑色] id5 --> id6[则不需要任何操作] id4 --> id7[父红色] id7 --> id8[叔叔红色] id8 --> id9["将父设为黑色,将叔叔设为黑色"] id8 --> id10["将祖父设为红色"] id8 --> id11["如果祖父为根，再将根变回黑色"] id8 --> id12["如果祖父为非根，将祖父设置为当前节点再进行其他判断"] id7 --> id13["叔叔黑色，当前节点是父的右孩子"] id13 --> id14["把父作为当前节点并左旋，再进行判断"] id7 --> id15["叔叔黑色，当前节点是父的左孩子"] id15 --> id16["将父设为黑色"] id15 --> id17["将祖父变为红色"] id15 --> id18["以祖父为支点进行右旋"]
红黑树旋转时，不需要将Nil叶节点进行旋转
红黑树增删改查的性能都很好