本文共 2226 字，大约阅读时间需要 7 分钟。

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

定义：

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

插入结点：

二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

删除结点：

在二叉排序树删去一个结点，分三种情况讨论：
1.删除结点为叶子结点，也就是无左右子树；
2.删除结点只有左子树或右子树；
3.删除结点左右子树均不为空。
参考文章：

平衡二叉查找树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。

调整平衡的基本思想：

当在平衡二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。
所谓最小不平衡子树，指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
先插入指定节点，记录下当前节点的信息，LH，EH或者RH。

1. 若左子树高LH，查看其左子树根节点的信息，若是LH，则一次右旋；若是RH，则一次左旋+一次右旋
2. 若右子树高RH，查看右子树根节点的信息，若是RH，则一次左旋；若是LH，则一次右旋+一次左旋
3. 调整改变的节点信息

追求绝对的高度平衡，随着树的高度的增加，动态插入和删除的代价也随之增加。

红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树 。二叉查找树这一数据结构并不难，而红黑树之所以难是难在它还是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

红黑树的性质：

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从性质5又可以推出：
性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

红黑树的其他操作方法及原理参考图文文章： 和文章： 还有文章：。

B树、B-树

B-树就是B树。英文名字叫做B-tree，中间的短线是英文连接符，只是翻译的时候将短线翻译成了减号。
全称Balance-tree(平衡多路查找树)，平衡的意思是左边和右边分布均匀。多路的意思是相对于二叉树而言的，二叉树就是二路查找树，查找时只有两条路，而B-tree有多条路，即父节点有多个子节点。

B-树用途：

使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。这个数据结构一般用于数据库的索引，综合效率较高。

定义：

阶的概念：阶定义为一个节点的子节点数目的最大值。
（1）树中每个结点至多有m 棵子树（注：m指的是树的阶）；
（2）若根结点不是叶子结点，则至少有两棵子树（注：根节点至少有两个儿子）；
（3）除根结点之外的所有非叶子结点至少有p个子节点；
（4）所有的非叶子结点中包含以下数据：（n，A0，K1，A1，K2，…，Kn，An）
其中：
1. Ki（i=1,2,…,n）为关键码，且Ki<Ki+1（注：ki是真实数据，存放在线性表当中，且从左至右升序排列）
2. Ai 为指向儿子的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的 关键码均大于Kn。（注：每个ki数据两旁各安放了一个指针，即Ai-1和Ai，左边的子树数据统统小于ki，右边子树的数据统 统大于ki）（注：总体来看指针数量比数据数量多1）
3. n 为关键码的个数（\left \lceil m/2 \right \rceil-1\leqslant n\leqslant m-1）。
（5）所有的叶子结点都出现在同一层次上，即所有叶节点具有相同的深度，等于树高度。并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

更多详情和操作参考文章：

B+树

B+树是基于B-树的一种变体，有着比B-树更高的查询性能。

定义：

一个m阶的B+树具有如下几个相较于B-树的新特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

更多概念理解参考图文文章：

B+树的实现参考文章：