# 数据结构
# 栈
先进后出，后进先出
一端开口 栈顶；一端封闭 栈底
# 队列
先进先出，后进后出
一端开口 后端；一端开头 前端
# 数组
- 在内存中一块在一起的元素，是一种查询快、增删慢的数据模型
- 查询速度快：通过地址值和索引定位，查询任意数据时间复杂度相同
- 删除效率低：将一个数据删除后，后面的每个数据都需要前移
- 添加（插入）效率极地：添加位置后每个数据后移，再添加元素
# 链表
在内存中是分散的
每个存储单位是一个节点，是一个单独的对象
- 节点有自己的地址
- 头节点存储第一个节点的地址（单向链表）或者存储第一个节点的地址和最后一个节点的地址（双向链表）
- 单向链表中节点中存储具体数据和下一个节点的地址
- 双向链表中节点中存储前一个节点的地址、具体数据、下一个节点的地址
链表增删较快、查询慢、首尾操作极快
# 二叉树
树形数据结构
度：每个节点的子节点数量
树高：树的总层数
根节点：最顶层的节点
左子节点：左下方的节点；右子节点：右下方的节点
根节点的左子树
二叉树中，任意节点的度<= 2
每个节点有一个父节点，一个左子节点，一个右子节点
节点的结构
# 二叉查找树
- 每个节点上最多有两个子节点
- 任意节点左子树上的值都小于当前节点
- 任意节点右子树上的值都大于当前节点
# 存储规则
- 小的存左边
- 大的存右边
- 一样的不存
# 二叉树遍历
# 前序遍历
从根节点开始，然后按照当前节点，左子节点，右子节点的顺序遍历
# 中序遍历（常用）
从最左边的子节点开始，然后按照左子节点，当前节点，右子节点的顺序遍历。
遍历出来的数据（二叉查找树）是从大到小排序的，因此最常用
# 后序遍历
从最左边的子节点开始，然后按照左子节点，右子节点，当前节点的顺序遍历
# 层序遍历
从根节点开始一层一层的遍历
# 平衡二叉树
***任意节点***左右子树高度差不超过1
# 左旋
- 确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
# 支点非根节点
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升原来的右子节点
# 支点为根节点
- 以不平衡的点作为支点
- 将根节点的右侧往左拉
- 原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
# 右旋
与左旋同理
# 需要旋转的四种情况
- 左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡
- 一次右旋即可
- 左右：当根节点左子树的右子树右节点插入，导致二叉树不平衡
- 先局部左旋，在整体右旋
- 右右：当根节点右子树的右子树右节点插入，导致二叉树不平衡
- 一次左转即可
- 右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡
- 先局部右旋，在整体左旋
# 红黑树
- 是一个二叉查找树
- 但不是高度平衡的
- 条件：特有的红黑规则
# 红黑规则
- 每个节点或是红色，或是黑色
- 根节点必须是黑色
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil,这些Nil视为叶结点，每个叶结点（Nil）是黑色的
- 如果一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
- 对每一个即诶的那，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色节点
# 添加规则
- 默认颜色：添加节点的默认颜色是红色
