C++深入理解AVL树的设计与实现：旋转操作详解

2024-09-02 09:04
文章标签 c++ 实现 设计 详解 操作 深入 理解 旋转 avl

本文主要是介绍C++深入理解AVL树的设计与实现：旋转操作详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++深入理解AVL树的设计与实现：旋转操作详解

AVL树（Adelson-Velsky and Landis Tree）是一种自平衡二叉搜索树，通过在插入和删除节点时进行旋转操作来保持树的平衡。AVL树的每个节点都维护一个平衡因子，即左右子树的高度差，确保其绝对值不超过1。本文将详细介绍如何实现一个AVL树，并提供旋转操作的实现细节。

一、AVL树的基本概念

AVL树是一种高度平衡的二叉搜索树，其特点是每个节点的左右子树高度差不超过1。AVL树的平衡性保证了其查找、插入和删除操作的时间复杂度为O(log n)。

二、AVL树的节点设计

在C++中，我们可以使用类来定义AVL树的节点。每个节点包含数据域、左子节点指针、右子节点指针和高度信息。以下是节点类的定义：

class AVLNode {
public:int key;int height;AVLNode* left;AVLNode* right;AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};
三、AVL树的类设计

AVL树类需要包含根节点指针，并提供插入、删除和查找操作的接口。以下是AVL树类的定义：

class AVLTree {
private:AVLNode* root;// 辅助函数int height(AVLNode* node);int getBalance(AVLNode* node);AVLNode* rightRotate(AVLNode* y);AVLNode* leftRotate(AVLNode* x);AVLNode* insert(AVLNode* node, int key);AVLNode* minValueNode(AVLNode* node);AVLNode* deleteNode(AVLNode* root, int key);public:AVLTree() : root(nullptr) {}void insert(int key);void deleteNode(int key);void inOrder();void preOrder();void postOrder();
};
四、旋转操作的实现

AVL树的旋转操作包括右旋、左旋、左右旋和右左旋。旋转操作用于在插入或删除节点后恢复树的平衡。

  1. 右旋操作：
AVLNode* AVLTree::rightRotate(AVLNode* y) {AVLNode* x = y->left;AVLNode* T2 = x->right;// 执行旋转x->right = y;y->left = T2;// 更新高度y->height = max(height(y->left), height(y->right)) + 1;x->height = max(height(x->left), height(x->right)) + 1;// 返回新的根节点return x;
}
  1. 左旋操作：
AVLNode* AVLTree::leftRotate(AVLNode* x) {AVLNode* y = x->right;AVLNode* T2 = y->left;// 执行旋转y->left = x;x->right = T2;// 更新高度x->height = max(height(x->left), height(x->right)) + 1;y->height = max(height(y->left), height(y->right)) + 1;// 返回新的根节点return y;
}
  1. 获取节点高度：
int AVLTree::height(AVLNode* node) {if (node == nullptr) return 0;return node->height;
}
  1. 获取节点平衡因子：
int AVLTree::getBalance(AVLNode* node) {if (node == nullptr) return 0;return height(node->left) - height(node->right);
}
五、插入操作的实现

插入操作需要在插入新节点后检查并恢复树的平衡。以下是插入操作的实现：

AVLNode* AVLTree::insert(AVLNode* node, int key) {// 1. 执行标准的BST插入if (node == nullptr) return new AVLNode(key);if (key < node->key) {node->left = insert(node->left, key);} else if (key > node->key) {node->right = insert(node->right, key);} else {return node; // 不允许插入重复键}// 2. 更新节点高度node->height = 1 + max(height(node->left), height(node->right));// 3. 获取节点平衡因子int balance = getBalance(node);// 4. 检查平衡因子并进行相应的旋转操作// LL情况if (balance > 1 && key < node->left->key) {return rightRotate(node);}// RR情况if (balance < -1 && key > node->right->key) {return leftRotate(node);}// LR情况if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);return rightRotate(node);}// RL情况if (balance < -1 && key < node->right->key) {node->right = rightRotate(node->right);return leftRotate(node);}return node;
}void AVLTree::insert(int key) {root = insert(root, key);
}
六、删除操作的实现

删除操作需要在删除节点后检查并恢复树的平衡。以下是删除操作的实现：

AVLNode* AVLTree::deleteNode(AVLNode* root, int key) {// 1. 执行标准的BST删除if (root == nullptr) return root;if (key < root->key) {root->left = deleteNode(root->left, key);} else if (key > root->key) {root->right = deleteNode(root->right, key);} else {if ((root->left == nullptr) || (root->right == nullptr)) {AVLNode* temp = root->left ? root->left : root->right;if (temp == nullptr) {temp = root;root = nullptr;} else {*root = *temp;}delete temp;} else {AVLNode* temp = minValueNode(root->right);root->key = temp->key;root->right = deleteNode(root->right, temp->key);}}if (root == nullptr) return root;// 2. 更新节点高度root->height = 1 + max(height(root->left), height(root->right));// 3. 获取节点平衡因子int balance = getBalance(root);// 4. 检查平衡因子并进行相应的旋转操作// LL情况if (balance > 1 && getBalance(root->left) >= 0) {return rightRotate(root);}// LR情况if (balance > 1 && getBalance(root->left) < 0) {root->left = leftRotate(root->left);return rightRotate(root);}// RR情况if (balance < -1 && getBalance(root->right) <= 0) {return leftRotate(root);}// RL情况if (balance < -1 && getBalance(root->right) > 0) {root->right = rightRotate(root->right);return leftRotate(root);}return root;
}void AVLTree::deleteNode(int key) {root = deleteNode(root, key);
}
七、遍历操作的实现

为了验证AVL树的正确性，我们可以实现中序、前序和后序遍历操作：

void inOrderHelper(AVLNode* root) {if (root != nullptr) {inOrderHelper(root->left);cout << root->key << " ";inOrderHelper(root->right);}
}void AVLTree::inOrder() {inOrderHelper(root);cout << endl;
}void preOrderHelper(AVLNode* root) {if (root != nullptr) {cout << root->key << " ";preOrderHelper(root->left);preOrderHelper(root->right);}
}void AVLTree::preOrder() {preOrderHelper(root);cout << endl;
}void postOrderHelper(AVLNode* root) {if (root != nullptr) {postOrderHelper(root->left);postOrderHelper(root->right);cout << root->key << " ";}
}void AVLTree::postOrder() {postOrderHelper(root);cout << endl;
}
八、完整代码示例

以下是完整的AVL树实现代码：

#include <iostream>
using namespace std;class AVLNode {
public:int key;int height;AVLNode* left;AVLNode* right;AVLNode(int k) : key(k),好的，我们继续实现AVL树的完整代码：```cpp
#include <iostream>
using namespace std;class AVLNode {
public:int key;int height;AVLNode* left;AVLNode* right;AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};class AVLTree {
private:AVLNode* root;int height(AVLNode* node) {if (node == nullptr) return 0;return node->height;}int getBalance(AVLNode* node) {if (node == nullptr) return 0;return height(node->left) - height(node->right);}AVLNode* rightRotate(AVLNode* y) {AVLNode* x = y->left;AVLNode* T2 = x->right;x->right = y;y->left = T2;y->height = max(height(y->left), height(y->right)) + 1;x->height = max(height(x->left), height(x->right)) + 1;return x;}AVLNode* leftRotate(AVLNode* x) {AVLNode* y = x->right;AVLNode* T2 = y->left;y->left = x;x->right = T2;x->height = max(height(x->left), height(x->right)) + 1;y->height = max(height(y->left), height(y->right)) + 1;return y;}AVLNode* insert(AVLNode* node, int key) {if (node == nullptr) return new AVLNode(key);if (key < node->key) {node->left = insert(node->left, key);} else if (key > node->key) {node->right = insert(node->right, key);} else {return node;}node->height = 1 + max(height(node->left), height(node->right));int balance = getBalance(node);if (balance > 1 && key < node->left->key) {return rightRotate(node);}if (balance < -1 && key > node->right->key) {return leftRotate(node);}if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);return rightRotate(node);}if (balance < -1 && key < node->right->key) {node->right = rightRotate(node->right);return leftRotate(node);}return node;}AVLNode* minValueNode(AVLNode* node) {AVLNode* current = node;while (current->left != nullptr) {current = current->left;}return current;}AVLNode* deleteNode(AVLNode* root, int key) {if (root == nullptr) return root;if (key < root->key) {root->left = deleteNode(root->left, key);} else if (key > root->key) {root->right = deleteNode(root->right, key);} else {if ((root->left == nullptr) || (root->right == nullptr)) {AVLNode* temp = root->left ? root->left : root->right;if (temp == nullptr) {temp = root;root = nullptr;} else {*root = *temp;}delete temp;} else {AVLNode* temp = minValueNode(root->right);root->key = temp->key;root->right = deleteNode(root->right, temp->key);}}if (root == nullptr) return root;root->height = 1 + max(height(root->left), height(root->right));int balance = getBalance(root);if (balance > 1 && getBalance(root->left) >= 0) {return rightRotate(root);}if (balance > 1 && getBalance(root->left) < 0) {root->left = leftRotate(root->left);return rightRotate(root);}if (balance < -1 && getBalance(root->right) <= 0) {return leftRotate(root);}if (balance < -1 && getBalance(root->right) > 0) {root->right = rightRotate(root->right);return leftRotate(root);}return root;}void inOrderHelper(AVLNode* root) {if (root != nullptr) {inOrderHelper(root->left);cout << root->key << " ";inOrderHelper(root->right);}}void preOrderHelper(AVLNode* root) {if (root != nullptr) {cout << root->key << " ";preOrderHelper(root->left);preOrderHelper(root->right);}}void postOrderHelper(AVLNode* root) {if (root != nullptr) {postOrderHelper(root->left);postOrderHelper(root->right);cout << root->key << " ";}}public:AVLTree() : root(nullptr) {}void insert(int key) {root = insert(root, key);}void deleteNode(int key) {root = deleteNode(root, key);}void inOrder() {inOrderHelper(root);cout << endl;}void preOrder() {preOrderHelper(root);cout << endl;}void postOrder() {postOrderHelper(root);cout << endl;}
};int main() {AVLTree tree;tree.insert(10);tree.insert(20);tree.insert(30);tree.insert(40);tree.insert(50);tree.insert(25);cout << "中序遍历: ";tree.inOrder();cout << "前序遍历: ";tree.preOrder();cout << "后序遍历: ";tree.postOrder();tree.deleteNode(40);cout << "删除40后的中序遍历: ";tree.inOrder();return 0;
}
九、总结

本文详细介绍了如何实现一个AVL树，并提供了旋转操作的实现细节。通过右旋、左旋、左右旋和右左旋操作，我们可以在插入和删除节点后保持树的平衡。AVL树在实际应用中具有广泛的用途，例如数据库索引、内存管理等。希望本文对你理解AVL树的实现有所帮助，并能在面试中展示你的编程能力和对C++语言特性的理解。

如果你有其他问题或需要进一步的帮助，请随时告诉我！😊

这篇关于C++深入理解AVL树的设计与实现：旋转操作详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1129555。

相关文章

mybatis执行insert返回id实现详解

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID：1. ​​useGeneratedKeys+keyProperty（推
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Python通用唯一标识符模块uuid使用案例详解

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数
阅读更多...
Linux在线解压jar包的实现方式

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》：本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u
阅读更多...
Linux系统性能检测命令详解

Linux系统性能检测命令详解

《Linux系统性能检测命令详解》本文介绍了Linux系统常用的监控命令（如top、vmstat、iostat、htop等）及其参数功能,涵盖进程状态、内存使用、磁盘I/O、系统负载等多维度资源监控,... 目录toppsuptimevmstatIOStatiotopslabtophtopdstatnmon
阅读更多...
java使用protobuf-maven-plugin的插件编译proto文件详解

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》：本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件
阅读更多...
Android ClassLoader加载机制详解

Android ClassLoader加载机制详解

《AndroidClassLoader加载机制详解》Android的ClassLoader负责加载.dex文件,基于双亲委派模型,支持热修复和插件化,需注意类冲突、内存泄漏和兼容性问题,本文给大家介... 目录一、ClassLoader概述1.1 类加载的基本概念1.2 android与Java Class
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
Java中的数组与集合基本用法详解

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2