参考：

• 通过BST,AVL,234树来理解红黑树
• 红黑树增删改查
• 二叉查找（排序）树
• 2-3树与2-3-4树
• B树、B+树详解

一、二叉查找（排序）树

1.概念

（1）.定义

二叉查找树就是一颗二叉树，他的左节点比父节点要小，右节点比父节点要大，它的高度决定查找效率

（2）.特点

• 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；

• 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；

• 二叉排序树的左右子树也要求都是二叉排序树；

2.BST操作

（1）.查找

从根节点开始查找

• 查找值比当前值大，则搜索右子树

• 查找值比当前值小，则搜索左子树

• 查找值等于当前值，停止查找，返回当前节点

（2）.插入

要插入节点，则必须先找到插入节点的位置。    

从根节点开始查找：

• 要插入的值比当前节点的值大，则比较右子树        

• 要插入的值比当前节点的值小，则比较左子树        

• 要插入的值和当前节点的值相等，因为二叉查找树不存在两个相同值的节点，所以不执行插入操作。    

直到比较到左右子树为空时，则插入到对应位置。

（3）.遍历

• 前（根）序遍历：根左右        

• 中（根）序遍历：左根右        

• 后（根）序遍历：左右根

（4）.查找最小值节点

从根节点开始，不断查询当前节点的左子节点，直到最后一个不为空的节点，该节点就是整棵树的最小值节点。

（5）.查找最大值节点

从根节点开始，不断查询当前节点的右子节点，直到最后一个不为空的节点，该节点就是整棵树的最大值节点。

（6）.查找前驱节点

前驱节点：小于当前节点的最大值节点    

即：        

• 当前节点有左子树时，其前驱节点就是其左子树中的最大值节点   

• 当前节点没有左子树，则向上递归到第一次左拐时节点的父节点就是其前驱节点

（7）.查找后继节点

后继节点：大于当前节点的最小值节点    

即：        

• 当前节点有右子树时，其后继节点就是其右子树中的最小值节点

• 当前节点没有右子树时，则向上递归到第一次右拐时节点的父节点就是其后继节点

（8）.删除

删除操作前提：删除要保证删除后，BST树的节点还能保证有序    

删除操作本质：是用被删除节点的前驱节点或者后继节点来替代。        

• 叶子节点直接删除（叶子节点即没有前驱和后继节点的节点）        

• 只有一个子节点的节点被删除，就用它的唯一的子节点来代替。（单子节点即只有前驱节点，或者只有后继节点的节点）        

• 有两个子节点的，需要找到替代节点（双子节点，既有前驱节点，也有后继节点的节点）

二、二叉平衡树

1.概念

（1）.定义

BST有一种极端情况，就是全左倾树，或者全右倾树。

（2）.特点

AVL树是一个高度自平衡的树，即AVL树的根节点的左右子树的高度差不超过绝对值1。且左右子树本身也是二叉平衡树。另外AVL树具备BST树的全部特性。    

AVL树查询的时间复杂度为O（logN）,即每次查询都是二分查找。

2.AVL树的旋转操作

当AVL树中插入新节点时，就可能出现左右子树高度差超过1的情况，此时AVL树就会进行旋转操作，来改变树的结构以保证平衡性，即将左右子树高度差降为1.

（1）.左旋

以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点 的右子节点，左子节点保持不变。

（2）.右旋

以某个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点 的左子节点，右子节点保持不变。

三、B树

1、概念

（1）、定义

B树是一种自平衡树数据结构，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除。B树是二叉搜索树的一般化，因为节点可以有两个以上的子节点。与其他自平衡二进制搜索树不同，B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统。它通常用于数据库和文件系统。

（2）、特点

B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件： 

• 每个节点最多只有m个子节点。

• 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。

• 如果根不是叶节点，则根至少有两个子节点。

• 具有k个子节点的非叶节点包含k -1个键。

• 所有叶子都出现在同一水平，没有任何信息（高度一致）。

2、B+树

（1）、定义

B+树是B树的一种变形，它把所有的卫星数据都存储在叶节点中，内部节点只存放关键字和孩子指针，因此最大化了内部节点的分支因子，所以B+树的遍历也更加高效(B树需要以中序的方式遍历节点，而B+树只需把所有叶子节点串成链表就可以从头到尾遍历)。

（2）、特点

• 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；

• 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；

• 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；

（3）、B+树比B树更适合数据库索引的原因

• B+树的磁盘读写代价更低

• B+树查询效率更加稳定

• B+树便于范围查询（最重要的原因，范围查找是数据库的常态）

四、2-3-4树

1.概念

234树是四阶的平衡树（Balance Tree）,它属于多路查找树

• 所有叶子节点都拥有相同的深度

• 节点只能是2-节点，3-节点，4-节点之一

• 2-节点：包含一个元素的节点，有两个子节点

• 3-节点：包含两个元素的节点，有三个子节点

• 4-节点：包含三个元素的节点，有四个子节点

• 所有节点至少包含一个元素

• 元素始终保持排序顺序，整体上保持二叉查找树的特性，节点的元素大于它的左子树所有节点的元素，小于它的右子树所有节点的元素。当节点有多个元素时，每个元素必须大于它左边和它左子树中的元素。

2.2-3-4树和红黑树的等价关系

• 2-3-4树中2-节点，3-节点，4-节点，虽然各个类型的节点中可以包含多个元素，但是它们本身就只是一个节点，内部的多个元素，会有引用互相关联。

• 红黑树的节点只能是红色或者黑色，且任意相连的两个节点的颜色不都是红色，即红黑树不存在红红相连，只存在红黑相连，黑黑相连。

• 红黑树新加入的节点都当成红色节点

• 红黑树的根节点只能黑色节点

五、红黑树

1.概念

（1）.定义

红黑树是一种节点带颜色属性的二叉查找树。

红黑树的每个节点都有存储为表示节点的颜色，只能是红或者黑。

红黑树的平衡是指任意节点到叶子节点的不同简单路径中所拥有的黑色节点个数相同。

即红黑树的平衡是一种黑色平衡。

（2）.特性

1.红黑树的每个节点只能是红色或者黑色。（非黑即红）

2.根节点必须是黑色。（黑根）

3.每个叶子节点是黑色的。（叶子节点是Nil）（黑叶）

4.如果某个节点是红色，则它的子节点必须是黑色，不能出现两个红色节点相连的情况。（红红互斥）

5.对于每个节点，从该节点到其后代的叶子节点的简单路径上，均包含相同数目的黑色节点。（黑色平衡）

2.红黑树原子行为

（1）.变色

（2）.左旋

（3）.右旋

未完待续