哈希表
定义：哈希表（也叫散列表），是根据关键码值（key,value）而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。关键码值（key,value）也可以当成是key的hash值。这个映射函数叫做散列函数，存放记录的数组叫做散列表
特点：数组（顺序表）：寻址容易
链表：插入与删除容易
哈希表：寻址容易，插入删除也容易的数据结构
例子：
缺点:扩容需要消费大量的空间和性能，散列函数需要重新设计。
应用：电话号码，字典，点歌系统，QQ，微信的好友等（有一定数量限制的）
设计：拉链法
jdk1.8以前使用链表
jdk1.8开始 当链表长度超过阈值，就转换成红黑树
树
树是N个结点的有限集。n=0时称为空树，在任意一颗非空树中：(1)有且仅有一个特定的称为根（Root）的结点：（2）当n>1时，其余结点可分为m个互不相交的有限集T1,T2.......Tm,其中每一个集合本身又是一棵树，并且称为根的子树。
节点与树的度
结点拥有的子树数称为结点的度。
度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。
除根结点以外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
结点的层次和深度
结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第一层，则其子树的根就在第1+1层。其双亲在同一层的结点互为堂兄弟。显然途中的D，E，F是堂兄弟，而G,H,I,J也是。树中结点的最大层次称为树的深度或高度，当前树的深度为4.
树的存储结构（孩子表示法）
二叉树
二叉树是N个结点的有限集合，该集合或者为空集，或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
二叉树的存储结构
顺序存储：
链式结构
二叉树的遍历：
前序遍历（DLR）
中序遍历（LDR）
后序遍历（LRD）
二叉树遍历的应用之分治法
1，查找技术
(1)顺序查找
public static int search(int[] a, int num) {
for(int i = 0; i < a.length; i++) {
if(a[i] == num){//如果数据存在
return i;//返回数据所在的下标，也就是位置
}
}
return -1;//不存在的话返回-1
}
(2)二分查找
前提条件：数据是已经排序的
原理图
注意：设计成左闭右开---是一种区间无重复的思想 random(0,1)等大量的数学函数都是这样设计的
/**
* 二分查找 前提是数组必须是有序的
*/
public static int binarySearch(int [] array,int fromIndex,int toIndex,int key){
int low = fromIndex;
int high = toIndex-1;//左闭右开原则
while(low<=high){
int mid = (low+high)/2;//取中间
int midValue = array[mid];
if(key>midValue){//去中点往右寻找
low = mid+1;
}else if(key<midValue){//去中点往左寻找
high = mid-1;
}else{
return mid;
}
}
return -(low+1);
}
2，快速排序（二叉树的前序遍历）
思想：先确定一个数组的数据，然后取出数组任意一个数据，通过比较，把比这个数小的数据都放在这个数的左边，把比这个数大的数据都放在这个数的右边，然后不停循环下去
应用场景：数据量大并且是线性结构
短处：有大量重复数据的时候，性能不好。单向链式结构处理性能不好
/**
* 快速排序 31 21 59 68 12 40 （先取一个数据出来，第一轮排序之后左边都小于这个数，右边都大于这个数，然后一直循环）
*/
public static void quickSort(int [] array,int begin,int end){
if(end-begin<=0) return;
int low = begin;//0
int high = end;//5
int x = array[begin];
//由于会分别从两头取数据
boolean direction = true;
L1:
while(low<high){
if(direction){//从右往左找
for(int i = high;i>low;i--){
if(array[i]<=x){
array[low++] = array[i];
high = i;
direction = !direction;
continue L1;
}
}
high = low;//如果一直上面的if从未进入，让两个指针重合
}else{//从左往右找
for(int i=low;i<high;i++){
if(array[i]>=x){
array[high--]=array[i];
low = i;
direction = !direction;
continue L1;
}
}
low = high;
}
}
array[low] =x;//第一轮确定X位置，左边的都小于X，右边的都大于X
quickSort(array,begin,low-1);
quickSort(array,low+1,end);
}
3，归并排序（二叉树的后序遍历）
思想：
应用场景：数据量大并且有很多重复数据，链式结构
短处：需要空间大（空间换时间）
/**
* 归并排序 思想：二叉树的后序遍历
* @param array
* @param left
* @param right
*/
public static void mergeSort(int[] array,int left,int right){
if(left == right){
return;
}else{
int mid = (left+right)/2;
mergeSort(array,left,mid);
mergeSort(array,mid+1,right);
merge(array,left,mid+1,right);
}
}
/**
* 将一个左右两边分别排好序的数组合并成一个完整的排好序的数组
*/
//1,2,5,9 ======== 3,4 ,10 ,11
public static void merge(int []array,int left,int mid ,int right){
//1,将一个数组分成左右两个数组
int leftSize = mid-left;
int rightSize = right - mid + 1;
int [] leftArray = new int[leftSize];
int [] rightArray = new int[rightSize];
//将数组的数组填充到左右两个数组中去
for(int i = left;i<mid;i++){
leftArray[i-left] = array[i];
}
for(int i = mid;i<=right;i++){
rightArray[i-mid] =array[i];
}
//将两个数组排序后合并
int i=0;
int j=0;
int k=left;
while(i<leftSize && j<rightSize){
if(leftArray[i]<rightArray[j]){
array[k] = leftArray[i];
k++;i++;
}else{
array[k] = rightArray[j];
k++;j++;
}
}
while(i<leftSize){
array[k] = leftArray[i];
k++;i++;
}
while(j<rightSize){
array[k] = rightArray[j];
k++;j++;
}
}
