二叉搜索树与平衡二叉搜索树：原理与C++实现详解-北京尧图网络

1. 引言二叉搜索树Binary Search TreeBST和平衡二叉搜索树Balanced Binary Search Tree是数据结构与算法中的核心内容广泛应用于查找、插入、删除等动态数据操作场景。本文将从基本概念出发结合C代码详细讲解二叉搜索树的定义、操作实现以及平衡二叉搜索树以AVL树为例的旋转原理与代码实现。2. 二叉搜索树BST2.1 什么是二叉搜索树二叉搜索树是一棵二叉树它满足以下性质左子树性质任意节点的左子树中所有节点的值都小于该节点的值。右子树性质任意节点的右子树中所有节点的值都大于该节点的值。递归性质左子树和右子树本身也分别是二叉搜索树。基于上述性质二叉搜索树的中序遍历结果是一个递增的有序序列这使得它非常适合用于快速查找和排序相关操作。2.2 二叉搜索树的节点定义在C中我们通常使用结构体或类来定义二叉搜索树的节点。每个节点包含一个键值key以及指向左孩子和右孩子的指针。struct TreeNode { int val; // 节点存储的值 TreeNode* left; // 左孩子指针 TreeNode* right; // 右孩子指针 // 构造函数 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };2.3 二叉搜索树的查找操作查找操作是二叉搜索树最基础的操作。从根节点开始将目标值与当前节点值比较若相等则查找成功若目标值小于当前节点值则递归地在左子树中查找否则递归地在右子树中查找。由于每次比较都能排除一半的子树查找的时间复杂度在理想情况下为 O(log n)。// 在二叉搜索树中查找值为 target 的节点 TreeNode* searchBST(TreeNode* root, int target) { // 当前节点为空说明查找失败 if (root nullptr) { return nullptr; } // 找到目标值返回当前节点 if (root-val target) { return root; } // 目标值小于当前节点值去左子树查找 if (target root-val) { return searchBST(root-left, target); } // 目标值大于当前节点值去右子树查找 return searchBST(root-right, target); }2.4 二叉搜索树的插入操作插入操作同样从根节点开始按照查找的规则找到合适的空位置将新节点作为叶子节点插入。插入后二叉搜索树的性质依然保持。// 向二叉搜索树中插入一个新节点返回插入后的根节点 TreeNode* insertBST(TreeNode* root, int val) { // 找到空位置创建新节点 if (root nullptr) { return new TreeNode(val); } // 待插入值小于当前节点值插入到左子树 if (val root-val) { root-left insertBST(root-left, val); } // 待插入值大于当前节点值插入到右子树 else if (val root-val) { root-right insertBST(root-right, val); } // 值相等时根据需求决定是否处理重复值这里选择忽略 return root; }2.5 二叉搜索树的删除操作删除操作相对复杂需要分三种情况讨论情况一待删除节点是叶子节点直接删除即可。情况二待删除节点只有一个孩子用其孩子节点替代它。情况三待删除节点有两个孩子通常用其左子树中的最大值节点或右子树中的最小值节点来替代它然后删除那个被替代的节点。// 找到以 root 为根的子树中的最小值节点 TreeNode* findMin(TreeNode* root) { while (root-left ! nullptr) { root root-left; } return root; } // 从二叉搜索树中删除值为 val 的节点返回删除后的根节点 TreeNode* deleteBST(TreeNode* root, int val) { if (root nullptr) { return nullptr; } // 待删除值小于当前节点值去左子树删除 if (val root-val) { root-left deleteBST(root-left, val); } // 待删除值大于当前节点值去右子树删除 else if (val root-val) { root-right deleteBST(root-right, val); } // 找到待删除节点 else { // 情况一叶子节点或只有一个右孩子 if (root-left nullptr) { TreeNode* temp root-right; delete root; return temp; } // 情况二只有一个左孩子 if (root-right nullptr) { TreeNode* temp root-left; delete root; return temp; } // 情况三有两个孩子用右子树中的最小值节点替代 TreeNode* minNode findMin(root-right); root-val minNode-val; root-right deleteBST(root-right, minNode-val); } return root; }2.6 二叉搜索树的性能瓶颈二叉搜索树的查找、插入和删除操作的时间复杂度与树的高度密切相关。在理想情况下树是平衡的高度为 O(log n)操作效率很高。但是如果插入的数据本身是有序的例如依次插入 1、2、3、4、5二叉搜索树会退化成一条链表树的高度变为 O(n)此时各种操作的时间复杂度也退化为 O(n)性能大幅下降。为了解决这个问题平衡二叉搜索树应运而生。3. 平衡二叉搜索树以AVL树为例3.1 什么是平衡二叉搜索树平衡二叉搜索树是一种在插入和删除操作后能够自动保持树高度平衡的二叉搜索树。它通过限制左右子树的高度差确保树的高度始终维持在 O(log n) 级别从而保证查找、插入、删除操作的时间复杂度稳定在 O(log n)。常见的平衡二叉搜索树包括 AVL 树、红黑树等。本文以 AVL 树为例进行讲解。3.2 AVL树的定义与平衡因子AVL 树是最早被发明的自平衡二叉搜索树。它在每个节点上维护一个平衡因子Balance Factor定义为左子树高度减去右子树高度。AVL 树要求任意节点的平衡因子的绝对值不超过 1即平衡因子只能取 -1、0 或 1。当插入或删除操作导致某个节点的平衡因子绝对值大于 1 时就需要通过旋转操作来恢复平衡。struct AVLNode { int val; // 节点存储的值 int height; // 以该节点为根的子树高度 AVLNode* left; // 左孩子指针 AVLNode* right; // 右孩子指针 AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {} }; // 获取节点高度空节点高度为 0 int getHeight(AVLNode* node) { return node nullptr ? 0 : node-height; } // 获取节点的平衡因子左子树高度 - 右子树高度 int getBalanceFactor(AVLNode* node) { return node nullptr ? 0 : getHeight(node-left) - getHeight(node-right); } // 更新节点高度 void updateHeight(AVLNode* node) { node-height 1 std::max(getHeight(node-left), getHeight(node-right)); }3.3 AVL树的旋转操作当插入或删除节点导致树失去平衡时需要通过旋转操作来恢复平衡。旋转分为四种基本类型左旋、右旋、左右旋和右左旋。右旋LL型失衡的修复当某个节点的左子树过高且左孩子的左子树也过高时执行右旋操作。// 右旋操作 AVLNode* rotateRight(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; // 执行旋转 x-right y; y-left T2; // 更新高度 updateHeight(y); updateHeight(x); // 返回新的根节点 return x; }左旋RR型失衡的修复当某个节点的右子树过高且右孩子的右子树也过高时执行左旋操作。// 左旋操作 AVLNode* rotateLeft(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; // 执行旋转 y-left x; x-right T2; // 更新高度 updateHeight(x); updateHeight(y); // 返回新的根节点 return y; }左右旋LR型失衡的修复当某个节点的左子树过高但左孩子的右子树过高时先对左孩子执行左旋再对当前节点执行右旋。// 左右旋操作 AVLNode* rotateLeftRight(AVLNode* node) { node-left rotateLeft(node-left); return rotateRight(node); }右左旋RL型失衡的修复当某个节点的右子树过高但右孩子的左子树过高时先对右孩子执行右旋再对当前节点执行左旋。// 右左旋操作 AVLNode* rotateRightLeft(AVLNode* node) { node-right rotateRight(node-right); return rotateLeft(node); }3.4 AVL树的插入操作AVL 树的插入操作分为两步第一步按照普通二叉搜索树的规则插入新节点第二步从插入位置向上回溯更新节点高度并检查平衡因子若失衡则进行相应的旋转修复。// 向AVL树中插入新节点返回插入后的根节点 AVLNode* insertAVL(AVLNode* root, int val) { // 1. 执行普通BST插入 if (root nullptr) { return new AVLNode(val); } if (val root-val) { root-left insertAVL(root-left, val); } else if (val root-val) { root-right insertAVL(root-right, val); } else { // 值已存在不重复插入 return root; } // 2. 更新当前节点高度 updateHeight(root); // 3. 获取平衡因子判断是否失衡 int balance getBalanceFactor(root); // 4. 根据失衡类型进行旋转修复 // 左左型LL左子树过高且左孩子的左子树过高 if (balance 1 val root-left-val) { return rotateRight(root); } // 右右型RR右子树过高且右孩子的右子树过高 if (balance -1 val root-right-val) { return rotateLeft(root); } // 左右型LR左子树过高但左孩子的右子树过高 if (balance 1 val root-left-val) { return rotateLeftRight(root); } // 右左型RL右子树过高但右孩子的左子树过高 if (balance -1 val root-right-val) { return rotateRightLeft(root); } // 未失衡直接返回当前节点 return root; }3.5 AVL树的删除操作AVL 树的删除操作同样分为两步第一步按照普通二叉搜索树的规则删除节点第二步从删除位置向上回溯更新高度并检查平衡因子必要时进行旋转修复。// 从AVL树中删除值为 val 的节点返回删除后的根节点 AVLNode* deleteAVL(AVLNode* root, int val) { // 1. 执行普通BST删除 if (root nullptr) { return nullptr; } if (val root-val) { root-left deleteAVL(root-left, val); } else if (val root-val) { root-right deleteAVL(root-right, val); } else { // 找到待删除节点 if (root-left nullptr || root-right nullptr) { AVLNode* temp root-left ! nullptr ? root-left : root-right; if (temp nullptr) { // 叶子节点 temp root; root nullptr; } else { // 只有一个孩子 *root *temp; } delete temp; } else { // 有两个孩子用右子树中的最小值节点替代 AVLNode* minNode root-right; while (minNode-left ! nullptr) { minNode minNode-left; } root-val minNode-val; root-right deleteAVL(root-right, minNode-val); } } // 如果树为空直接返回 if (root nullptr) { return nullptr; } // 2. 更新当前节点高度 updateHeight(root); // 3. 获取平衡因子 int balance getBalanceFactor(root); // 4. 根据失衡类型进行旋转修复 // 左左型LL if (balance 1 getBalanceFactor(root-left) 0) { return rotateRight(root); } // 左右型LR if (balance 1 getBalanceFactor(root-left) 0) { return rotateLeftRight(root); } // 右右型RR if (balance -1 getBalanceFactor(root-right) 0) { return rotateLeft(root); } // 右左型RL if (balance -1 getBalanceFactor(root-right) 0) { return rotateRightLeft(root); } return root; }3.6 AVL树的遍历与验证为了验证 AVL 树的正确性我们可以实现中序遍历来检查输出是否有序并实现一个检查函数来验证每个节点的平衡因子是否满足 AVL 性质。// 中序遍历输出有序序列 void inorderTraversal(AVLNode* root) { if (root nullptr) { return; } inorderTraversal(root-left); std::cout root-val ; inorderTraversal(root-right); } // 检查是否为合法的AVL树 bool isAVL(AVLNode* root) { if (root nullptr) { return true; } int balance getBalanceFactor(root); // 平衡因子绝对值4. 总结4.1 核心要点回顾二叉搜索树BST通过左小右大的节点组织方式使得查找、插入和删除操作在理想情况下都能达到 O(log n) 的时间复杂度其中序遍历结果天然有序。然而当插入数据本身有序时BST 会退化为链表操作复杂度恶化到 O(n)。平衡二叉搜索树以 AVL 树为例通过维护每个节点的平衡因子左子树高度减右子树高度绝对值不超过 1在插入和删除后自动执行旋转操作恢复平衡从而保证树的高度始终维持在 O(log n) 级别使各项操作的时间复杂度稳定在 O(log n)。4.2 适用场景对比数据结构适用场景优势局限普通二叉搜索树BST数据基本随机、插入删除不频繁、对最坏情况不敏感的场景实现简单内存开销小适合教学和简单应用有序输入下退化为链表最坏时间复杂度为 O(n)AVL 树查找操作远多于插入删除、对查询性能要求严格的场景严格平衡查找性能稳定最坏情况也有保证旋转操作频繁插入删除开销略高实现较复杂红黑树插入删除频繁、需要兼顾查找与写操作性能的场景如 C STL 的 map/set平衡条件较宽松旋转次数少写操作性能更好树高略高于 AVL 树查找性能略逊4.3 选择建议学习与入门优先掌握普通 BST 和 AVL 树理解平衡因子的含义与四种旋转LL、RR、LR、RL的触发条件。查找密集型应用若查询操作远多于插入删除选择 AVL 树可获得最稳定的查找性能。写操作密集型应用若插入删除频繁红黑树因旋转次数更少而整体性能更优这也是 C STL 中 map 和 set 采用红黑树的原因。工程实践多数标准库已内置平衡树实现优先复用成熟容器仅在特殊需求下自行实现。

二叉搜索树与平衡二叉搜索树：原理与C++实现详解

相关推荐

二叉树详解：四种遍历方法及C++代码实现

基于STM32与PID算法的高精度半导体制冷片温控系统设计与实现

Sigrity OptimizePI CapGen实战：基于目标阻抗的PDN去耦电容自动优化

更多资讯

QT for webassembly

C++仿C#实现事件处理

HarmonyOS 开发

C++ 机器学习 dlib 实践

C++ 有向图拓扑排序算法

PIC18F57K42与MAX14431的SPI隔离方案设计与实践

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？