经典数据结构：二叉查找树、平衡二叉树、红黑树、B树、B+树、B*树的定义及解惑

我会带着你远行 2022-04-25 03:28 199阅读 0赞

**1、二叉搜索树（BST）**  
二叉搜索树的英文名是Binary Search Tree，简称 BST，它是一棵二叉树，具有如下性质：

1.  若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.  若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.  左、右子树也分别为二叉搜索树；
4.  没有键值相等的节点（因此，插入的时候一定是叶子节点）。

注意：在有些博客中将二叉搜索树成为 B 树，这是存在严重的错误的。B 树是指多路搜索树，不是指二叉搜索树。

**2、平衡二叉树（AVL树）**  
平衡二叉搜索树，又被称为 AVL 树，有别于AVL算法，具有以下性质：

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

常用算法有红黑树、Treap、伸展树等。在平衡二叉搜索树中，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。

**3、红黑树**  
红黑树是一种自平衡的二叉搜索树，除了符合二叉搜索树的基本特性外，它还具有以下性质：

1.  节点是红色或者黑色的；
2.  根结点是黑色的；
3.  每个叶子节点都是黑色的空节点（ NIL 节点或者 NULL 节点）；
4.  每个红色节点的两个子节点都是黑色的，从每个叶子节点到根的所有路径上不能有两个连续的红色节点；
5.  从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

**4、B树**  
B 树，英文名：B-tree，一种平衡的多叉树，有时翻译为B-树、B\_树，它们指是同一个该概念。一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是具有以下性质的树：

1.  根结点至少有两个子女；
2.  每个中间节点都包含 k-1 个元素和 k 个孩子，其中 m/2 <= k <= m；
3.  每一个叶子节点都包含 k-1 个元素，其中 m/2 <= k <= m；
4.  所有的叶子结点都位于同一层；
5.  每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

**5、B+树**  
B+ 树，英文名：B+ -tree，是 B 树的一种变形树，一棵 m 阶的 B+ 树和 m 阶的 B 树的差异在于：

1.  n棵子树的结点中含有n个关键字 （而B 树是n棵子树有n-1个关键字）；
2.  所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接 （而B 树的叶子节点并没有包括全部需要查找的信息）；
3.  所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字（而B 树的非终节点也包含需要查找的有效信息）。

**6、B\*树**  
B\* 树，英文名：B\*-tree，是B+树的变体，它在 B+ 树的基础上增加了如下性质：

1.  非根和非叶子结点增加了指向兄弟节点的指针；
2.  每个中间节点都包含 k 个元素和 k 个孩子，其中`（2/3）*m <= k <= m`，即节点的最低使用率为2/3（代替B+树的1/2）。

后续文章会对以上数据结构进行详细的介绍。文章内容仅代表个人观点，如有不正之处，欢迎批评指正，谢谢大家。