最小生成树——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节点当做了叶子节点）

• 左旋和右旋

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

                                 z
     x                          /                  
    / \      --(左旋)-->       x
   y   z                      /
                             y

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

                                 y
     x                            \                 
    / \      --(右旋)-->           x
   y   z                            \
                                     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的基础上进行了优化，增加了顺序访问指针。