数据结构 - 树的分类

野性酷女 2024-04-20 09:03 67阅读 0赞

#### 文章目录 ####

*  1. 树的分类
 *  2. 二叉树
 *   *   *  2.1 AVL Tree
         *  2.2 R-B Tree
 *  3. 多叉树
 *   *   *  3.1 B-Tree
         *  3.2 B+Tree

## 1. 树的分类 ##

根据树分支的数量限制，可以将树结构分为两类：

*  **二叉树**：二叉树也就是一个节点最多只有两个子节点的树结构，比较有代表的如 红黑树
 *  **多叉树**：多叉树一个节点可以有多于两个的子节点，典型如 B树

根据树节点的有序性，可以将树结构分为另外两类：

*  **查找树**：也可以叫搜索树，基本特征为任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值
 *  **无序树**：节点的键值无特定大小关系

## 2. 二叉树 ##

#### 2.1 AVL Tree ####

AVL树是一种自平衡二叉查找树，其定义如下：

1.  它的左子树和右子树都是AVL树
2.  左子树和右子树的高度差不能超过 1

在AVL树中任何节点的两个子树的高度差最大为1，所以它也被称为高度平衡树。为了保证平衡，AVL树中的每个节点都有一个平衡因子（balance factor，用BF表示），它表示这个结点的左、右子树的高度差，即左子树高度减去右子树高度的结果值。AVL 树上所有结点的BF值只能是-1、0、1，如果二叉树上一个结点的BF绝对值大于1，则该二叉树就不是 AVL 树。

AVL 树增加和删除节点可能需要通过多次旋转操作使树结构重新达到平衡，故其增删效率较低，但平衡后降低树了的高度，提高了其搜索性能。

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

#### 2.2 R-B Tree ####

`红黑树(Red-Black Tree，简称R-B Tree)`，是一种特殊的二叉查找树，同时它只要求部分地达到平衡，任何不平衡都会在三次旋转之内解决，故其增删效率相对 AVL 树更高，查询效率则稍逊。

红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)，其特性如下：

1.  每个节点或者是黑色，或者是红色
2.  根节点是黑色
3.  每个叶子节点是黑色
4.  如果一个节点是红色的，则它的子节点必须是黑色的
5.  从一个节点到其左右子树叶节点的所有路径上包含相同数目的黑节点

关于它的特性，需要注意的是：

1.  特性(3) 中的叶子节点是只为空(NIL或null)的节点
2.  特性(5) 确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对接近平衡的二叉树

红黑树的左旋操作如下，`对一个 节点 x 的左旋操作需要保证 x 有右子节点 y，过程为将 x 作为旋转顶端，x向左移动到其左子节点位置，其右子节点 y 向上移动到 x 原来的位置`

/**
         * 对红黑树的节点(x)进行左旋转
         *
         * 左旋示意图(对节点x进行左旋)：
         *      px                              px
         *     /                               /
         *    x                               y
         *   /  \      --(左旋)----->        /  \              
         *  lx   y                          x   ry
         *     /   \                       / \
         *    ly   ry                     lx  ly
         *
         *
         */

红黑树的右旋操作示意如下，其实就是和左旋相反

![在这里插入图片描述][20190921105819716.gif]

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

## 3. 多叉树 ##

#### 3.1 B-Tree ####

m 阶 B-Tree: m 为一个节点最大子节点个数，可参考 [MySQL 索引原理][MySQL]

一个m 阶 B树是一个多叉平衡搜索树，其要么是一棵空树，要么是满足以下条件的树:

1.  结点最多有m个分支
2.  根结点最少有两个分支，非根非叶结点至少有ceil(m/2)个分支
3.  结点内关键字递增排序
4.  一个结点有n-1个关键字，则该结点有n个分支，将关键字一一隔开
5.  结点中任何一个关键字，其左边分支上的结点值都小于这个关键字，右边分支的结点值都大于这个关键字
6.  叶子结点处于同一层

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

#### 3.2 B+Tree ####

B+ 树是应文件系统所需而产生的一种B树的变种，一颗 m 阶的B+树和 m 阶的B树的差异在于：

1.  有n棵子树的结点中含有n个关键字
2.  所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
3.  所有的内结点可以看成是索引部分，结点中仅含有其子树（根节点）中最大（或最小）关键字

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/730ff5ddb0644c0293a406f3fcaa8ec5.png
[20190921105819716.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/186161e7043c49fd9fe5c9f73c3fbdd2.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6fc35329566c4658973307651ea1dda5.png
[MySQL]: https://blog.csdn.net/weixin_45505313/article/details/99178748#22__14
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/39bad4ae1c4e4c38abd872b63f4579f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/fb4ed4fbcba7478fb554a5f4fbfe839a.png