数据结构
数据结构
数据结构式计算机存储、组织数据的方式。
是指数据相互之间是以什么方式排列在一起的。
数据结构是为了更加方便管理和使用数据，需要结合具体的业务场景来进行选择
主要通过以下三个方面去理解
- 每种数据结构长什么样子
- 如何添加数据
- 如何删除数据
常见的数据结构
栈
栈的特点：后进先出，先进后出
- 数据进入栈模型的过程称为：压/进栈
队列
队列的特点：先进先出，后进后出
- 数据从后端进入队列模型的过程称为：入队列
- 数据从前端离开队列模型的过程称为：出队列
数组
数组是一种查询块，增删慢的数据模型
查询速度快
查询数据通过地址值和索引定位，查询任意数据耗时相同。（元素在内存中是连续存储的）
删除效率低
要将元素数据删除，同时后面每个数据前移
添加效率极低
添加位置后的每个数据后移，在添加元素
链表
链表中的每一个元素，我们会称之为结点，每一个结点都是一个对象，这个对象都会有一个独立的地址值表示结点在内存中的位置，在结点里面会存储具体的数据和下一个结点的地址。
链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址
查询速度慢
无论查询哪个数据都要从头开始找。
增删相对快
在插入数据的时候，只需要修改对应结点的地址值即可
首尾操作极快
当查询第N个元素的时候，双向链表比单向链表查询速度更快，因为会根据第几个元素，决定是从头部还是尾部开始查找
二叉树
二叉树的弊端：普通的二叉树是没有顺序的，没有任何意义
节点的内部结构
- 父节点地址
- 值
- 左子节点地址
- 右子节点地址
度：每一个节点的子节点数量
规则：二叉树中，任意节点的度<=2
二叉查找树
二叉查找树，又称二叉排序树或者二叉搜索树
特点
- 每一个节点上最多有两个子节点
- 任意节点左子树上的值都小于当前节点
- 任意节点右子树上的值都大于当前节点
添加规则
- 小的存左边
- 大的存右边
- 一样的不存
二叉数的遍历方式
前序就是当前节点在前面获取、中序就是当前节点在中间获取、后序就是当前节点在后面获取
前序遍历
从根节点开始，然后按照当前结点，左子节点，右子节点的顺序遍历
中序遍历(重要，遍历出来的数字按照从小到大排序)
从最左边的子结点开始，然后按照左子结点，当前结点，右子节点的顺序遍历（按照左中右的顺序获取数据的）
后续遍历
从最左边的子节点开始，然后按照左子结点，右子结点，当前结点的顺序遍历
层序遍历
从根节点开始一层一层的遍历
平衡二叉树
查找二叉树有弊端：如果7、8、9、10、11、12,按照查找二叉树的规则去存，那么右子结点会特别长，而左子结点没有数据，导致左右子节点高度相差太大，这样也会影响查询的效率，在这个基础上引出了平衡二叉树的概念。
规则
任意节点左右子树高度差不超过1
以下两个都不是平衡二叉树。这边记住是任意节点的左右子树高度差不超过1，以左边为例，如果是10，那么左子节点的高度为0，右子节点的高度为3，高度相差大于1，所以不是平衡二叉树。
旋转机制
- 规则1：左旋
- 规则2：右旋
- 触发时机：当添加一个节点之后，该树不再是一颗平衡二叉树
左旋
确定支点：从添加的节点开始，不断的往父节点找不平衡的节点，找到的第一个满足条件的，就作为支点
步骤：
- 以不平衡的点作为支点
- 把支点左旋降级，变成左子节点
- 晋升原来的右子节点
左旋完的结果：
左旋的特殊情况
左旋完后的结果：
右旋
基本和左旋相同的步骤，只不过往左的改为往右
需要旋转的四种情况
左左（一次右旋）
当根节点左子树的左子树有节点插入，导致二叉树不平衡
左右（先局部左旋，在整体右旋）
当根节点左子树的右子树有节点插入，导致二叉树不平衡。
由于一次右旋，还是未平衡，所以需要先局部左旋（结果就会变成左左一样的情况），在整体右旋。
整体在右旋：
右右（一次左旋）
当根节点右子树的右子树有节点插入，导致二叉树不平衡。
右左（先局部右旋，在整体左旋）
当根节点右子树的左节点有节点插入，导致二叉树不平衡。
红黑树
红黑树增删改查的性能都很好
- 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
- 它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色
- 每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过红黑规则进行实现的
节点的内部结构
- 父节点地址
- 值
- 左子节点地址
- 右子节点地址
- 颜色
红黑规则
- 每一个节点是红色或者是黑色的
- 根节点必须是黑色的
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的
- 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
红黑树添加节点规则
- 默认颜色：添加节点默认是红色的（效率高）
- 效率高的原因的假设默认是黑的每添加一次节点就违背了规则5，每次都需要调整，如果假设添加的默认是红色，那么添加三个节点，才调整一次（违反了规则4）
