前端面试专栏-算法篇：22.树结构（二叉树、B树、红黑树）-EW帮帮网

🔥 欢迎来到前端面试通关指南专栏！从js精讲到框架到实战，渐进系统化学习，坚持解锁新技能，祝你轻松拿下心仪offer。
前端面试通关指南专栏主页
 前端面试专栏规划详情

树结构（二叉树、B树、红黑树）

在计算机科学中，树结构是一种非常重要的非线性数据结构，它能够高效地组织和存储数据。与线性数据结构如数组和链表相比，树结构具有层级关系，更适用于表示具有父子关系的数据。树结构广泛应用于以下领域：

数据库系统：用于索引实现（如B树、B+树）
文件系统：目录结构组织
搜索引擎：网页排名和索引
网络路由：路由器表查找
人工智能：决策树算法

二叉树

二叉树是最基本的树结构之一，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树有以下几种重要的变种：

完全二叉树

除最后一层外，其他各层的节点数都达到最大值，且最后一层的节点都集中在左侧。这种结构常用于堆的实现。

满二叉树

每一层的节点数都达到最大值。即如果树的高度为h，则节点数为2^h-1。

二叉搜索树(BST)

具有以下性质：

左子树所有节点的值小于根节点的值
右子树所有节点的值大于根节点的值
左右子树也分别为二叉搜索树

二叉搜索树的平均时间复杂度：

查找：O(log n)
插入：O(log n)
删除：O(log n)

但在最坏情况下（如插入有序数据时退化为链表），时间复杂度会降为O(n)。

B树

B树是一种平衡的多路搜索树，主要应用于磁盘存储系统。其特点包括：

节点结构：
- 每个节点最多包含m个子节点（m阶B树）
- 根节点至少有两个子节点（除非它是叶子节点）
- 非根非叶子节点至少有⌈m/2⌉个子节点
操作特性：
- 所有叶子节点位于同一层次
- 插入操作可能导致节点分裂
- 删除操作可能导致节点合并

典型应用场景：

数据库索引（如MySQL的InnoDB存储引擎使用B+树）
文件系统（如NTFS、ReiserFS）

B树与二叉搜索树相比的优势：

减少磁盘I/O次数（一个节点可以存储多个键值）
更适合处理大规模数据
保持平衡的特性保证操作效率

红黑树

红黑树是一种自平衡的二叉搜索树，具有以下性质：

节点着色规则：
- 每个节点是红色或黑色
- 根节点是黑色
- 每个叶子节点（NIL节点）是黑色
- 红色节点的子节点必须是黑色
- 从任一节点到其每个叶子节点的路径包含相同数目的黑色节点
平衡特性：
- 最长路径不超过最短路径的两倍
- 保证基本操作在最坏情况下的时间复杂度为O(log n)
- 通过旋转（左旋/右旋）和重新着色维持平衡

红黑树的应用实例：

Java的TreeMap和TreeSet实现
C++ STL的map和set容器
Linux内核的进程调度
计算几何中的区间树

与其他平衡树的比较：

与AVL树相比，红黑树的平衡要求更宽松，插入/删除操作需要的旋转更少
与B树相比，红黑树更适合内存中的数据结构实现

在实际系统设计中，选择哪种树结构取决于具体应用场景、数据规模和性能要求。理解这些树结构的特点和实现原理，有助于开发高效、稳定的软件系统。

一、二叉树（Binary Tree）

1.1 基本概念

二叉树是一种树形数据结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的定义具有递归性，即一个二叉树要么为空，要么由一个根节点和两棵互不相交的子二叉树组成。这种递归特性使得二叉树非常适合使用递归算法来处理。

二叉树的基本术语：

根节点(Root)：位于树顶端的节点，没有父节点
叶子节点(Leaf)：没有子节点的节点
内部节点：至少有一个子节点的节点
深度(Depth)：从根节点到该节点的路径长度
高度(Height)：从该节点到叶子节点的最长路径
度(Degree)：节点的子节点数目

二叉树的几种特殊形式：

满二叉树：每个节点要么有两个子节点，要么没有子节点。若高度为h，则节点总数为2^h-1
完全二叉树：除了最后一层外，每一层都被完全填充，且最后一层的节点都尽可能靠左。常用于堆的实现
二叉搜索树（BST）：对于每个节点，其左子树的所有节点值小于该节点值，右子树的所有节点值大于该节点值。这种特性使得查找、插入和删除操作的平均时间复杂度为O(log n)

示例：

这是一个典型的二叉搜索树示例，其中：

8是根节点
1、4、7、9、14是叶子节点
节点6的度为2，深度为2，高度为1
满足BST特性：任意节点的左子树节点值都小于它，右子树节点值都大于它

二叉树在计算机领域有广泛应用：

文件系统目录结构
数据库索引(B树、B+树)
编译器中的语法分析树
游戏开发中的决策树
网络路由算法

1.2 二叉搜索树（BST）的实现

以下是二叉搜索树的Python实现，包含节点类和基本操作：

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        """插入新节点"""
        self.root = self._insert_recursive(self.root, key)
    
    def _insert_recursive(self, root, key):
        if root is None:
            return Node(key)
        if key < root.key:
            root.left = self._insert_recursive(root.left, key)
        else:
            root.right = self._insert_recursive(root.right, key)
        return root
    
    def search(self, key):
        """查找节点"""
        return self._search_recursive(self.root, key)
    
    def _search_recursive(self, root, key):
        if root is None or root.key == key:
            return root
        if key < root.key:
            return self._search_recursive(root.left, key)
        return self._search_recursive(root.right, key)
    
    def inorder_traversal(self):
        """中序遍历（升序输出）"""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, root, result):
        if root:
            self._inorder_recursive(root.left, result)
            result.append(root.key)
            self._inorder_recursive(root.right, result)
    
    def min_value_node(self, root):
        """找到最小节点"""
        current = root
        while current.left is not None:
            current = current.left
        return current
    
    def delete(self, key):
        """删除节点"""
        self.root = self._delete_recursive(self.root, key)
    
    def _delete_recursive(self, root, key):
        if root is None:
            return root
        
        if key < root.key:
            root.left = self._delete_recursive(root.left, key)
        elif key > root.key:
            root.right = self._delete_recursive(root.right, key)
        else:
            # 节点只有一个子节点或没有子节点
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            
            # 节点有两个子节点，获取右子树的最小节点
            temp = self.min_value_node(root.right)
            root.key = temp.key
            root.right = self._delete_recursive(root.right, temp.key)
        
        return root

# 使用示例
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print("中序遍历结果:", bst.inorder_traversal())  # 输出: [20, 30, 40, 50, 60, 70, 80]

bst.delete(20)
print("删除20后的中序遍历:", bst.inorder_traversal())  # 输出: [30, 40, 50, 60, 70, 80]

bst.delete(50)
print("删除50后的中序遍历:", bst.inorder_traversal())  # 输出: [30, 40, 60, 70, 80]

1.3 二叉树的应用场景

文件系统目录结构：
现代操作系统普遍采用树形结构管理文件和目录，其中每个目录节点可以包含多个子目录或文件。例如在Linux系统中，根目录"/"作为树的根节点，包含bin、etc、home等子目录，这些子目录又可以继续包含更深层次的子目录，形成一个典型的树形层级结构。这种结构使得文件的查找和管理更加高效。
编译器的语法树：
在编译器设计领域，抽象语法树（AST）是源代码语法结构的树状表示。编译器前端将源代码解析后，会生成一棵语法树，其中每个节点代表一个语法构造。例如对于表达式"3*(4+5)"，编译器会构建一棵二叉树，其中"*“作为根节点，数字"3"和”+“作为子节点，”+"节点又包含"4"和"5"两个子节点。这种树形结构有助于编译器进行语义分析和代码优化。
数据库索引：
数据库系统广泛使用B树和B+树作为索引结构，这些数据结构都是多路平衡树的变种。例如MySQL的InnoDB存储引擎就使用B+树索引，树的高度通常维持在3-4层，这使得即使在上亿条记录中也能快速定位数据。B+树的所有数据都存储在叶子节点，并且叶子节点之间通过指针连接，非常适合范围查询和磁盘I/O优化。
游戏AI：
在游戏人工智能中，决策树和博弈树发挥着重要作用。例如在国际象棋AI中，博弈树用于评估可能的走法，每个节点代表一个棋盘状态，分支代表可能的移动。通过Minimax算法和Alpha-Beta剪枝，AI可以高效地搜索最佳策略。决策树也常用于NPC的行为决策，根据不同条件选择不同行为分支。
数据压缩：
霍夫曼编码是一种经典的无损数据压缩算法，它通过构建最优二叉树来实现。频率高的字符分配较短的编码，频率低的字符分配较长的编码。例如在ZIP压缩格式中，就使用了霍夫曼编码的变种。构建霍夫曼树的过程包括：统计字符频率、构建优先队列、合并节点直至形成完整二叉树，最终生成每个字符的变长编码。

二、B树（B-Tree）

2.1 基本概念

B树（Balance Tree）是一种自平衡的多路搜索树，由Rudolf Bayer和Edward M. McCreight于1972年提出，常用于文件系统和数据库索引。与普通的二叉树不同，B树的每个节点可以有多个子节点（称为阶数，通常用m表示），这使得B树在存储大量数据时能够保持较小的树高度，从而提高磁盘I/O效率。

B树的特点：

多子节点结构：
- 每个内部节点（非根节点）至少有⌈m/2⌉个子节点，最多有m个子节点
- 例如，一个4阶B树（m=4）中，每个节点有2到4个子节点
键值存储方式：
- 每个节点存储k个键值（k-1 <= m-1），其中k值满足⌈m/2⌉-1 <= k <= m-1
- 键值按升序排列，例如一个节点可能存储[10, 20, 30]三个键值
平衡特性：
- 所有叶子节点都位于同一层，确保树的绝对平衡
- 每次插入/删除操作后都会自动进行平衡调整
搜索路径：
- 对于节点中的键值K₁, K₂,…, Kₙ：
  - 小于K₁的键值在第一个子树中
  - 介于Kᵢ和Kᵢ₊₁之间的键值在第i+1个子树中
  - 大于Kₙ的键值在最后一个子树中
- 例如：查找25时，在[10,20,30]节点会进入20和30之间的子树
实际应用：
- 数据库系统（如MySQL的InnoDB引擎）
- 文件系统（如NTFS、ReiserFS）
- 需要大量磁盘读写的场景，因为B树可以减少磁盘访问次数

典型应用示例：在数据库索引中，一个B树节点的大小通常设置为磁盘块大小（如4KB），这样每次磁盘读取可以获取一个完整节点，极大提高了查询效率。

2.2 B树的结构与操作

2.2.1 B树的基本结构

B树是一种平衡的多路搜索树，其阶数(order)定义为每个节点最多可以拥有的子节点数。一个m阶B树需要满足以下结构特性：

节点容量限制：
- 每个节点最多包含m-1个键值(key)和最多m个子节点指针
- 例如，一个5阶B树的节点最多可存储4个键值，最多有5个子节点
节点填充要求：
- 除根节点外，每个非叶子节点至少有⌈m/2⌉-1个键值和⌈m/2⌉个子节点
- 例如5阶B树(⌈5/2⌉=3)的非根节点至少要有2个键值和3个子节点
根节点特例：
- 根节点至少要有1个键值
- 当不是叶子节点时，至少要有2个子节点
平衡性保证：
- 所有叶子节点都位于同一层级
- 树的高度保持平衡，确保操作效率

2.2.2 B树的核心操作

搜索操作：
- 从根节点开始，采用二分查找方式在当前节点查找目标键值
- 若找到则返回；否则根据键值大小选择适当的子节点继续查找
- 示例：在存储学生成绩的B树中查找学号为2023005的记录
插入操作：
- 步骤1：找到合适的叶子节点位置
- 步骤2：插入新键值，保持节点键值有序
- 步骤3：若节点超出容量(m-1个键值)，则进行节点分裂：
  - 将中间键值提升至父节点
  - 分裂剩余键值形成两个新节点
  - 若导致父节点溢出，递归向上分裂
- 应用场景：数据库索引添加新记录时触发的B树调整
删除操作：
- 情况1：删除叶子节点键值
  - 直接删除后检查是否满足最少键值要求
  - 若不满足，考虑向兄弟节点借键值或与兄弟节点合并
- 情况2：删除内部节点键值
  - 用前驱或后继键值替换被删键值
  - 递归处理前驱/后继键值原来的位置
- 合并操作示例：当5阶B树节点键值少于2个时，会与相邻节点合并
维护操作：
- 键值重新分配：在相邻节点间移动键值以保持平衡
- 节点合并：将两个不足的节点合并为一个合法节点
- 树高调整：当根节点被合并时，树的高度会降低

这些操作确保了B树在动态增删数据时始终保持平衡，为数据库系统和文件系统提供了高效的索引结构。典型的应用包括MySQL的InnoDB存储引擎、文件系统如NTFS、HFS+等。

2.3 B树的应用场景

1. 数据库索引

B树及其变种（特别是B+树）是关系型数据库中最常用的索引结构。例如：

MySQL：InnoDB存储引擎默认使用B+树作为索引结构
Oracle：采用B树索引作为主要索引类型
PostgreSQL：实现多种索引类型，其中B树是最基本的形式
SQL Server：同样大量使用B树索引

典型应用场景：

处理范围查询（如WHERE age BETWEEN 20 AND 30）
支持ORDER BY排序操作
实现主键/唯一键约束

2. 文件系统

现代文件系统广泛采用B树结构来组织文件和目录：

Ext4：Linux主流文件系统，使用B树管理目录项
NTFS：Windows NT文件系统采用B+树存储文件索引
ReiserFS：完全基于B*树设计
HFS+：苹果文件系统使用B树存储目录

优势体现：

快速定位文件（O(log n)时间复杂度）
支持大规模目录（百万级文件）
高效处理文件元数据操作

3. 高效存储大量数据

B树的平衡特性使其特别适合处理海量数据存储：

磁盘读写优化：
- 典型节点大小设置为磁盘页大小（如4KB）
- 一次I/O可读取整个节点
- 树高度通常保持3-4层（可存储数十亿记录）

性能对比：

操作类型	哈希表	二叉搜索树	B树
查找	O(1)	O(n)	O(log n)
插入	O(1)	O(n)	O(log n)
范围查询	不支持	O(n)	O(log n + k)

典型应用案例：

分布式存储系统（如Google Bigtable）
时间序列数据库（如InfluxDB）
键值存储系统（如LevelDB）

三、红黑树（Red-Black Tree）

3.1 基本概念

红黑树（Red-Black Tree）是一种高效的自平衡二叉搜索树，由 Rudolf Bayer 在1972年发明。它在普通二叉搜索树的基础上增加了颜色属性（红色或黑色）和一系列平衡规则，通过颜色约束和旋转操作来维持树的相对平衡。

红黑树的关键特性

颜色属性：
- 每个节点存储一个额外的颜色位（通常用1位表示）
- 颜色只能是红色或黑色
- 新插入的节点默认设置为红色（可以减少违反规则的情况）
结构规则：
- 根规则：根节点必须为黑色（确保从根节点出发的路径都满足黑节点数量要求）
- 叶子规则：所有NIL节点（空节点）被视为黑色（为计算黑高度提供统一的基准）
- 红色约束：红色节点的子节点必须为黑色（防止连续红色节点导致路径过长）
- 黑高度一致：从任意节点到其子树中每个NIL节点的路径必须包含相同数量的黑色节点（称为该节点的黑高度）

平衡性保证

这些规则确保了红黑树的关键平衡特性：

最长路径（红黑交替）不超过最短路径（全黑）的两倍
树的高度始终保持在O(log n)级别
查找、插入、删除操作的时间复杂度稳定在O(log n)

应用场景示例

红黑树广泛应用于需要高效查找和动态更新的场景：

Java的TreeMap和TreeSet实现
C++ STL中的map和set容器
Linux内核的进程调度（完全公平调度器使用红黑树管理进程）
文件系统的目录结构管理
数据库索引的实现

通过严格遵守这五条规则，红黑树在动态数据集合的管理中提供了优异的性能表现，成为工程实践中最重要的平衡树结构之一。

3.2 红黑树的操作

红黑树的基本操作（插入、删除、搜索）与二叉搜索树类似，但在插入和删除后需要通过旋转和重新着色来维持红黑树的性质。这些维护操作确保了红黑树始终保持良好的平衡性，使得其最坏情况下的时间复杂度仍为O(log n)。

旋转操作

旋转是红黑树维持平衡的关键操作，分为两种基本类型：

左旋：

设当前节点为x，其右子节点为y
将y提升为新的子树根节点
x成为y的左子节点
y原来的左子节点变为x的右子节点
示例：

    x              y
   / \            / \
  a   y   →      x   c
     / \        / \
    b   c      a   b

右旋：

设当前节点为x，其左子节点为y
将y提升为新的子树根节点
x成为y的右子节点
y原来的右子节点变为x的左子节点
示例：

      x            y
     / \          / \
    y   c  →     a   x
   / \              / \
  a   b            b   c

插入操作

红黑树的插入过程分为两个阶段：

标准插入阶段：
- 按照二叉搜索树的规则找到合适的插入位置
- 创建新节点并初始化为红色（保持性质5）
- 将新节点插入树中
修复阶段（可能需要递归处理）：
- 情况1：新节点是根节点 → 直接染黑
- 情况2：父节点是黑色 → 无需处理
- 情况3：父节点和叔节点都是红色 → 重新着色
- 情况4：父节点红色而叔节点黑色 → 需要旋转
  - 左左或右右情况 → 单旋转
  - 左右或右左情况 → 双旋转

删除操作

删除操作更为复杂，需要考虑多种情况：

标准删除阶段：
- 查找要删除的节点
- 如果节点有两个子节点，找到其前驱/后继替换
- 实际删除该节点（最多一个子节点的情况）
修复阶段（当删除黑色节点时）：
- 情况1：兄弟节点是红色 → 旋转并重新着色
- 情况2：兄弟节点是黑色且其子节点都是黑色 → 重新着色
- 情况3：兄弟节点是黑色且近侄子节点是红色 → 旋转并重新着色
- 情况4：兄弟节点是黑色且远侄子节点是红色 → 旋转并重新着色

应用场景示例：

Java的TreeMap/TreeSet实现
Linux内核的进程调度
文件系统索引
数据库索引结构

每次插入/删除后，最多需要O(log n)次旋转和重新着色操作即可恢复红黑树的性质。

3.3 红黑树的应用场景

红黑树作为一种自平衡的二叉查找树，因其出色的性能特性（插入、删除、查找的时间复杂度均为O(log n)）而被广泛应用于多个领域：

Java集合框架
- TreeMap：基于红黑树实现的有序键值对集合，保持键的自然排序或自定义排序
- TreeSet：基于TreeMap实现的有序集合，常用于需要元素自动排序的场景
- 典型应用：实现有序字典、优先级队列等数据结构
C++标准库
- STL中的map：基于红黑树的有序关联容器，提供高效的键值查找
- STL中的set：基于红黑树的有序集合容器
- 实现特点：保证元素有序的同时，提供O(log n)的查找性能
Linux内核
- 进程调度：用于管理进程描述符，实现高效的进程选择
- 内存管理：组织虚拟内存区域(VMA)，快速查找内存区域
- 文件系统：ext3文件系统用于目录项索引
- 优势：在系统资源有限的环境下仍能保持稳定性能
高效的动态数据存储
- 适用于需要频繁执行以下操作的场景：
  - 动态插入数据（如实时日志处理）
  - 频繁删除数据（如缓存系统）
  - 高频率查找（如数据库索引）
- 对比优势：相比AVL树，红黑树的旋转操作更少，适合写操作频繁的场景
- 实际应用示例：
  - 实时竞价系统(RTB)中的广告库存管理
  - 游戏服务器中的玩家状态管理
  - 金融系统中的实时报价处理
其他领域应用
- 网络路由表：快速查找最优路由路径
- 图形处理：空间分区数据结构
- 编译器实现：符号表管理

四、三种常见树结构的特性对比

特性	二叉树	B树	红黑树
节点子树数量	严格限制为最多2个子节点（左/右）	节点最多可包含m个子树（m为B树阶数），典型数据库实现中m=100-1000	与二叉树相同，最多2个子节点，但通过颜色标记维持平衡
平衡性	无自动平衡机制，可能退化为链表	绝对平衡，通过节点分裂/合并保证所有叶子节点在同一层级	相对平衡，最长路径长度不超过最短路径的2倍
搜索效率	无序二叉树最坏O(n)；有序二叉树（如BST）平均O(log n)但可能退化	稳定O(log n)，因高度可控且节点存储多个键	稳定O(log n)，平衡因子保证树高度
插入/删除效率	无序O(1)；有序BST平均O(log n)但最坏O(n)	稳定O(log n)，需要处理节点分裂/合并	稳定O(log n)，最多需要3次旋转维护平衡
适用场景	表达式树、哈夫曼编码等简单结构；递归算法教学	磁盘存储系统（MySQL索引）、文件系统（NTFS、ReiserFS）	Java TreeMap/TreeSet、C++ STL map/set
空间开销	每个节点仅需存储2个指针（约16字节）	每个节点存储m-1个键和m个指针，空间利用率通常保持在50%-100%	额外1位存储颜色信息，整体空间与二叉树相当
实现复杂度	简单，基础数据结构课程常见示例	中等，需处理多键节点和分裂合并逻辑	较高，需维护颜色属性和旋转规则
典型应用实例	编译器语法分析树、游戏决策树	Oracle/MySQL的B+树索引、MongoDB的B树索引	Linux内核进程调度器、Epoll事件管理

补充说明：

二叉树在完全随机插入时平均性能较好，但面对有序数据会退化为O(n)性能
B树的高分支特性使其特别适合磁盘存储，单节点可存储数百个键，减少IO次数
红黑树的旋转策略包括：左旋、右旋、颜色翻转等，插入最多2次旋转，删除最多3次旋转

五、总结

树结构是计算机科学中非常重要的一类数据结构，不同类型的树在不同场景下发挥着重要作用。二叉树是基础，适合简单的数据组织和递归算法；B树通过多路搜索和平衡特性，在大规模数据存储和数据库索引中表现出色；红黑树则通过颜色标记和旋转操作，在动态数据集合中提供高效的插入、删除和查找操作。

理解各种树结构的特点和适用场景，有助于在实际开发中做出合适的选择。例如，当处理大量磁盘数据时，B树是理想选择；而在内存中实现高效的集合操作时，红黑树更为合适。掌握这些树结构的原理和实现，是成为优秀程序员的重要一步。

本文详细介绍了二叉树、B树和红黑树的基本概念、实现原理和应用场景，并对它们进行了对比分析。通过学习这些树结构，读者可以更好地理解和应用它们解决实际问题。

📌 下期预告：图结构与遍历算法
❤️❤️❤️：如果你觉得这篇文章对你有帮助，欢迎点赞、关注本专栏！后续解锁更多功能，敬请期待！👍🏻 👍🏻 👍🏻
更多专栏汇总：
前端面试专栏
 Node.js 实训专栏

数码产品严选

前端面试专栏-算法篇：22.树结构（二叉树、B树、红黑树）