二叉查找树

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点（no duplicate nodes）。

AVL完全平衡的二叉查找树

平衡条件

左子树和右子树都是高度平衡的二叉树；<br />左子树和右子树的高度之差的绝对值不超过1。

平衡调整

1.旋转的目的就是减少高度，通过降低整棵树的高度来平衡。
2.哪边的子树高，就把那边的子树向上旋转。
3.找离新插入的节点最近的不平衡的树进行调整

插入

例如对于被破坏平衡的节点 a 来说：

LL右旋

“C”节点右单旋即将“C”节点提高，原本它的父节点“E”则变为其右子节点，“C”节点原来的右子节点则变为其父节点“E”的左子节点。右单旋后的结果如下，重新达到了平衡。

RR左旋

G”节点左单旋即将“G”节点提高，原本它的父节点“E”则变为其左子节点，“G”节点原来的左子节点则变为其父节点“E”的右子节点。左单旋后的结果如下，重新达到了平衡。

LR左右双旋

遍历过程会检查哪里不平衡，检查到“B”节点和“G”节点的高度差大于1，而且插入节点“C”属于“E”节点的左子树的右子树，于是进行左右双旋，
1.先以“D”节点为轴进行左单旋
2.再以“D”节点为轴进行右单旋

RL右左双旋

1.先以“F”节点为轴进行右单旋
2.再以“F”节点为轴进行左单旋

删除

删除叶子节点

叶子节点删除是最简单的情况，由于叶子节点没有左右子树，删除后不会破坏原有的树形结构，所以我们只需要找到节点并且把它置为null即可。

删除的节点只有一个子节点

比如我们要删除上图中3所在的节点，3只有一个左子树1。
实际上我们只需要把5所在节点的左子树指向原来3的左子树即可。

删除的节点左右子树都有

由于二叉查找树的性质，如果将当前节点替换为左子树中最大的或者右子树中最小的一定不会破坏二叉查找树的结构。

红黑树

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：

每个结点要么是红的要么是黑的。  
根结点是黑的。  
每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。  
如果一个结点是红的，那么它的两个儿子都是黑的。  
对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

最短路径：一定是纯黑色的
最长路径：一定是红黑相间（这里要保证上面的第四条性质）

插入

新插入节点时，都插入红色节点。
cur：新插入节点
parent：新插入节点的父亲
garndfather：新插入节点的父亲的父亲
uncle：新插入节点的父亲的兄弟

插入数据不需要调整

1.插入节点的父节点是黑色
不会影响平衡，直接插入就行

插入数据需要调整

1.父亲为红，叔叔为红

1.将父亲，叔叔节点调整为黑色
2.将爷爷节点调整为红色

2.父亲为红，叔叔为黑，父节点的右子节点

1.右旋
2.交换以前的父结点P和祖父结点G的颜色

2.父亲为红，叔叔为黑，父节点的左子节点

1.左旋
2.右旋
2.交换以前的父结点P和祖父结点G的颜色

删除

1.被删结点无子结点，且被删结点为红色。

此时直接将结点删除即可，不破坏任何红黑树的性质。

2.被删结点无子结点，且被删结点为黑色

方形结点代表要删除的节点
2.1brother为黑色，且brother有一个与其方向一致的红色子结点son

2.2brother为黑色，且brother有一个与其方向不一致的红色子结点son

2.3brother为黑色，且brother无红色子结点


2.4brother为红色，则father必为黑色。**

3.被删结点有一个子结点，且被删结点为黑色

被删结点node的另一个子结点value必然为红色，此时直接将node删掉，用value代替node的位置，并将value着黑即可。

4.被删结点有两个子结点，且被删结点为黑色或红色

当被删结点node有两个子结点时，先要找到这个被删结点的后继结点successor，然后用successor代替node的位置，同时着成node的颜色，此时相当于successor被删。

B树(B-tree)

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构

规则

1.排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
2.子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
3.关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
4.所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;
最后我们用一个图和一个实际的例子来理解B树（这里为了理解方便我就直接用实际字母的大小来排列C>B>A）

B树的查询流程

如上图我要从上图中找到E字母，查找流程如下
（1）获取根节点的关键字进行比较，当前根节点关键字为M，E（2）拿到关键字D和G，D（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

B树的插入节点流程

定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则：

（1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
（2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;
先插入 3、8、31、11

再插入23、29

再插入50、28

B树节点的删除

遵循规则：

（1）节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
（2）满足节点本身比左边节点大，比右边节点小的排序规则;
（3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；

特点：
B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;

B+树

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别

规则

（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
（4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

特点

1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B*树

规则

B树是B+树的变种，相对于B+树他们的不同之处如下：
（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b树的初始化个数为（cei(2/3m)）
（2）B+树节点满时就会分裂，而B树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；
特点
在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；