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

AVL树和红黑树的特性以及模拟实现

news 2025/7/27 14:30:05

 

目录

AVL树的特性

红黑树和 AVL 树都是计算机科学中常用的自平衡二叉搜索树，它们通过特定的平衡规则维持树的结构，确保插入、删除、查找等操作的时间复杂度稳定在O(log n)（n 为节点数量）

1.AVL树的特性

 AVL 树是最早发明的自平衡二叉搜索树，其核心特性围绕 “节点高度平衡” 展开

  1. 二叉搜索树的基础特性

    • 对于任意节点，其左子树中所有节点的值均小于该节点的值；右子树中所有节点的值均大于该节点的值。

  2. 平衡条件：左右子树高度差不超过 1

    • 每个节点的平衡因子（左子树高度 - 右子树高度）的绝对值必须≤1。
    • 节点的 “高度” 指从该节点到最远叶子节点的路径长度（叶子节点高度为 0，空节点高度为 - 1）。

  3. 失衡后的调整：旋转操作

    • 当插入或删除节点导致平衡因子绝对值＞1 时，通过旋转（左旋、右旋、左右旋、右左旋）恢复平衡。
      • 例如：左左失衡（左子树的左子树过高）→ 右旋；右右失衡→左旋；左右失衡→先左旋后右旋；右左失衡→先右旋后左旋。

  4. 优点与缺点

    • 优点：平衡度高，查找效率稳定（因为树的高度严格控制在 O (log n)）。
    • 缺点：插入和删除操作频繁时，旋转次数多（维护成本高），适合查询多、修改少的场景。

AVL树的模拟实现 

#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;template<class K, class V>
struct AVLTreeNode
{pair<K, V>_kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;//balace factor//拷贝构造AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//链接父亲cur->_parent = parent;//控制平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){//更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){//继续更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//不平衡，需要旋转if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}// 右旋转void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;subL->_parent = pParent;}else{pParent->_right = subL;subL->_parent = pParent;}}subL->_bf = 0;parent->_bf = 0;}//左旋转void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pParent==nullptr ){_root = subR;subR->_parent = nullptr;}else{if (parent == pParent->_left){pParent->_left = subR;subR->_parent = pParent;}else{pParent->_right = subR;subR->_parent = pParent;}}subR->_bf = 0;parent->_bf = 0;}//左右旋转void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);// 就是这个位置了}}//右左旋转void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else if(bf == 1){subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else{assert(false);}}//AVL的查找 Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}//析构AVL树~AVLTree(){_DestoryAVLTree(_root);}void InOrder(){_Inorder(_root);cout << endl;}int Height(){return _Height(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}int Size(){return _Size(_root);}private:void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << ':' << root->_kv.second<<endl;_Inorder(root->_right);}int _Height(Node* root){if (root == nullptr){return 0;}int leftHeight = _Height(root->_left);int rightHright = _Height(root->_right);return leftHeight > rightHright ? leftHeight + 1 : rightHright + 1;}int _Size(Node* root){if (root == nullptr){return 0;}return _Size(root->_left)+_Size(root->_right) + 1;}//判断树是不是AVL树bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}void _DestoryAVLTree(Node* root){if (root == nullptr){return;}_DestoryAVLTree(root->_left);_DestoryAVLTree(root->_right);delete root;}private:Node* _root = nullptr;
};

 2.红黑树的特性

 红黑树通过 “颜色标记” 和一系列规则维持平衡，平衡条件比 AVL 树宽松，核心是确保 “最长路径不超过最短路径的 2 倍”

        

  1. 二叉搜索树的基础特性

    • 与 AVL 树一致，左子树值＜节点值＜右子树值。

  2. 颜色规则

    • 每个节点要么是红色，要么是黑色。
    • 根节点必须是黑色。
    • 叶子节点（NIL 节点，空节点）必须是黑色（实际实现中可能省略，仅逻辑上存在）。
    • 如果一个节点是红色，其两个子节点必须是黑色（即：不存在连续的红色节点）。
    • 从任意节点到其所有叶子节点的路径中，黑色节点的数量相同（称为 “黑高” 相等）。

  3. 失衡后的调整：变色与旋转

    • 插入或删除节点后，若违反颜色规则，通过变色（改变节点颜色）和旋转（同 AVL 树的四种旋转）恢复平衡。
    • 插入时新节点默认为红色（减少对黑高的影响），若父节点为红色（违反 “无连续红节点” 规则），则触发调整（如：叔叔节点为红则变色，叔叔节点为黑则旋转 + 变色）。

  4. 优点与缺点

    • 优点：插入和删除时旋转次数少（平均 1-2 次），维护成本低，适合修改频繁的场景（如集合、映射等数据结构）。
    • 缺点：平衡度不如 AVL 树严格，极端情况下查找效率略低于 AVL 树，但仍为 O (log n)。

红黑树的模拟实现 

#pragma onceenum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}// 链接父亲cur->_parent = parent;// 父亲是红色，出现连续的红色节点，需要处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){//   g// p   uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//     g//   p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//   g// u   pNode* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//   g// u   p//       cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool isbalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}private:bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历走到空时，意味着一条路径走完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}private:Node* _root = nullptr;
};

 

特性AVL树红黑树
树高严格 O (log n)（更矮）O (log n)（可能稍高）
旋转次数插入最多 2 次，删除可能更多插入最多 2 次，删除最多 3 次
平衡依据节点平衡因子（高度差≤1）颜色规则（最长路径≤最短路径 ×2）
空间开销需存储每个节点的高度信息需存储颜色标记
使用场景查询操作频繁插入 / 删除频繁

总的来说：

1.AVL 树是 “严格平衡” 的二叉树，适合查询密集型场景，代价是修改操作效率低。

2.红黑树是 “近似平衡” 的二叉树，修改操作效率更高，在实际工程中应用更广泛（如 C++ STL 的 map/set、Linux 内核、Java 的 TreeMap 等）。

3.两者本质都是通过平衡规则避免二叉搜索树退化为链表（O (n) 复杂度），但平衡策略的宽松程度决定了它们的适用场景差异。

 

http://www.lryc.cn/news/599336.html

相关文章：

  • 【开发杂谈】用AI玩AI聊天游戏：使用 Electron 和 Python 开发大模型语音聊天软件
  • golang怎么实现每秒100万个请求（QPS）,相关系统架构设计详解
  • MyBatis 之缓存机制核心解析
  • “磁”力全开：钕铁硼重塑现代科技生活
  • 求职招聘小程序源码招聘小程序开发定制
  • 解密国密 SSL 证书：SM2、SM3、SM4 算法的协同安全效应
  • Spring Boot 接口安全设计：接口限流、防重放攻击、签名验证
  • SEC_FirePower 第二天作业
  • 软件异常读写威胁硬盘安全：从过往案例到防护之道
  • Linux运维新人自用笔记（Rsync远程传输备份，服务端、邮箱和客户端配置、脚本）
  • 网络资源模板--基于Android Studio 实现的天气预报App
  • Inception网络架构：深度学习视觉模型的里程碑
  • Java-Properties类和properties文件详解
  • android app适配Android 15可以在Android studio自带的模拟器上进行吗，还是说必须在真机上进行
  • 【Android Studio】安装Trae插件后Android Studio 启动崩溃问题处理
  • AR眼镜重塑外科手术导航：精准“透视”新突破
  • 深入理解 TCP 协议：从原理到实践的技术解析
  • 机器学习之knn算法保姆级教学
  • 扣子平台之提示词生成
  • 双指针算法介绍及使用（下）
  • 进阶向:基于Python的局域网聊天工具（端对端加密）
  • Amazon Bedrock中的Stability AI文本转图像模型：技术原理、应用实践与未来趋势
  • 创始人IP：知识变现的核心资产
  • RAG实战指南 Day 24：上下文构建与提示工程
  • winform表格DataGridView多个单元格批量输入数字
  • 瑞萨电子RA-T MCU系列新成员RA2T1——电机控制专家
  • MySQL性能优化配置终极指南
  • 详谈OSI七层模型和TCP/IP四层模型以及tcp与udp为什么是4层，http与https为什么是7层
  • Kotlin 数据容器 - List（List 概述、创建 List、List 核心特性、List 元素访问、List 遍历）
  • STM32与ADS1220实现多通道数据采集的完整分析和源程序