手撕memcpy#

memcpy函数是c和c++使用的内存拷贝函数，函数原型是：

1
void *memcpy(void*dest, const void *src, size_t n);

表示由src指向地址为起始地址的连续n个字节的数据复制到以dest指向地址为起始地址的空间内。

与strcpy相比，memcpy并不是遇到’\0’就结束，而是一定会拷贝完n个字节。

注意事项：对于地址重叠的情况，上述函数的行为是未定义的，因此要考虑到此问题

要点：void*类型的指针不能运算，必须强转

​ 必须要考虑内存重叠问题(画个图自然就明白了！)

1
void * my_memcpy(void *dst, const void *src, size_t count){
2
  if(dst==nullptr||src==nullptr){
3
    return nullptr;
4
  }
5
    char* temp_dst=(char*)dst;
6
    char* temp_src=(char*)src;
7
    if(temp_dst>temp_src&&temp_dst<temp_src+count ){
8
        //有内存重叠的情况
9
         temp_dst=temp_dst+count-1;
10
        temp_src=temp_src+count-1;
11
        while(count--){
12
            *temp_dst--=*temp_src--;
13
        }
14
    }else{
15
        //没有内存重叠的情况
16
         while(count--){
17
            *temp_dst++=*temp_src++;
18
        }
19
    }
20
    return (void *)dst;
21
}

十大排序算法#

排序算法的稳定性：在具有多个相同关键字的记录中，若经过排序这些记录的次序保持不变，说排序算法是稳定的。

冒泡排序O(n^2^)#

思路：两两比较元素，顺序不同就交换

图解：

代码：

1
void Bubble_Sort(int a[],int length) {
2
  for (int i = 0;i < length - 1;i++) {
3
    for (int j = 0;j <length-i-1 ;j++) {
4
      if (a[j]>a[j+1]) {
5
        int temp = a[j];
6
        a[j] = a[j +1];
7
        a[j+1] = temp;
8
      }
9
    }
10
  }
11
}

选择排序O(n^2^)#

思路：每一次从待排序的数据元素中选择最小（最大）的一个元素作为有序的元素。如果是升序排序，则每次选择最小值就行，这样已经排好序的部分都是生序排序选择排序是不稳定的，比如说（55231这种情况，两个5的相对顺序会变）

图解：

代码：

1
void Select_Sort(int a[],int length) {
2
  for (int i = 0;i < length - 1;i++) {
3
    int min_index = i;
4
    for (int j = i+1;j < length;j++) {
5
      if (a[min_index]>a[j]) {
6
        min_index = j;
7
      }
8
    }//for j
9
    if (i!=min_index) {
10
      int temp = a[i];
11
      a[i] = a[min_index];
12
      a[min_index] = temp;
13
    }
14
  }//for i
15
}

展开收起

希尔排序——缩小增量排序O(nlogn)#

思路：

希尔排序又叫缩小增量排序，使得待排序列从局部有序随着增量的缩小编程全局有序。当增量为1的时候就是插入排序，增量的选择最好是531这样间隔着的。

其实这个跟选择排序一样的道理，都是不稳定的比如下图7变成9的话，就是不稳定的

图解：

代码：

1
void Shell_Sort1(int a[], int length) {
2
  //首先定义一个初始增量，一般就是数组长度除以2或者3
3
  int gap = length / 2;
4
  while (gap >= 1) {
5
    for (int i = gap;i < length;i++) {
6
      int temp = a[i];
7
      int j = i;
8
      while (j >= gap&&temp<a[j - gap]) {
9
        a[j] = a[j - gap];
10
        j = j - gap;
11
      }//while
12
      a[j] = temp;
13
    }//for
14
    gap=gap/2;
15
  }//while
16
}
17
/*****************另一种写法， 好理解****************************/
18
void shellsort3(int a[], int n)
19
{
20
    int i, j, gap;
21
    for (gap = n / 2; gap > 0; gap /= 2)
22
        for (i = gap; i < n; i++)
23
            /*j>gap之后，j前面的可以重新比较依次保证j前面间隔gap的也是有序的*/
24
            for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
25
                Swap(a[j], a[j + gap]);
26
}

展开收起

快速排序O(nlogn)#

思路：快排的核心叫做“基准值“，小于基准值的放在左边，大于基准值的放在右边。然后依次递归。基准值的选取随机的，一般选择数组的第一个或者数组的最后一个，然后又两个指针low和high

图解：“基准值就是第一个元素”

1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；

2）以第一个数组元素作为关键数据，赋值给 key ，即 key =A[0]； 　　

3）从J开始向前搜索，即由后开始向前搜索（J=J-1即J—），找到第一个小于 key 的值A[j]，A[j]与A[i]交换； 　　

4）从I开始向后搜索，即由前开始向后搜索（I=I+1即I++），找到第一个大于 key 的A[i]，A[i]与A[j]交换； 　　

5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。）

代码：

1
//快速排序 需要两个函数配合
2
int Quick_Sort_GetKey(int a[],int low,int high) {
3
  int temp = a[low];
4
  while (low<high) {
5
    //首先比较队尾的元素和关键之temp，如果队尾大指针就往前移动
6
    while (low<high&&a[high]>=temp) {
7
      high--;
8
    }
9
    //当a[high]<temp的时候，跳出循环然后将值付给a[low],a[low]=temp
10
    a[low] = a[high];
11
    //赋值过一次之后就立刻从队首开始比较
12
    while (low<high&&a[low]<=temp) {
13
      low++;
14
    }
15
    a[high] = a[low];
16
  }//while (low<high)
17
  a[low] = temp;//或者a[high]=temp
18
  return low;
19
}
20
void Quick_Sort(int a[],int low,int high) {
21
  if (low<high) {
22
    int key = Quick_Sort_GetKey(a, low,high);
23
    Quick_Sort(a,low,key-1);
24
    Quick_Sort(a,key+1,high);
25
  }
26
}

展开收起

堆排序O(nlogn)#

思路：堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。堆排序分为两步：首先将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。随后第二步将其与末尾元素进行交换，此时末尾就为最大值。然后将这个堆结构映射到数组中后，就会变成升序状态了。（即升序—大根堆）

当数组元素映射成为堆时：

1. 父结点索引：(i-1)/2
2. +左孩子索引：2**i*+1
3. 左孩子索引：2**i*+2

图解：

基本思想：

1. 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2. 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3. 将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

代码：

1
//index是第一个非叶子节点的下标（根节点）
2
//递归的方式构建
3
void Build_Heap(int a[],int length,int index){
4
  int left = 2 * index + 1;  //index的左子节点
5
  int right = 2 * index + 2;//index的右子节点
6
  int maxNode = index; //默认当前节点是最大值，当前节点index
7
  if (left<length&&a[left]>a[maxNode]) {
8
    maxNode = left;
9
  }
10
  if (right<length&&a[right]>a[maxNode]) {
11
    maxNode = right;
12
  }
13
  if (maxNode!=index) {
14
    int temp = a[maxNode];
15
    a[maxNode] = a[index];
16
    a[index] = temp;
17
    Build_Heap(a,length,maxNode);
18
  }
19

20
}
21
void Heap_Sort(int a[],int length) {
22
    // 构建大根堆（从最后一个非叶子节点向上）
23
    //注意，最后一个非叶子节点为(length / 2) - 1
24
  for (int i = (length / 2) - 1;i >= 0;i--) {
25
    Build_Heap(a, length, i);
26
  }
27
  for (int i = length - 1;i >= 1;i--) {
28
    //交换刚建好的大顶堆的堆顶和堆末尾节点的元素值，
29
    int temp = a[i];
30
    a[i] = a[0];
31
    a[0] = temp;
32
    //交换过得值不变，剩下的重新排序成大顶堆
33
    Build_Heap(a,i,0);
34
  }
35
}

展开收起

归并排序(nlogn)#

思路：分治思想，将若干个已经排好序的子序合成有序的序列。

图解：

代码：

1
//分治思想，先逐步分解成最小(递归)再合并
2
//归并
3
void Merge(int a[],int low,int mid,int high) {
4
  int i = low;
5
  int j = mid + 1;
6
  int k = 0;
7
  int *temp = new int[high - low + 1];
8
  while (i<=mid&&j<=high) {
9
    if (a[i]<=a[j]) {
10
      temp[k++] = a[i++];
11
    }
12
    else {
13
      temp[k++] = a[j++];
14
    }
15
  }//while (i<mid&&j<=high)
16
  while (i<=mid) {
17
    temp[k++] = a[i++];
18
  }
19
  while (j<=high) {
20
    temp[k++] = a[j++];
21
  }
22
  for (i = low, k = 0;i <= high;i++, k++) {
23
    a[i] = temp[k];
24
  }
25
  delete[] temp;
26
 }
27
//递归分开
28
void Merge_Sort(int a[], int low, int high) {
29
  if (low < high) {
30
    int mid = (low + high) / 2;
31
    Merge_Sort(a, low, mid);
32
    Merge_Sort(a, mid + 1, high);
33
    cout << "mid=" << mid <<" " <<a[mid]<< endl;
34
    cout << "low=" << low << " " << a[low] << endl;
35
    cout << "high=" << high << " " << a[high] << endl;
36
    cout << endl;
37
    //递归之后再合并
38
    Merge(a, low, mid, high);
39
  }
40
}

展开收起

代码看不懂没关系，参考链接

计数排序O(n+k)#

思路：

将待排序的数据存放到额外开辟的空间中。首先找出元素的最大最小值，然后统计每个元素i出现的次数，然后放入数组i中，数组中存放的是值为i的元素出现的个数。额外数组中第i个元素是待排序数组中值为i的元素的个数。因为要求输入的数有确定范围，同时只能对整数进行排序，有场景限制。

图解：

代码：

1
void Count_Sort(int a[],int length) {
2
  //得到待排序的最大值
3
  int max = a[0];
4
  int i=0;
5
  while ( i<length-1) {
6
    max = (a[i] > a[i + 1]) ? a[i] : a[i + 1];
7
    i++;
8
  }
9
  int *countArray = new int[max + 1]{0};
10
  int *temp = new int[length];
11

12
  for (int i = 0;i < length;i++) {
13
    countArray[a[i]]++;
14
  }
15
  //!!!这一步的思想特别重要，在非比较排序中
16
  for (int i = 1;i < max+1;i++) {
17
    countArray[i] += countArray[i - 1];
18
  }
19
  //反向遍历
20
  for (int i = length - 1;i >= 0;i--) {
21
    temp[countArray[a[i]]-1] = a[i];
22
    countArray[a[i]]--;
23
  }
24
  for (int i = 0;i < length;i++) {
25
    a[i] = temp[i];
26
  }
27
  delete[] countArray;
28
  delete[] temp;
29
}

展开收起

基数排序O(n*k)#

**思路：**基数也就表明桶的个数是定死的，就是10个。基数排序的思想是，从个位依次开始排序，首先按照个位的大小排序，将改变的序列按照十位开始排序，然后一次往后……

图解：

代码：

1
int Get_Max_Digits(int a[],int length) {
2
  int max = a[0];
3
  int i = 0;
4
  while (i<length-1) {
5
    max = (a[i] > a[i + 1]) ? a[i] : a[i + 1];
6
    i++;
7
  }
8
  int b = 0;//最大值的位数
9
  while (max>0) {
10
    max = max / 10;
11
    b++;
12
  }
13
  return b;
14
}
15
//切记！桶子只能是十个，是定死的
16
void Radix_Sort(int b[],int length) {
17
  int d = Get_Max_Digits(b, length);//得到最大值的位数
18
  int * temp = new int[length];//开辟一个和原数组相同的临时数组
19
  //根据最大值的位数进行排序次数循环
20
  int radix = 1;
21
  for (int i = 0;i < d;i++) {
22
    //每次把数据装入桶子前先清空count
23
    int count [10] = { 0 }; //计数器 每次循环都清零
24
    for (int j = 0;j < length;j++) {
25
      //统计尾数为0-9的个数，一次是个十百千....位
26
      int tail_number = (b[j]/radix)%10;
27
      count[tail_number]++;//每个桶子里面的个数
28
    }
29
    //桶中的每一个数的位置一次分配到temp数组中，先找到位置
30
    for (int j = 1;j < 10;j++) {
31
      count[j] += count[j - 1];
32
    }
33
    //分配到temp中排序后的位置
34
    for (int j = length - 1;j >= 0;j--) {
35
      int tail_number = (b[j] / radix) % 10;
36
      temp[count[tail_number] - 1] = b[j];
37
      count[tail_number]--;
38
    }
39
    //赋值
40
    for (int j = 0;j < length;j++) {
41
      b[j] = temp[j];
42
    }
43
    radix *= 10;
44
  }//for(int i)
45
  delete[] temp;
46
}

展开收起

桶排序O(n+k)#

**思路：**基数排序和计数排序都是桶思想的应用。桶排序是最基本的

​ 首先要得到整个待排序数组的最大值和最小值，然后设置桶的个数k，这样可以得到每个桶可以放的数的区间。

​ 然后遍历待排序的数组，将相关区间内的数放到对应的桶中，这样桶内在排序，就使得整个序列相对有序

图解：

代码：

1
void bucketSort(int arr[], int len) {
2
    // 确定最大值和最小值
3
    int max = INT_MIN; int min = INT_MAX;
4
    for (int i = 0; i < len; i++) {
5
        if (arr[i] > max) max = arr[i];
6
        if (arr[i] < min) min = arr[i];
7
    }
8

9
    // 生成桶数组
10
    // 设置最小的值为索引0，每个桶间隔为1
11
    int bucketLen = max - min + 1;
12
    // 初始化桶
13
    int bucket[bucketLen];
14
    for (int i = 0; i < bucketLen; i++) bucket[i] = 0;
15

16
    // 放入桶中
17
    int index = 0;
18
    for (int i = 0; i < len; i++) {
19
        index = arr[i] - min;
20
        bucket[index] += 1;
21
    }
22

23
    // 替换原序列
24
    int start = 0;
25
    for (int i = 0; i < bucketLen; i++) {
26
        for (int j = start; j < start + bucket[i]; j++) {
27
            arr[j] = min + i;
28
        }
29
        start += bucket[i];
30
    }
31
}

展开收起

查找算法（七大查找算法）#

非递归遍历二叉树#

• 先序遍历·

  1
  /*对于任一结点cur：
  2
  1)访问结点cur，并将结点cur入栈;
  3
  2)判断结点cur的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点cur，循环至1);
  4
      若不为空，则将cur的左孩子置为当前的结点cur;
  5
  3)直到cur为NULL并且栈为空，则遍历结束。*/
  6
  void NonRecursive::PreTraverse(BinaryTree *T) {
  7
    stack<BinaryTree *> s;
  8
    BinaryTree *cur=T;
  9
    while (cur!=nullptr||!s.empty()) {
  10
      while (cur!=nullptr) {
  11
        cout << cur->val <<" ";
  12
        s.push(cur);
  13
        cur = cur->leftchild;
  14
      }
  15
      //涉及到pop的操作所以判定条件是栈不为空
  16
      if (!s.empty()) {
  17
        cur = s.top();
  18
        s.pop();
  19
        cur = cur->rightchild;
  20
      }
  21
    }
  22
  }

  展开收起

• 中序遍历

  1
  /*cur的左孩子置为当前的cur，然后对当前结点cur再进行相同的处理；
  2
  2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的cur置为栈顶结点的右孩子；
  3
  3)直到cur为NULL并且栈为空则遍历结束
  4
  */
  5
  void NonRecursive::MidTraverse(BinaryTree *T) {
  6
    stack<BinaryTree *>s;
  7
    BinaryTree *cur = T;
  8
    while (cur!=nullptr||!s.empty()) {
  9
      while (cur!=nullptr) {
  10
        s.push(cur);
  11
        cur = cur->leftchild;
  12
      }
  13
      if (cur==nullptr) {
  14
        cur = s.top();
  15
        cout << cur->val << " ";
  16
        s.pop();
  17
      }
  18
      cur = cur->rightchild;
  19
  
  20
    }
  21
    cout << endl;//回车换行
  22
  }

  展开收起

• 后序遍历

  1
  //思想： 一共有两种情况
  2
  //①节点同时没有左孩子和右孩子，说明是根节点，可以遍历然后出栈；
  3
  //②或者不是根节点但同时左孩子和右孩子被访问过，也可以遍历后出栈
  4
  void NonRecursive::EndTraverse(BinaryTree *T) {
  5
    stack<BinaryTree *> s;
  6
    BinaryTree *cur ;
  7
    BinaryTree *pre = nullptr;
  8
    s.push(T);
  9
    while (!s.empty()) {
  10
      cur = s.top();
  11
      if ((cur->leftchild==nullptr&&cur->leftchild==nullptr)  //没有左孩子和右孩子了说明可以访问
  12
        ||  (pre!=nullptr&&  (pre==cur->leftchild||pre==cur->rightchild)) //存在子树同时左孩子和右孩子都被访问过了
  13
        ) {
  14
        cout << cur->val<<" ";
  15
        s.pop();
  16
        pre = cur;
  17
      }
  18
      else {
  19
        //右孩子先入栈  左孩子后入栈
  20
        if (cur->rightchild!=nullptr) {
  21
          s.push(cur->rightchild);
  22
        }
  23
        if (cur->leftchild!=nullptr) {
  24
          s.push(cur->leftchild);
  25
        }
  26
      }
  27
    }
  28
  }

  展开收起

KMP算法#

**字符串匹配问题：**字符串 P 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？” 其中 S 称为主串；P 称为模式串。如下图：

最容易想到的方法：Brute-Force

暴力法的时间复杂度是$O(|P|*(|S|-|P|+1)) = O(|P|*|S|) = O(mn)$

KMP算法：

kmp算法就是尽量利用残余信息，不用逐个比字符串。其思路下面这个图就解释清楚了：

即我们可以不用一个一个往后挪这比较，而是往后挪好几个身位去比较。这个时候挪多少个位置呢？需要next数组去帮我们。

next数组中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长 度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。

最小生成树——Prim算法和Kruskal算法#

这两种算法都是求最小生成树的，都是贪心算法的典型应用

这个算法讲的详细

• Prim算法

  图论中的一种算法，可以在加权连通图中搜索最小生成树。包括图中所有顶点之且所有边的权值之和最小

• Kruskal算法

  也是用来寻找最小生成树的算法

  思路是将所有边的长度排序，然后

二叉查找树，二叉搜索树#

它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

AVL树（平衡二叉树）#

AVL是一种高度平衡的二叉树，本质也是一颗二叉查找树，有以下两个特点：

1. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
2. 左右两个子树也都是一棵平衡二叉树。

这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多

AVL树主要的难点在于插入和删除

• 插入

参考链接

又回看了以便，其实插入位置为左左型和右右型的其实是一个东西，本质上都是一次旋转就行了，注意有个节点需要断开原先的连接

像左右型和右左型这种都需要两次旋转，但是这两次旋转本质上和一次旋转一模一样，所以说这四种插入位置其实本质上都差不多的。

字典树#

• 什么是字典树？

  字典树我愿意给他叫做单词查找树，利用字符串的公共前缀来降低查询时间进而提高效率。有以下三个性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 总根节点到某一个节点，路径上的字符连接起来为该节点对应的字符串。
  3. 每个节点所有子节点包含的字符都不同。

• 字典树的使用范围

  1. 词频统计

     如果内存有限，hash表所占的空间很大，我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。

  2. 前缀匹配

     ​

2-3查找树#

• 定义

  相比于AVL树对平衡性的严格要求，2-3查找树相对灵活一些。这里面2-3查找树允许一个节点保存多个键。

  通常我们将一棵标准的二叉查找树成为2-节点，因为每个节点都只有一个键（关键字）和两个链接

  但是2-3查找树引入了3节点，表示一个节点中有两个关键字和三个节点。

  

• 性质

  1. 任意一个节点都有1个或者2个关键码
  2. 当节点有1个关键码的时候，节点有2个子树
  3. 当节点有两个关键码的时候，节点有3个子树
  4. 所有叶子节点都在树的同一层

红黑树#

线性查找 —性能低—>二分查找— 二查叉树会出现退化成链表的问题—>出现AVL平衡二叉树—数据变化有频繁更新节点问题(即AVL变态的平衡)—>出现红黑树

AVL树和红黑树都是由二叉树繁衍而来，这两个数有不同的适用条件：

1. 如果有频繁的插入和删除的话，不要用AVL数，因为其变态的平衡要求
2. 如果频繁的查找，但是插入和删除不多的话用AVL树的话是可以的

参考链接

红黑树本质上也是一种二叉查找树，但是他是自平衡的，在插入和删除可能会破坏树的结构的情况下需要自行处理以达到平衡状态。

红黑树有以下特性：

1. 每个节点不是黑色就是红色
2. 根节点是黑色
3. 如果一个节点为红色，则子节点必为黑色
4. 任意一个节点到每个叶子节点的路径上都包含数量相同的黑节点（这个时候null节点不算进去）
5. 每个叶子节点（NULL）都是黑色的。（红黑树吧null节点当做了叶子节点）

• 左旋和右旋

  左旋和右旋是一个相对的概念，但是只要记住：对一个节点左旋的时候，意味着将这个节点变成左节点，如果这个节点是根节点的话，那么也变成左节点，他的右节点就是这个节点的根节点

  1
                                 z
  2
     x                          /
  3
    / \      --(左旋)-->       x
  4
   y   z                      /
  5
                             y

  右旋也是一样的，x节点变成右孩子节点，左旋就是变成左孩子节点。然后x节点的左孩子节点变成x节点的根节点

  1
                                 y
  2
     x                            \
  3
    / \      --(右旋)-->           x
  4
   y   z                            \
  5
                                     z

• 插入

• 删除

B-tree#

对于树结构的查找来说，有以下几种：二叉查找树，平衡二叉查找树，红黑树，B-tree等等。对于二叉树来说，查找的为log2N，很明显和树的深度有关，因此在数据量特别大的时候，我们需要尽可能降低树的深度来提高查询效率。但是如果减少树的深度，那么每棵树上的节点数就会很多，这样还是退化到了对于节点的线性查找，可能时间复杂度还会增加，怼到线性的。因此我们想要降低树的深度就要采用多叉树结构。因此B树就是一个多叉树，为了降低磁盘频繁的查找操作而设计的。

B树也称B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生，其实，B树和后面讲到的B+树也是从最简单的二叉树变换而来的

B树有用度定义的，有用阶定义的。在这里我写的话就用阶的概念来定义，阶就是说这个树最多有多少个子节点数，用m表示。m取2的时候就表示我们的二叉树

**度数：**每个节点子节点的个数称为该树的度。

**阶数：**一个节点的子节点数目最大值。

用阶定义B数如下图：

1. 根节点不是叶子节点至少要有两个子节点，非根节点至少有m/2个子节点，取上限。
2. 有n个子节点的节点恰好包含n-1个关键字
3. 每个节点中的关键字都是按照从小到大的顺序排列的，同时每个关键字的左子树中的关键字均小于它，右子树中的关键字均大于它。
4. 所有叶子节点都在同一层中

下图所示就是一个阶为4的B树：

B+树的叶子节点内部结构如下图：

本质上说叶子节点存储的也不是数据，而是数据指针，指向磁盘中的数据。

通常在实际应用中B树的阶都很大，通常大于100。因此即使存储了大量的数据，B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。

• 查找

  

  如上图所示，根据根节点004和008可得，有小于004，大于004小于008和大于008三种情况，分别对应三个子树，就这样查找如果树结构里面没有包含所要查找的节点则返回null，总体来说，B树的搜索流程跟普通二叉搜索树的搜索流程大体类似。

  所以B树的查询并不稳定，根节点中关键字可能只需要1次IO操作，但是如果在叶子节点中可能需要树高度次磁盘IO操作

• 插入操作

  1. 树中已经存在当前的key，则更新value

  2. 若当前节点的关键字个数小于m-1，则正常插入

  3. 若加入key后当前节点的个数大于m-1， 则以当前节点中所有关键字的中间为基准点开始分裂，将基准点的key值放入到父节点（因为B数要求左边小于父节点，右边大于父节点），当前基准值的左子树都比他小，右子树都比他大。

     举一个5阶树的列子：

     1. 未插入元素前：

        

     2. 插入22后，图如下，就不满足5阶B树的定义了

        

     3. 分裂中间基准点40

        

     4. 接着插入23，25，39，然后继续分裂，如下：

        

     以上就是B树的插入过程。

• 删除操作

  1. 如果不存在对应的key，则删除失败
  2. 如果删除的是叶子节点中的关键字，则删除就行
  3. 若当前删除的key位于非叶子节点，则用key的后继节点替换当前要删除的节点，然后把这个后继节点删除（后继节点一定位于叶子节点上）。.

• 复杂度分析

  具体分析看B+树中，我把B+和B树一起给分析了，这俩时间复杂度是一样的。

B+ Tree#

参考

B+树是b树的一种变体，广泛的用在存储引擎中。

和B树的相同点：

根节点不是叶子节点至少要有两个子节点，非根节点至少有m/2个子节点，取上限。

和B树的不同点：

1. B+树有两种类型的节点：索引结点和叶子结点。索引节点就是非叶子节点，内部节点不存储数据，只存储索引（即key），数据都存储在叶子节点。
2. 非叶子节点中，有n颗子树就包含n个key
3. 非叶子节点中包含的是子树中最大或最小的key
4. 所有叶子节点中包含了全部关键字的信息， 及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接；

如下图所示：

• 查找

  查询单个元素

  

  比如说查询元素59。第一次磁盘IO，访问根节点。然后发现59<=[59,97]，访问当前节点的第一个孩子节点。第二次磁盘IO，发现59>=[15,44,59]，访问当前节点的第三个孩子节点。第三次磁盘IO，访问叶子节点[51,59]，顺序遍历内部节点找到59

  可以看到，B+树查找每个元素所用的磁盘IO数量一样

  区间查询元素

  区间查询的关键点在于叶子节点中，每个叶子节点都有一个指向下一个叶子节点的$P_{next}$指针。

  为了更好地对比B树和B+树他们区间查询的优势，我先说一下B树的，查询21<=key<=63

  

  首先找到21所在的节点，上图中在叶子节点。然后从关键字21开始进行中序遍历，关键字依次为37、44、51、59、72、63。不考虑中序遍历过程的压栈和入栈操作，磁盘IO就多了两次(72、63)

  再来看B+树的区间查找：

  

  根据每个节点的索引找到叶子节点[21、37、44]后找到左端点21，接着不需要中序遍历，而是链表形式的遍历，从21找到63，没有任何额外的磁盘IO操作

• 插入

  要注意一下几点：

  1. 插入的操作全部都在叶子结点上进行，且不能破坏关键字自小而大的顺序；
  2. 由于 B+树中各结点中存储的关键字的个数有明确的范围，做插入操作可能会出现结点中关键字个数超过阶数的情况，此时需要将该结点进行 “分裂”；

  插入有三种情况：

  1. 若被插入关键字所在的结点，其含有关键字数目小于阶数 M，则直接插入；
  

  2. 若被插入关键字所在的结点，其含有关键字数目等于阶数 M，则需要将该结点分裂为两个结点，一个结点包含 ⌊M/2⌋ ，另一个结点包含 ⌈M/2⌉ 。同时，将⌈M/2⌉的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M，则插入操作完成。

     

  3. 在第 2 情况中，如果上移操作导致其双亲结点中关键字个数大于 M，则应继续分裂其双亲结点。

     

• 删除

  1. 删除该关键字，如果不破坏 B+树本身的性质，直接完成删除操作；
  2. 如果删除操作导致其该结点中最大（或最小）值改变，则应相应改动其父结点中的索引值；
  3. 在删除关键字后，如果导致其结点中关键字个数不足，有两种方法：一种是向兄弟结点去借，另外一种是同兄弟结点合并（情况 3、4 和 5）。（注意这两种方式有时需要更改其父结点中的索引值。）

• 复杂度分析

  B+树 是 B-树的一个升级版本，在存储结构上的变化，由于磁盘页的大小限制，只能读取少量的B-树结点到内存中（因为B-树结点就带有数据，占用更多空间，所以说是 少量）；而B+树就不一样了。因为非叶子结点不带数据，能够一次性读取更多结点进去处理，所以对于同样的数据量， B+树更加 “矮胖”， 性能更好。但是两者在查找、插入和删除等操作的时间复杂度的量级是一致的，均为$O(log_mN)$，其中m是阶数，N是关键字个数

  求查找时间复杂度也就是树的高度。对于B树和B+树来说，树的高度为h，一个节点存储m个关键字，有N个关键字，则满足$N=m^h$，所以$h=log_mN$。同时一个节点中包含的key数量是m，需要$O(m)$的时间复杂度，但是对这些节点key的遍历是放在内存中的，时间可以忽略，我们更加关注的是磁盘IO次数，即树的高度，所以B树和B+树两者在查找、插入和删除等操作的时间复杂度的量级是一致的，均为$O(log_mN)$，其中m是阶数，N是关键字个数

B树比B+树的优势在于：

1. 如果经常访问的数据离根节点很近，而B树的非叶子节点存储关键字数据的地址，所以这种数据检索的时候会要比B+树快。

B+树比B树的优势在于：

1. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;(logn)
2. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，查询区间数据时更方便，数据紧密性很高，缓存的命中率也会比B树高。
3. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
4. 适合区间查询，需要的磁盘IO数少

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

手撕LRU算法#

LRU(Least Recently Used) 即最近最少使用，属于典型的内存淘汰机制。

根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”，其思路如下图所示：

该算法需要达到两个目的：①可以轻易的更新最新的访问数据。②轻易的找出最近最少未使用的数据。所以要用到哈希表+双向链表实现。利用map，获取key对应的value是O(1)，利用双向链表，实现新增和删除都是O(1)。

传统意义的LRU算法是为每一个Cache对象设置一个计数器，每次Cache命中则给计数器+1，而Cache用完，需要淘汰旧内容，放置新内容时，就查看所有的计数器，并将最少使用的内容替换掉。它的弊端很明显，如果Cache的数量少，问题不会很大， 但是如果Cache的空间过大，达到10W或者100W以上，一旦需要淘汰，则需要遍历所有计数器，其性能与资源消耗是巨大的。效率也就非常的慢了。双链表LRU的原理： 将Cache的所有位置都用双链表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。 这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，则向链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

LRU数据结构如下图：

根据上图我们可以分析一下：

1. 如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
2. 对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。
3. 链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。

• 版本1：自己实现循环链表存储，没有用API

  1
  /********************不用API的版本*************************/
  2
  /********************简单说一下思路*************************/
  3
  //1.首先hash表用的是unordered_map来实现，用来查找key对应的node节点，所以hash表应该是[key,node]形式存储
  4
  //2.LRUCache这个类实现双向链表的添加，删除，更新和遍历
  5
  //3.同时这个类还要实现get和put两个功能
  6
  //4.我这里用的是循环双向链表，因此查找链表尾端的元素为O(1)，正常的双向链表是O(n)
  7
  //总结：最重要的就是hash表中的key对应的不是int而是一个node节点，这个要记住
  8
  #include<unordered_map>
  9
  #include<iostream>
  10
  struct Node{
  11
      int key;
  12
      int value;
  13
      Node* pre;
  14
      Node* next;
  15
      Node(){}
  16
      Node(int k, int v):key(k), value(v), pre(nullptr), next(nullptr){}
  17
  };
  18
  
  19
  class LRUCache{
  20
  private:
  21
      //通过key可以找到位于链表中的节点
  22
      std::unordered_map<int, Node*> hash;
  23
      int capacity;
  24
      Node* head_node;
  25
  public:
  26
      LRUCache(int cap){
  27
          capacity = cap;
  28
          head_node = new Node();
  29
          //初始化dummy_Node,next和pre都指向自己
  30
          head_node->next = head_node->pre = head_node;
  31
      }
  32
      //将新来的插入双向链表头部
  33
      void add_Node(Node* n);
  34
      //将某个节点拿出来重新插入头部
  35
      void update_Node(Node* n);
  36
      //移除链表中最后一个（最久未使用）
  37
      void pop_back();
  38
      //输出LRU结构
  39
      void show();
  40
      int get(int key);
  41
      void put(int key, int value);
  42
  };
  43
  
  44
  //注意，该节点可能是新节点，也可能是已经存在的有重新入链表的节点
  45
  void LRUCache::add_Node(Node* n){
  46
      //表示当前节点n就是dummy的next节点，不用加入
  47
      if(n->pre == head_node){
  48
          return;
  49
      }
  50
      //将节点n插入head_node后面
  51
      n->pre = head_node;
  52
      n->next = head_node->next;
  53
      head_node->next->pre = n;
  54
      head_node->next = n;
  55
  }
  56
  
  57
  void LRUCache::update_Node(Node* n){
  58
      //表示当前节点n就是dummy的next节点，不用断掉
  59
      if(n->pre == head_node){
  60
          return;
  61
      }
  62
      n->next->pre = n->pre;
  63
      n->pre->next = n->next;
  64
      add_Node(n);
  65
  }
  66
  
  67
  //弹出链表的最后一个，由于是循环链表，就是head_node->pre
  68
  void LRUCache::pop_back(){
  69
      Node* tmp = head_node->pre;
  70
      head_node->pre = tmp->pre;
  71
      tmp->pre->next = head_node;
  72
      //删除unordered_map中的key
  73
      hash.erase(tmp->key);
  74
  }
  75
  
  76
  void LRUCache::show(){
  77
      //链表中没有节点，退出
  78
      if(head_node->next = head_node){
  79
          return;
  80
      }
  81
      Node* tmp = head_node->next;
  82
      while(tmp->next != head_node){
  83
          std::cout<<"key:"<<tmp->key<<",vlaue:"<<tmp->value<<std::endl;
  84
      }
  85
  }
  86
  int LRUCache::get(int key){
  87
      auto it = hash.find(key);
  88
      if(it == hash.end()){
  89
          std::cout<<"there is no key"<<std::endl;
  90
          return -1;
  91
      }
  92
      //取出key对应的node节点
  93
      Node* node = it->second;
  94
      update_Node(node);
  95
      return node->value;
  96
  
  97
  }
  98
  void LRUCache::put(int key, int value){
  99
      auto it = hash.find(key);
  100
      if(it == hash.end()){
  101
          Node* node = new Node(key, value);
  102
          add_Node(node);
  103
          hash.insert({key, node});
  104
          if(hash.size() > capacity){
  105
  
  106
              pop_back();
  107
          }
  108
      }else{
  109
          it->second->value = value;
  110
          update_Node(it->second);
  111
      }
  112
  }

  展开收起

• 版本2：使用deque，为什么使用deque说的很清楚

  1
  /****************注意unordered_map的插入************/
  2
  
  3
  #include <iostream>
  4
  #include <deque>
  5
  #include <unordered_map>
  6
  #include <list>
  7
  
  8
  class LRUCache{
  9
  private:
  10
      int capacity;
  11
      //1.之所以用deque不用list是因为移除尾部元素的时候，deque方便
  12
      //2.deque里面可以存储自定的node类型，也可以用pair表示，这里我用pair了
  13
      std::deque<std::pair<int, int>> my_deque;
  14
      //通过key找到对应key在deque中的位置
  15
      std::unordered_map<int, std::deque<std::pair<int, int>>::iterator> hash;
  16
  public:
  17
      LRUCache(int cap):capacity(cap){}
  18
      int get(int key);
  19
      void put(int key, int value);
  20
  };
  21
  
  22
  int LRUCache::get(int key){
  23
      if(hash.find(key) == hash.end()){
  24
          std::cout<<"there is no key"<<std::endl;
  25
          return -1;
  26
      }
  27
      std::pair<int, int> tmp = *hash[key];
  28
      my_deque.erase(hash[key]);
  29
      my_deque.push_front(tmp);
  30
      //更新hash表中对应key位于deque的位置
  31
      hash[key] = my_deque.begin();
  32
      return tmp.second;
  33
  }
  34
  
  35
  void LRUCache::put(int key, int value){
  36
      if(hash.find(key) == hash.end()){
  37
          if(my_deque.size() >= capacity){
  38
              //把hash表中的抹除，然后删除deque中的
  39
              auto it = my_deque.back();
  40
              hash.erase(it.first);
  41
              my_deque.pop_back();
  42
              my_deque.push_front({key, value});
  43
              hash.insert({key, my_deque.begin()});
  44
          }else{
  45
              my_deque.push_front({key, value});
  46
              hash.insert({key, my_deque.begin()});
  47
          }
  48
      }else{
  49
          //更新就行
  50
          my_deque.erase(hash[key]);
  51
          my_deque.push_front({key, value});
  52
          //更新hash表中key的位置
  53
          hash[key] = my_deque.begin();
  54
      }
  55
  }

  展开收起

线性对数级排序算法详解（重要！）#