数据结构

数据结构是计算机底层存储、组织数据的方式，是指数据相互之间是以什么方式排列在一起的。

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

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

分为栈、队列、数组、链表、树

栈

先进后出、后进先出

数据进入栈模型的过程：压/进栈

数据离开栈模型的过程：弹/出栈

队列

先进先出、后进后出

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

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

数组

查询快、增删慢

链表

查询慢、增删快

链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址

树

二叉树

任意节点的度 ≤ 2

二叉查找树

1. 特点：

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

1. 添加节点

规则：小的存左边，大的存右边，一样的不存

1. 遍历

• 前序遍历：根 → 左 → 右
• 中序遍历：左 → 根 → 右
• 后序遍历：左 → 右 → 根
• 层序遍历：从根节点开始一层一层地遍历

1. 弊端

   可能会退化为链表

平衡二叉树

是二叉查找树的升级版

规则：任意节点左右子树高度差 ≤ 1

如何保持平衡？

旋转机制：

首先要确定支点：从添加的节点开始，不断地往父节点找不平衡的节点

触发时机：当添加一个节点之后，该树不再是一颗平衡二叉树

1. 左旋

• 情况一（右子树无左节点）：以不平衡的点作为支点，把支点左旋降级，变成左子节点，晋升原来的右子节点

• 情况二（右子树有一个左节点）：以不平衡的点作为支点，将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子结点出让，给已经降级的根节点当右子节点

1. 右旋

• 情况一（左子树无右节点）：以不平衡的点作为支点，把支点右旋降级，变成右子节点，晋升原来的左子节点
• 情况二（左子树有一个右节点）：以不平衡的点作为支点，将根节点的左侧往右拉，原先的左子节点变成新的父节点，并把多余的右子结点出让，给已经降级的根节点当左子节点

何时左旋 / 右旋？

1. 左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡

   一次右旋

2. 左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡

   先局部左旋，再整体右旋

   

1. 右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡

   一次左旋

2. 右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡

   先局部右旋，再整体左旋

红黑树

红黑树是一种自平衡的二叉查找树，1972年出现，当时被称为平衡二叉B树

是一种特殊的二叉查找树，每一个节点上都有存储位表示节点的颜色

每一个节点可以使红或者黑；红黑树不是高度平衡的，它的平衡是通过**“红黑规则”**进行实现的

红黑规则：

• 每一个节点或者是红色的，或者是黑色的
• 根节点必须是黑色
• 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每一个叶节点（Nil）是黑色的
• 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
• 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

默认颜色：添加节点默认是红色的（效率高）

添加节点：