数据结构是对大规模的数据进行规划，提高操作的效率。
时间复杂度：
时间复杂度就是一个函数，用来描述算法的运行时间的
假设算法要处理的数据总量为X,X足够大，算法为了达到某一个目的（查找，删除，修改....）所要消耗的计算次数为Y
Y=aX+b Y=X O(n)
Y=aX^2+bX+c Y=X^ O(n^2)
Y=a(常数) O(1)
a^Y=X Y=logaX a是大于2的 Y=logX O(logn)
当X足够大，a,b的值已经忽略不记
时间复杂度是评价算法的指标之一
求冒泡排序时间复杂度（无序变有序）：前后两两数据进行比较 ，数据大的往后走，数据小的往前走（从小到大排列）一轮之后一个数据到达正确位置，一轮进行了x-1次，第二轮x-2次，第三轮x-3次，直到k轮，一次。k=x-1
y=x-1+x-2+x-3+....+1=（x-1+1）*（x-1）/2 O(n^2)
二叉查找法 在有序数组中查找一个值
第一次 x个数据 运算一次
第二次 x/2个数据 运算一次
第三次 x/4个数据 运算一次
第k次 1个数据（x/2^(k-1)） 运算一次 求K = log2X O(logn)
快速判断时间复杂度
直接对问题规模下手O(n) 比如从前到后遍历
循环减半log(n)
k层循环O(n^k)
数组（地址连续）：无序数组查找O(n) 降低时间复杂度有
1.二分查找法 先将无序数组变为有序数组，然后二分查找法 O(logn) 要排序 冒泡排序O（n^2） 不好！
2.利用某种算法，设计一种算法来决定数据插入的位置（比如对数据取余(哈希算法)）根据数组下标进行操作时间复杂度O(1)
缺点 ： 会覆盖原来的值，两个不同的值计算出来咋同一个位置（哈希冲突） 解决：拉链法 在冲突位置加入链表
链表长度不长，时间复杂度依然O(1) 链表长度很长，遍历链表的时间就不能够忽略，时间复杂度就是O(n) 解决
链表用不了二分查找法
树 降低时间复杂度
有序二叉树（一个结点左边的值小于该结点，结点右边的值大于该结点）
有多少层就比较多少次，假设有k层 数据总量=2^0+2^1+2^2+......2^k-1=等比求和公式=2^k-1 k=log2X 不稳定也有可能是O(n)，只有左子树或者右子树
平衡二叉树 不光满足二叉树的条件，还要左右子树的高度差不能超过1
链表：地址不连续
四种旋转 LL LR RR RL 由造成不平衡结点朝着不平衡结点走两步
LL 右旋转90 LR 先左旋后右旋 RR 左旋 RL 后2自旋，先右旋后左旋
旋转很消耗计算机资源
红黑树 最优二叉树 转换机制 由2-3-4树转换
1.每个节点不是红色就是黑色
2.根结点永远是黑色
3.每个叶子结点都是黑色，并且是null
4.如果一个节点是红色的，那么它的子节点一定是黑色
5.从根节点到任意一个叶子节点 路径上黑色节点数目相同
重要结论：在红黑树上没有一条路径比其他路径长超过两倍，最多两倍
最短路径：黑+黑+黑
最长路径： 黑+红+黑+红+黑+红 交替
时间复杂度：比较层数
2-3-4树 二节点 能分两个叉，存一个数值，一个存值，两个存数值的情况
三节点 存两个值，分3个叉
四节点 存三个值，4个叉
哈夫曼树和哈夫曼编码
ascii 定长编码
传输的数据太多，需要压缩，就要用变长编码
路径：从根节点到该节点所走的路线
路径长度：路径上边的条数 边：父子节点之间的连线
节点的权 ： 节点的值
带权路径长度： 从根节点到该节点之间的路径长度 与 该节点的权值 的乘积
树的带权路径长度： 所有叶子节点的带权路径长度之和 WPL
WPL最小的就是哈夫曼树
哈夫曼树的构建过程：
1.将代构建哈夫曼树的节点从小到大进行排序，每个数据看成一个节点
2.取出权值最小的两个节点
3.组成一颗新的二叉树，新二叉树根节点的权值就是这两个节点权值之和
4.将这个二叉树以根节点的权值大小再次排序
不断的重复1234，直到所有数据都被处理，就得到哈夫曼树
哈夫曼编码
1.传输的字符串
2.统计各个字符出现的次数
3.按照上面出现的次数构造哈夫曼树，次数作为权值
4.根据哈夫曼树给各个字符编码，向左的路径0向右的路径1
