当前位置：首页 > news >正文

树、二叉树、二叉查找树、AVL 树及红黑树的深入解析

news 来源：原创 2025/9/13 23:25:37

树、二叉树、二叉查找树、AVL 树及红黑树的深入解析

- 1 .树的基本知识
- - 1.1 树的定义
  - 1.2 基本术语和概念
  - 1.3 常见树的结构
  - 1.4 树的遍历（取决于什么时候访问根节点）
- 2 二叉树
- - 2.1 二叉树的定义
  - 2.2二叉树与度为2的树的区别
  - 2.3二叉树的性质
  - 2.4 二叉树分类
- 3 红黑树
- - 3.1 红黑树的定义
  - 3.2 黑红树的代码实现
  - 3.3 左旋和右旋(无需涉及到颜色变化)
  - 4.4 应用场景以及性能分析

1 .树的基本知识

1.1 树的定义

树是n（n≥0）结点的有限集合。n=0时，称为空树。
在任意以可非空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根结点的子树。

请添加图片描述显然，树的定义是递归的，是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：
1）树的根结点没有前驱结点，除根结点外的所有结点有且只有一个前驱结点。
2）树中所有结点可以有零个或多个后继结点。

1.2 基本术语和概念

请添加图片描述

祖先结点与子孙结点：
以结点K为例，根A到结点K的唯一路径上的任意结点，称为结点K的祖先结点。
如结点B、A都是结点K的祖先结点，而结点K是结点B的子孙结点。
双亲结点、孩子结点与兄弟结点：
以结点K为例，路径上最接近结点K的结点E称为结点K的双亲结点，而结点K为结点E的孩子结点。
根A是树中唯一没有双亲的结点。
有相同双亲的结点称为兄弟结点。如结点K和结点L有相同的双亲结点E，即K和L为兄弟结点
结点的度与树的度：
树中一个结点的子结点的个数称为该结点的度。
树中结点的最大度数称为树的度。
如结点B的度为2，结点D的度为3，树的度为3。
分支结点与叶子结点：
度大于0的结点称为分支结点（又称非终端结点），度为0（没有孩子结点）的结点称为叶子结点（又称终端结点）。
在分支结点中，每个结点的分支数就是该结点的度。
结点的深度、高度和层次：
结点的层次从根开始定义，根结点为第1层（有些地方将根结点定义为第0层），它的子结点为第2层，以此类推。
结点的深度是从根结点开始自顶向下逐层累加的。
结点的高度是从叶结点开始自底向上逐层累加的。
树的高度（又称深度）是树中结点的最大层数。如上图树的高度为4。
有序树和无序树：
树中结点的子树从左到右是有次序的，不能交换，这样的树称为有序树，有序树中，一个结点的子结点按照从左到右的顺序出现是有关联的，反之则称为无序树。上图所示的树就是一棵有序树，若将子结点的位置互换，则变成一棵不同的树。
路径和路径长度：
树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
在上图中，结点A和结点K的路径长度为3，中间经过结点B和结点E。
注意：由于树中的分支是有向的，即从双亲结点指向孩子结点，所以树中的路径是从上向下的，同一双亲结点的两个孩子结点之间不存在路径。
森林：
森林是m（m≥0）棵互不相交的树的集合。
森林的概念和树的概念十分相近，只要把树的根结点删去就成了森林。反之，只要给n棵独立的树加上一个结点，并把这n棵树作为该结点的子树，则森林就变成了树。

1.3 常见树的结构

二叉树：每个节点最多有两个子树的树结构，分别称为左子树和右子树。二叉树具有一些特殊的性质，如在第 i 层上最多有 2^(i - 1) 个节点（i≥1）；深度为 k 的二叉树最多有 2^k - 1 个节点（k≥1）等。
哈夫曼树：一种带权路径长度最短的二叉树，常用于数据编码和压缩等领域。
B 树：一种平衡的多路查找树，常用于文件系统和数据库系统中，以提高数据的存储和检索效率。

1.4 树的遍历（取决于什么时候访问根节点）

前序遍历：先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。对于二叉树，其访问顺序是根节点、左子节点、右子节点。
中序遍历：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。对于二叉树，其访问顺序是左子节点、根节点、右子节点。
后序遍历：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。对于二叉树，其访问顺序是左子节点、右子节点、根节点。
层序遍历：从根节点开始，按照从上到下、从左到右的顺序依次访问树中的每个节点。

2 二叉树

2.1 二叉树的定义

二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；活着左、右子树皆为空。
请添加图片描述

2.2二叉树与度为2的树的区别

1 度为2的的树必须有三个节点以上(否则就不叫度为二了，一定要先存在)，二叉树可以为空。
2 二叉树的度不一定为2,比如斜树。
3 二叉树有左右节点区分，而度为2的树没有左右节点的区分。

2.3二叉树的性质

性质1：二叉树第i层上的节点数目最多为 $2^{i-1}$ (i≥1)。
性质2：深度为k的二叉树至多有 $2^k-1$ 个节点（k>=1）。
性质3：包含n个节点的二叉树的高度至少为 $log_{2}(n + 1)$
性质4：在任意一颗二叉树中，若终端节点的个数为 $n_{0}$ ，度为2的节点数为 $n_{2}$ ，则 $n_{0}$ = $n_{2}$ +1

2.4 二叉树分类

满二叉树
高度为h，并且由 $2^{h} –1$ 个结点的二叉树，被称为满二叉树数学公式
请添加图片描述
完全二叉树
一颗二叉树中，只有最下面一层的度可以小于2，并且最下层的叶节点集中在靠左的若干位置上。

二叉查找树
二叉查找树是一种二叉树，它满足对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。即中序遍历为顺序
请添加图片描述

代码实现

// 定义二叉查找树的节点结构体
typedef struct TreeNode {int data;               // 节点存储的数据struct TreeNode *left;  // 指向左子节点的指针struct TreeNode *right; // 指向右子节点的指针
} TreeNode;// 定义二叉查找树的结构体
typedef struct BinarySearchTree {TreeNode *root; // 指向根节点的指针
} BinarySearchTree;

其实你构建一个树和链表差不多，先构建节点再构建树

性能分析(增删查改都一样)

然二叉查找树在理想情况下，节点均匀分布时具有较好的查找性能，其高度与平衡树相近，查找操作的时间复杂度也是 $O (l o g n)$ 。但在最坏情况下，例如插入节点的顺序是有序的，二叉查找树会退化为一条链，此时树的高度为 n，查找操作的时间复杂度会退化为 $(O (n)$

平衡二叉搜索树
平衡二叉树搜索树：又被称为AVL(Adelson-Velsky and Landis)树，且具有以下性质：它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树请添加图片描述

性能分析

平衡二叉搜索树在查找、插入和删除操作上都具有 $(O (l o g n)$ 的时间复杂度，空间复杂度为 $O (n)$ 。这使得它在处理动态数据集（需要频繁进行插入、删除和查找操作）时表现出良好的性能，能够高效地完成各种操作。

3 红黑树

黑红树太重要了所有单开一节

3.1 红黑树的定义

理解平衡二叉树的不足：平衡二叉树（如 AVL 树）能保证树的高度平衡，左右子树高度差绝对值不超过 1，查找效率稳定$ O(log n))。但插入和删除操作可能导致频繁的旋转来维持平衡，在树的深度很大时，调整效率较低
红黑树是一种特殊的平衡二叉查找树变体，通过对节点着色及一些规则约束，在一定程度上放宽了平衡条件，降低了调整平衡的代价，提高了插入和删除操作的效率

在这里插入图片描述
红黑树的性质

节点是红色或黑色。
根节点是黑色。
每个叶节点（NIL 节点，空节点）是黑色的。
如果一个节点是红色的，则它的子节点必须是黑色的，即父子节点之间不能出现两个连续的红节点。
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

3.2 黑红树的代码实现

#define RED     0#define BLACK   1typedef int KEY_TYPE;typedef struct _rbtree_node {//rbtreeunsigned char color;struct rbtree_node *parent;struct rbtree_node *left;struct rbtree_node *right;// endKEY_TYPE key; void* val；// value//
} rbtree_node;struct rbtree {rbtree_node *root;rbtree_node *nil; // NULL
};

typedef int KEY_TYPE 拓展类型
key-val 值
引进nil节点

简化边界条件处理
在红黑树的操作（如插入、删除、查找等）中，经常需要处理节点为空的情况。如果不使用 nil 节点，对于空指针的处理往往需要额外的条件判断，这会使代码变得复杂且容易出错。而引入 nil 节点后，可以将所有原本为空指针的情况统一用 nil 节点来表示，简化了代码逻辑。

3.3 左旋和右旋(无需涉及到颜色变化)

概念
在这里插入图片描述
左旋（Left Rotate）

操作对象与目的：图中左旋操作 LeftRotate(T, x) 是以节点 x 为中心进行的。目的是通过调整节点之间的链接关系，改变二叉查找树的局部形态，在红黑树等自平衡二叉树中，常用来维护树的平衡性质。
操作过程：
- 节点 x 的右子节点 y 成为新的子树的根节点。
- y 的左子节点 b 变为 x 的右子节点，即 x.right = y.left 。
- x 成为 y 的左子节点，也就是 y.left = x 。

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {// NULL --> T->nilif (x == T->nil) return ;// 1rbtree_node *y = x->right;//y 的左子节点 b 变为 x 的右子节点 ，即 x.right = y.leftx->right = y->left;if (y->left != T->nil) {y->left->parent = x;}// 节点 x 的右子节点 y 成为新的子树的根节点y->parent = x->parent;if (x->parent == T->nil) {T->root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}// x 成为 y 的左子节点，也就是 y.left = xy->left = x;x->parent = y;}

发现其实就是3条边再变

右旋（Right Rotate）

操作对象与目的：右旋操作 RightRotate(T, y) 是以节点 y 为中心。同样也是用于调整二叉查找树的局部结构，在自平衡二叉树中协助维持平衡。
操作过程：
- 节点 y 的左子节点 x 成为新子树的根节点。
- x 的右子节点 b 变为 y 的左子节点，即 y.left = x.right 。
- y 成为 x 的右子节点，也就是 x.right = y 。

void rbtree_right_rotate(rbtree *T, rbtree_node *y) {// NULL --> T->nilif (y == T->nil) return ;// 1rbtree_node *x = y->left;y->left = x->right;if (y->left != T->nil) {y->left->parent = x;}// 2y->parent = x->parent;if (x->parent == T->nil) {T->root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}// 3y->left = x;x->parent = y;}

至于其他操作你想要详细了解
详解红黑树

4.4 应用场景以及性能分析

应用场景

应用领域	具体应用场景	红黑树发挥的作用
数据结构	C++ STL 的 `map` 和 `set`、Java 的 `TreeMap` 和 `TreeSet`	实现高效的键值对存储、查找，维持元素有序性，时间复杂度为 $O(\log n)$
操作系统	Linux 进程调度	快速插入新进程、查找高优先级进程，实现高效资源分配
	Linux 虚拟内存管理	快速定位虚拟地址所属区域，提升内存管理效率
数据库	数据库索引	在数据插入、删除时保持平衡，快速定位数据记录，提升查询性能
网络服务器	Nginx 定时器管理	高效查找即将发生的定时事件，处理超时和定时操作
	Nginx 流量控制	快速查找并更新客户端状态信息，实现限流功能
交易系统	高频交易和大规模交易系统	按指标对交易订单排序，快速处理订单的增删查操作
算法实现	与动态维护平衡相关的算法	优化算法性能，确保操作高效执行

性能分析
以下是二叉搜索树、AVL树和红黑树的对比：

类型	二叉搜索树	AVL树	红黑树
定义与特性	每个节点的左子树所有节点值小于该节点值，右子树所有节点值大于该节点值	是一种高度平衡的二叉搜索树，任意节点的左右子树高度差绝对值不超过1	是一种自平衡的二叉搜索树，通过节点着色和特定规则保证树的平衡
平衡策略	无显式平衡策略，插入和删除节点后可能导致树不平衡	插入或删除节点后，通过旋转操作使树在高度上保持平衡	通过节点着色（红或黑）以及一些规则，如根节点为黑色、红色节点的子节点为黑色等，在插入和删除时进行有限的旋转和颜色调整来维持平衡
插入操作时间复杂度	平均 $O(\log n)$ ，最坏 $O (n)$	$O(\log n)$	$O(\log n)$
删除操作时间复杂度	平均 $O(\log n)$ ，最坏 $O (n)$	$O(\log n)$	$O(\log n)$
查找操作时间复杂度	平均 $O(\log n)$ ，最坏 $O (n)$	$O(\log n)$	$O(\log n)$
适用场景	数据相对静态，插入和删除操作较少，对查找性能要求不特别高，且不需要严格保证最坏情况下性能的数据处理场景，如简单的数据存储和偶尔的查找场景	对查找性能要求极高，且数据相对稳定，插入和删除操作不频繁的场景，如硬件资源有限且对实时性要求高的系统中，处理少量但频繁查找的数据	数据动态变化频繁，同时对查找性能有一定要求，能容忍一定程度的不平衡以换取更好的插入和删除性能的场景，如各种系统中的数据结构、数据库索引等
空间复杂度	$O (n)$	$O (n)$	$O (n)$
实现复杂度	较低，只需遵循二叉搜索树的基本规则进行节点的插入、删除和查找操作	较高，需要额外的代码来维护树的高度平衡，在插入和删除节点后要进行复杂的旋转操作	中等，需要实现节点着色和一些相对简单的平衡调整规则，相比AVL树，旋转操作通常较少

树、二叉树、二叉查找树、AVL 树及红黑树的深入解析

1 .树的基本知识

1.1 树的定义

1.2 基本术语和概念

1.3 常见树的结构

1.4 树的遍历（取决于什么时候访问根节点）

2 二叉树

2.1 二叉树的定义

2.2二叉树与度为2的树的区别

2.3二叉树的性质

2.4 二叉树分类

3 红黑树

3.1 红黑树的定义

3.2 黑红树的代码实现

3.3 左旋和右旋(无需涉及到颜色变化)

4.4 应用场景以及性能分析

相关文章：