二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树概念的简单区分

一时失言乱红尘 2021-10-19 09:38 343阅读 0赞

### 文章目录 ###

*   *  1、二叉树（Binary Tree）
     *  2、二叉搜索树（Binary Search Tree）
     *  3、平衡二叉树（AVL Tree）
     *  4、红黑树（Red-Black Tree）
     *  5、B树（Balance tree）
     *  6、B+树（B+ tree）

## 1、二叉树（Binary Tree） ##

二叉树是每个节点最多有两个子节点的树。  
二叉树的叶子节点有0个字节点，二叉树的根节点或者内部节点有一个或者两个字节点。

![img][]

## 2、二叉搜索树（Binary Search Tree） ##

二叉搜索树， 又叫 二叉查找树，

它或者是一棵空树，或者是具有下列性质的二叉树：

*  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 *  它的左、右子树也分别为二叉搜索树。  
    ![img][img 1]

一个印象比较深的二叉搜索树就是问手机号。  
假设你遇到一个美女想问他手机号，但是美女一般不告诉你数字。她只回答是否题。  
那么你可以问她不超过14个问题就可以知道她手机号了。

假定手机号最大值是1000 0000 0000  
是否大于500 0000 0000，开始分叉。  
如果大于500 0000 0000，那么是否大于750 0000 0000。。。  
如果小于500 0000 0000，那么是否大于250 0000 0000。。。

以此类推，这就是一个典型的二叉搜索树。看起来很神奇，其实源自于一种巧妙的数学。

## 3、平衡二叉树（AVL Tree） ##

平衡二叉树 全称叫做 `平衡二叉搜索（排序）树`，简称 AVL树。

AVL 什么意思？  
AVL 是大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写，他们提出的平衡二叉树的概念，为了纪念他们，将 平衡二叉树 称为 AVL树。

AVL树本质上是一颗二叉查找树，

AVL树的特性：

*  它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
 *  左右两个子树 也都是一棵平衡二叉树。

在AVL树中，任何节点的两个子树的高度最大差别为 `1` ，所以它也被称为平衡二叉树 。

**如下图：**  
根节点左边高度是3，因为左边最多有3条边；右边高度而2，相差1。  
根节点左边的节点50的左边是1条边，高度为1，右边有两条边，高度为2，相差1。  
![img][img 2]

## 4、红黑树（Red-Black Tree） ##

红黑树是一种含有红、黑结点，并能自平衡的二叉查找树，其性质如下：

1、每个结点或是红色的，或是黑色的  
2、根节点是黑色的  
3、每个叶结点（NIL）是黑色的  
4、如果一个节点是红色的，则它的两个儿子都是黑色的。  
5、对于每个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]

## 5、B树（Balance tree） ##

B树，也叫 B tree、B-树、B\_树。

B树是一种平衡的多路查找树、m阶树 (m>=3)

B树的定义：

1、根结点至少有两个子节点；

2、每个非叶子节点（根节点除外）最少有m/2个子节点，即内部节点的子节点个数最少也有m/2个。

3、根节点最少有两个子节点。

4、有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。

5、所有叶子节点在同一层，即所有叶子几点高度一致。

如下图（B树的内部节点可以存放数据，类似ZK的中间节点一样。B树不是每个节点都有足够多的子节点）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 1]

## 6、B+树（B+ tree） ##

B+树是从B树的变体。  
跟B树的不同：

1、B+树非叶子节点不存放数据，只存放keys（索引数据）。  
2、B+树的叶子节点之间存在指针相连，而且是单链表。

如下图（其实B+树上二叉搜索树的扩展，二叉搜索树是每次一分为二，B树是每次一分为多）

现代操作系统中，磁盘的存储结构使用的是B+树机制，mysql的innodb引擎的存储方式也是B+树机制

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 2]

[img]: /images/20211018/02a8ebd504ee4a1e892a85883613cdc9.png
[img 1]: /images/20211018/731519d0580040cb9b98f759b02229ae.png
[img 2]: /images/20211018/58681488e88a469abe96c5a1bf330e55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]: /images/20211018/5f1217abfd934323aa8cc249c143f939.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 1]: /images/20211018/c0fe5e106cc7420e9832f0d9977e39ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 2]: /images/20211018/149991a8b7de48b387dae18d5c0e52df.png