栈Stack
- 后进先出，先进后出
- 压栈/进栈：数据进入栈模型的过程
- 弹栈/出栈：数据离开栈模型的过程
队列Queue
- 先进先出，后进后出
- 入队列：数据从后端进入队列模型的过程
- 出队列：数据从前端离开队列模型的过程
数组
- ==查询速度快==：查询数据通过地址值和索引定位，查询任意数据耗时相同（元素在内存中是连续存储的）
- ==删除效率低==：要将原始数据删除，同时后面每个数据前移
- ==添加效率低==：添加位置后的每个数据后移，再添加元素
链表
- 链表中的结点是独立的对象，在内存中是不连续的，每个节点包含数据值和下一个结点的地址
- 链表==查询慢==，无论查询哪个数据都从头开始找。
- 链表的==增删快==（对比数组）
树
[父节点地址值，值，左子节点地址值，右子节点地址值]
度：每一个节点的 子节点 数量
树高：树的总层数
10 <-- 根节点
/ \
5 15 <-- 第二层
/ \ \
3 7 20 <-- 第三层
/
6 <-- 第四层
二叉树的遍历方式
前序遍历
- 从根节点开始，按照当前节点，左子节点，右子节点的顺序遍历
中序遍历
- 从最左边的子节点开始，然后按照左子节点，当前节点，右子节点的顺序遍历
后序遍历
- 从最右边的子节点开始，然后按照左子节点，右子节点，当前节点的顺序遍历
层序遍历
- 从根节点开始一层一层遍历
二叉查找树
- 每一个节点上最多有两个子节点
- 任意节点左子树上的值都小于当前节点
- 任意节点右子树上的值都大于当前节点
添加节点
- 小的存左边，大的存右边，一样的不存
弊端
- 左子树全部为空，从形式上看，更像一个==单链表==
- 插入速度没有影响
- 查询速度明显降低
解决弊端：平衡二叉树
平衡二叉树也叫 平衡二叉搜索树（Self-balancing binary search tree），又被称为 AVL 树，可以保证 查询效率较高。它是解决 二叉排序 可能出现的查询问题。
- 二叉查找树
- 规则：==任意节点左右子树高度差不超过1==
保持平衡的旋转机制
- 左旋
- 右旋
- 当添加一个节点时，该树不再是一颗平衡二叉树 -> 旋转
左旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
步骤：
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升 原来的右子节点
 |  |
|---|
- 步骤：
- 以不平衡的点作为支点
- 将根节点的右侧往左拉
- 原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
 |  |
|---|
需要旋转的四种情况
左左LL
- 当==根结点左子树的左子树==有节点插入，导致二叉树不平衡
- 一次右旋
左右LR
- 当==根结点左子树的右子树==有节点插入，导致二叉树不平衡
- 先局部左旋 -> 左左LL
- 再整体右旋
右右RR
- 当==根结点右子树的右子树==有节点插入，导致二叉树不平衡
- 一次左旋
右左RL
- 当==根结点右子树的左子树==有节点插入，导致二叉树不平衡
- 先局部右旋 -> 右右RR
- 再整体左旋
红黑树
- 平衡二叉树的弊端：在添加节点的时候，旋转次数太多，造成添加节点的时间浪费
- 红黑树刚开始被称为平衡二叉B树
- 是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色
- 每一个节点可以是红或者黑；红黑树不是高度平衡的，他的平衡是通过“红黑规则“进行实现的
- 是一个二叉查找树
- ==但是不是高度平衡的==
- 条件：特有的红黑规则
红黑规则
- 每一个节点是红色或黑色
- 根节点必须是黑色的
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil被视为叶节点，每个叶节点 (Nil) 是黑色的
- 如果某一个节点是红色的，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
- 对每一个节点，从该接待你到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
添加节点
- 添加的节点默认是红色的（红色效率高）
- 查找、插入、删除的时间复杂度最坏为O(log n)
