十四、数据结构

一、栈

• 特点：
• 数据进入栈模型的过程称为：
• 数据离开栈模型的过程称为：

二、队列

• 特点：
• 数据进入栈模型的过程称为：
• 数据离开栈模型的过程称为：

三、数组

• 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同（元素在内存中是连续储存的）
• 删除效率低：要将原始数据删除，同时后面的每个数据前移
• 添加效率极低：添加位置后的每个数据后移，再添加元素
• 数组是一种的模型

四、链表

• 链表中的节点是独立的对象，在内存中是不连续的，每个节点包含索引值和下一节点的地址
• 单向链表和双向链表

五、树

• 度：每一个节点的子节点数量
• 树高：树的总层数
• 根节点：最顶层的节点
• 左子节点：左下方的节点
• 右子节点：右下方的节点

六、二叉树

1、前序遍历

20->18->16->19

23->22->24

2、中序遍历

16->18->19->20

22->23->24

3、后序遍历

16->19->18

22->24->23

20

4、层序遍历

20

18->23

16->19->22->24

七、二叉查找树

• 二叉查找树，又称二叉排序树或者二叉搜索树
• 每一个节点上最多有两个子节点
• 任意节点左子树上的值都小于当前节点
• 任意节点右子树上的值都大于当前节点

八、平衡二叉树

规则：任意节点左右子树高度差不超过1

1、旋转机制

（1）左旋

• 情况一

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

• 步骤：

  1. 以不平衡的点作为支点
  2. 把支点左旋降级，变成左子节点
  3. 晋升原来的右子节点

• 情况二

• 确定支点：以添加的节点开始，不断的往父节点找不平衡的节点
• 步骤：
  1. 以不平衡的点作为支点
  2. 将根节点的右侧往左拉
  3. 原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点

（2）右旋

• 情况一

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

• 步骤：

  1. 以不平衡的点作为支点
  2. 把支点右旋降级，变成右子节点
  3. 晋升原来的左子节点

• 情况二

• 确定支点：从添加的节点开始，不断的往父节点找不平衡的节点
• 步骤：
  1. 以不平衡的点作为支点
  2. 将根节点的左侧往右拉
  3. 原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点

2、四种不平衡的情况

（1）左左（一次右旋）

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

旋转前

右旋一次

（2）左右（先局部左旋，再整体右旋）

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

旋转前

局部左旋

整体右旋

（3）右右（一次左旋）

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

旋转前

左旋一次

（4）右左（先局部右旋，再整体左旋）

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

旋转前

局部右旋

整体左旋

九、红黑树

• 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
• 1972年出现，当时称之为平衡二叉B树。后来1978年被修改为如今的“红黑树”
• 它是一种特殊的二叉查找树，红黑树每一个节点上都存储位表示节点的颜色
• 每一个节点可以是红或者黑，红黑树不是高度平衡的，它的平衡你是通过“红黑规则”进行实现的

1、与平衡二叉树区别

平衡二叉树

• 高度平衡
• 当左右子树高度差超过1时，通过旋转保持平衡

红黑树

• 是一个二叉查找树
• 但是高度不是平衡的
• 条件：

2、红黑规则

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

3、添加规则

默认颜色：添加节点默认是红色的