常见的数据结构
- 数据结构概述、栈、队列
- 数组
- 链表
- 二叉树、二叉查找树
- 平衡二叉树
- 红黑树
数据结构概述：
- 数据结构是计算机底层存储、组织数据的方式。是指数据相互之间以什么方式排列在一起的。
- 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率
1、栈
- 先进后出，后进先出
- 数据进入栈模型的过程称为：压/进栈
- 数据离开栈模型的过程称为：弹/出栈
2、队列
- 先进先出，后进后出
- 数据从前端进入队列模型的过程称为：入队列
- 数据前端离开队列模型的过程称为：出队列
3、链表的特点
- 链表中的元素是游离存储的，每个元素节点包含数据值和下一个元素的地址
- 链表查询慢。无论查询哪一个元素都需要从头开始查找
- 链表增删相对快
链表的分类
4、二叉树
二叉树概述
二叉树特点
- 只能有一个根节点，每个节点最多支持2个直接子节点
- **节点的度：**节点拥有的子树的个数，二叉树的度不大于2，叶子节点的度为0，也称之为终端节点
- **高度：**叶子节点的高度为1，叶子节点的父节点高度为2，以此类推，根节点的高度最高
- 层：根节点在第一层，以此类推
- **兄弟节点：**拥有共同父节点的节点互称兄弟节点
二叉查找树又称二叉排序树或者二叉搜索树
特点：
- 每一个节点上最多又两个子节点
- 左子树上所有节点的值都小于根节点的值
- 右子树上所有的节点的值都大于根节点的值
5、平衡二叉树
二叉树查找存在的问题
将上面的节点按照二叉查找树的规则存入
**问题：**出现瘸子现象，导致查询的性能与单链表一样，查询速度变慢
平衡二叉树是在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高数据的性能
平衡二叉树的要求
- 任意节点的左右两个子树的高度差不超过1，任意节点的左右两个子树都是一颗平衡二叉树
识别如下是否是平衡二叉树
平衡二叉树在添加元素后可能导致不平衡
- 基本策略是进行左旋，或者右旋保证平衡。
平衡二叉树-旋转的四种情况
- 左左
- 左右
- 右右
- 右左
平衡二叉树-左左
- ? 左左
- 当根节点左子树的左子树有节点插入，导致二叉树不平衡
- 当根节点左子树的左子树有节点插入，导致二叉树不平衡
平衡二叉树-左右
- ? 左右
- 当根节点左子树的右子树有节点插入，导致二叉树不平衡
6、红黑树
红黑树概述
- 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
- 1972年出现，当时被称之为平衡二叉B树。1978年被修改为如今的“红黑树”
- 每一个节点可以是红或者黑；红黑树不是通过高度平衡的，它的平衡是通过“红黑规则”进行实现的。
红黑规则
-
每一个节点或是红色的，或者是黑色的，根节点必须是黑色。每一个节点或是红色的，或者是黑色的，根节点必须是黑色.
-
如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，叶节点是黑色的。、
-
如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
-
对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
添加节点
- 添加节点的颜色，可以是红色，也可以是黑色
- 默认用红色效率高
红黑树小结
规则如下：
- 每一个节点或是红色，或者是黑色的，根节点必须是黑色
- 如果一个节点没有子节点或者父节点，则该节点的指针属性为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的；
- 如果某一个节点是红色的，那么它的子节点必须是黑色的（不能出现两个红色节点相连的情况）
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
红黑树增删改查的性能都很好