数据结构
数据结构是计算机底层存储、组织数据的方式
是指数据相互之间是以什么方式排列在一起的
数据结构是为了更加方便的管理和使用数据，需要结合具体的业务场景来进行选择
一般情况下，精心选择的数据结构可以带来更高的运行或存储效果
常见的数据结构
- 栈
- 队列
- 数组
- 链表
- 二叉树
- 二叉查找树
- 平衡二叉树
- 红黑树
重点掌握：
- 数据结构的样式
- 如何添加数据
- 如何删除数据
数据结构（栈）
栈的特点：后进先出，先进后出
数据进入栈模型的过程称为：压栈/进栈
数据离开栈模型的过程称为：弹栈/出栈
栈内最后进入的元素（处于顶部的元素）称为栈顶元素
栈内最先进入的元素（处于底部的元素）称为栈底元素
数据结构（队列）
队列的特点：先进先出，后进后出，将数据进入的一端称为后端，数据出去的一端称为前端
数据从后端进入队列模型的过程称为：入队列
数据从前端离开队列模型的过程称为：出队列
数据结构（数组）
- 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同（元素在内存中是连续存储的）
- 删除效率低：要将原始数据删除，同时后面每个数据前移
- 添加效率极低：添加位置后的每个数据后移，再添加元素
数据结构（链表）
链表内的每一个元素都称为结点，每一个结点都是一个对象
结点中，会存储如下内容：
- 存储具体的数据
- 地址值
- 下一个结点的地址（当不存在下一个结点时，地址为空）
链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址
特点：
链表查询慢，无论查询哪个数据都要从头开始找
链表的增删相对快（只需要修改对应结点记录的地址值）
以上就是最基础的单向链表，还有一种链表为双向链表，即结点中存储三个部分：数据、前一个结点的地址、后一个结点的地址
数据结构（树）
示例：
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 TD9((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 TD7((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 TD7((7))7 --> 8((8))8 --> 9((9))9 --> 10((10))10 --> 11((11))
假设要查询数据10，效率太低。此时需要平衡二叉树
示例：
flowchart TD9((9))9 --> 8((8))8 --> 7((7))9 --> 10((10))10 --> 11((11))
旋转机制
规则1：左旋
规则2：右旋
触发时机：当添加一个节点后，该树不再是一棵平衡二叉树
左旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
步骤：
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升原来的右子节点
不平衡二叉树示例1：
flowchart TD7((7))7 --> 4((4))7 --> 10((10))10 --> 11((11))11 --> 12((12))
以上图例，不平衡点为10
将10作为左子节点，再晋升11、12
经过左旋后的平衡二叉树：
flowchart TD7((7))7 --> 4((4))7 --> 11((11))11 --> 10((10))11 --> 12((12))
不平衡二叉树示例2：
flowchart TD7((7))7 --> 4((4))7 --> 10((10))10 --> 11((11))10 --> 9((9))11 --> 12((12))
此时，不平衡点就不再是10，而是根节点7
且左旋的步骤也发生了改变：
- 以不平衡点为支点
- 将根节点的右侧往左拉
- 原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
经过左旋后的平衡二叉树：
flowchart TD10((10))10 --> 7((7))7 --> 4((4))7 --> 9((9))10 --> 11((11))11 --> 12((12))
右旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
步骤：
- 以不平衡的点作为支点
- 把支点右旋降级，变成右子节点
- 晋升原来的左子节点
使用方法和左旋类似
平衡树需要旋转情况
- 左左
- 左右
- 右右
- 右左
左左
当根节点左子树的左子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD7((7))7 --> 4((4))4 --> 2((2))4 --> 5((5))7 --> 10((10))
左左，在根节点左子树的左子树插入节点，导致不平衡二叉树：
flowchart TD7((7))7 --> 4((4))4 --> 2((2))4 --> 5((5))2 --> 1((1))7 --> 10((10))
一次右旋就可以保持平衡：
flowchart TD4((4))4 --> 2((2))4 --> 7((7))7 --> 5((5))7 --> 10((10))2 --> 1((1))
左右
当根节点左子树的右子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD7((7))7 --> 4((4))4 --> 2((2))4 --> 5((5))7 --> 10((10))
左右，在根节点左子树的右子树插入节点，导致不平衡二叉树：
flowchart TD7((7))7 --> 4((4))4 --> 2((2))4 --> 5((5))5 --> 6((6))7 --> 10((10))
先在局部进行左旋，使其成为左左
flowchart TD7((7))7 --> 5((5))5 --> 4((4))5 --> 6((6))4 --> 2((2))7 --> 10((10))
再整体右旋
flowchart TD5((5))5 --> 4((4))4 --> 2((2))5 --> 7((7))7 --> 6((6))7 --> 10((10))
右右
当根节点右子树的右子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD7((7))7 --> 4((4))7 --> 10((10))10 --> 9((9))10 --> 11((11))
右右，在根节点右子树的右子树插入节点，导致不平衡二叉树：
flowchart TD7((7))7 --> 4((4))7 --> 10((10))10 --> 9((9))10 --> 11((11))11 --> 12((12))
一次左旋就可以保持平衡：
flowchart TD10((10))10 --> 7((7))7 --> 4((4))7 --> 9((9))10 --> 11((11))11 --> 12((12))
右左
当根节点右子树的左子树有节点插入，导致二叉树不平衡
节点插入前的平衡二叉树：
flowchart TD7((7))7 --> 4((4))7 --> 10((10))10 --> 9((9))10 --> 11((11))
右左，在根节点右子树的左子树插入节点，导致不平衡二叉树：
flowchart TD7((7))7 --> 4((4))7 --> 10((10))10 --> 9((9))9 --> 8((8))10 --> 11((11))
局部右旋
flowchart TD7((7))7 --> 4((4))7 --> 9((9))9 --> 10((10))9 --> 8((8))10 --> 11((11))
再整体左旋
flowchart TD9((9))9 --> 7((7))7 --> 4((4))7 --> 8((8))9 --> 10((10))10 --> 11((11))
总结
左左和右右只需一次旋转就可以保持平衡，而左右和右左需要进行局部旋转，再整体旋转才能保持平衡
二叉树遍历方式
前序遍历：
从根节点开始，然后按照当前节点，左子节点，右子节点的顺序遍历
示例：
flowchart TD20((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 TD13((13)):::black13 --> 8((8)):::red13 --> 17((17)):::red8 --> 1((1)):::black8 --> 11((11)):::black1 --> Nil1((Nil)):::black1 --> 6((6)):::red11 --> Nil2((Nil)):::black11 --> Nil3((Nil)):::black17 --> 15((15)):::black17 --> 25((25)):::black15 --> Nil4((Nil)):::black15 --> Nil5((Nil)):::black25 --> 22((22)):::red25 --> Nil6((Nil)):::black22 --> Nil7((Nil)):::black22 --> Nil8((Nil)):::black6 --> Nil9((Nil)):::black6 --> Nil10((Nil)):::blackclassDef black fill:#000,color:#fffclassDef red fill:red,color:#fff
节点添加规则
默认颜色：添加节点默认是红色的（效率高）
flowchart LRid1[添加节点]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叶节点进行旋转
红黑树增删改查的性能都很好