数据结构

数据结构

数据结构是计算机存储，组织数据的方式。是指相互之间存在的一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

• 栈
• 队列
• 数组
• 列表

栈：
数据进入栈模型的过程称为：压/进栈。
数据离开栈模型的过程称为：弹/出栈。
先进后出
队列：
数据从后端进入队列模型的过程称为：入队列
数据从前段离开队列模型的过程称为：出队列
先进先出
数组：
查询数据通过地址值和索引定位，查询任意数据耗时相同，查询速度快
删除数据时，要将原始数据删除，同时后面每个数据前移，删除效率低
添加数据时，添加位置后的每个数据后移，再添加元素，添加效率极低
链表

链表是一种增删快的模型（对比数组）
链表是一种查询慢的模型（对比数组）
单向链表和双向链表

数据结构-树

二叉树

二叉查找树

二叉查找树，又称为二叉排序树或者二叉搜索树
特点：

1. 每个节点上最多有两个子节点
2. 每个节点的左子节点都是小于自己的
3. 每个节点的右子节点都是大于自己的

二叉查找树添加节点规律：
小的存左边
大的存右边
一样的不存

平衡二叉树

二叉树左右两个子树的高度差不超过1
任意节点的左右两个子树都是一颗平衡二叉树

平衡二叉树-左旋-右旋

左旋：就是将根节点的右侧往左侧拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点。
右旋：将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点。

小结

二叉查找树需要利用左旋和右旋机制保证树的平衡
注意点：

• 判断添加元素与当前节点的关系
• 成功添加之后，判断是否破坏了二叉树的平衡

旋转的四种情况
左左：当根节点左子树有节点插入，导致二叉树不平衡

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

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

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

红黑树

• 平衡二叉B树
• 每一个节点可以是红或者黑
• 红黑树不是高度平衡的，它的平衡是通过“自己的红黑规则”进行实现的

红黑规则

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

添加节点

• 添加的节点的颜色可以是红色的，也可以是黑色的

如果添加三个黑色节点，需要调整两次。
如果添加三个红色节点，需要调整一次。
所以，添加节点时，默认为红色，效率高。
红黑树在添加节点的时候：
添加的节点默认时红色的。