AVL ，图，查找算法
平衡二叉树：
前提是有序的二叉树，它的左右子树的高相差不超过1，它的所有的子树也要满足这个要求。
如果一个有序二叉树呈单支状（接近单支），它的效率接近链表，因此只有达到平衡时它的效率才最高。
由于节点的位置受值的影响，因此只能进行调整，而不能强行修改。
二叉树不平衡的基础原因：
xy
/ \/\
yt1以为轴向右旋转zx
/ \/ \/ \
Zt2t3 t4 t2 t1
/ \
t4t3xy
/ \/\
t1yxz
/ \心y为轴向左旋转/ \/ \
t2zt1 t2 t3 t4
/ \
t3t4xxz
/ \/ \/\
yt1zt1yx
/ \/ \/ \/ \
t4zyt2t4 t3 t2 t1
/\/ \
t3t2t4t3
以z为轴向左旋转以z为轴向右旋转最终达到平衡xxz
/ \/ \/\
t1yt1zxy
/ \/ \/ \/ \
zt4t2yt1 t2 t3t4
/ \/ \
t2t3t3 t4
以z为轴向右旋转心z为轴向左旋转
红黑树：
也一种自平衡的二叉树，它不是根据子树的高度来调整平衡的，而是给节点设置一个颜色，来达到平衡。
优点：插入与删除的效率，比AVL树要高。
缺点：没有AVL均匀，查找效率没AVL树高。
图(Graph)型结构：
什么图型结构：由顶点的有穷且非空和顶点之间边的集合.
通常表示：G(V,E)，G表示一个图，V是图中顶点集合(元素)，E是图中边(元素之间的关系)的集合。
无向图：
边用(A,B)方式表示，点与点之间是互通的。
在无向图中，任意两个顶点之间都有边，该图称为无向完全图，则含有n个顶点的无向完全图有，n*(n-1)/2条边。
有向图：
边用方式表示，仅仅是A到到B点，有向图的边也叫弧，A是弧尾，B是弧头。
在有向图中，任意两个顶点之间都方向相反的两条弧，这种图叫有向完全图，则含有n个顶点的有向完全图有，n*(n-1)。
注意：不存在顶点到自身的边，且一条边不重复出现，这种图叫简单图，数据结构中只研究简单图。
图的点多边少的图叫稀疏图，反之的叫稠密图，图的点与点之间边带数据，这些数据叫作边的权重，带权重的图被称为网。
依附于顶点的边的数量叫作顶的度，有向图双分为出度(从顶出的的弧的数量)和入度(指向顶点的弧的数量)。
路径：顶点到顶点经过的边叫路径，边的数量叫路径的长度。
第一个顶点到最后一个顶的路径是相同的，这种路径叫回路或者环。
序列顶点中不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点，其余顶点不重复出现的回路叫简单回路。
如果顶点V到顶点V1有路径，则称V和V1是连通的，如果图中和任意顶点之间是连通的，则称图为连通图，如果一个图中有n个顶点那么至少需要n-1条边才能达到连通图，仅需要n-1边的连通叫生成树，如果再配合上权重，代价最的叫最小生成树。
树的存储结构：
阾接矩阵：
用一个一维数组来存储n个顶点，用一个n*n二维数组来存储边。
char V[n] = {A,B,C,D,E,F,G};
A B C D E F G
A [0][1][0][0][0][0][0] [1] A
B [0][0][0][1][1][0][0] [1] B
C [1][0][0][0][1][0][0] [1] C
D [0][0][0][0][0][1][1] [1] D 3
E [0][0][0][0][0][0][0] [1] E
F [0][0][1][0][0][0][0] [1] F
G [0][0][0][0][0][1][0] [1] G
A B D F C E G
A B D F C E G
A B E D F C G
二维数组中E[i][j]的值为1，则表示项V[i]，到顶点V[j]有边。
注意：由于不存在自己到自己的边，主对角线上的值为假。
如果存储的是无向图则二维数组中的值沿主对角线对称，可以压缩为一维数组（参看矩阵压缩）。
阾接矩阵的优点是可以方便计算顶点的入度和出度，但缺点是当图是稀疏图时，会非常浪费存储空间。
阾接表：
边：
顶点下标
下一条边的地址
顶点：
数据
指向第一条边的指针
图：
由顶点组成的数组
顶点数量cnt
优点：可以节约存储空间，计算入度麻烦。
十字链表：
边：
弧尾下标
弧头下标
指向相同弧尾的下一条边
指向相同弧头的下一条边
顶点：
数据
指向第一条边的指针
指向入度的边
图：
由顶点组成的数组
顶点数量cnt
阾接多重表：
是一种专门存储无向图的一种结构。
边：
i,j 两个互相依附的顶点的下标
inext 指向下一个依附i项点的边
jnext 指向下一个依附j项点的边
顶点：
数据
指向与顶点有关系的一条边。图：
由顶点组成的数组。
顶点数量
算法：
输入: 算法具有0个或多个输入
输出: 算法至少有1个或多个输出
有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性：算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完
如果评价一个算法：
时间复杂度：由于计算机的性能不同，无法准确统计出算法执行所需要的时间。
因此我们用算法执行的次数来代表算法的时间复杂度，O(公式)，一般忽略常数。
常见的时间复杂度：
// O(1)
printf("%d",i);
// O(logn)
for(int i=n;
i>=0;
i=i/2)
{
printf("%d",i);
}
// O(n)
for(int i=0;
i=0;
i=i/2)
{
printf("%d",i);
}
}
// O(n^2)
for(int i=0;
i 【AVL ，图，查找算法】查找算法：
顺序查找：
对待查找的数据没有要求，时间复杂度: O(n)
二分查找:
对待查找的数据必须有序，时间复杂度: O(logn)
块查找
哈希查找
