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。

相关文章

MySQL 主从复制部署及验证(示例详解)

MySQL 主从复制部署及验证(示例详解)

《MySQL主从复制部署及验证(示例详解)》本文介绍MySQL主从复制部署步骤及学校管理数据库创建脚本,包含表结构设计、示例数据插入和查询语句,用于验证主从同步功能,感兴趣的朋友一起看看吧... 目录mysql 主从复制部署指南部署步骤1.环境准备2. 主服务器配置3. 创建复制用户4. 获取主服务器状态5
阅读更多...
python生成随机唯一id的几种实现方法

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1：使用 UUID 模块（推荐）方法 2：使用 Secrets 模块（安全敏感场景）方法
阅读更多...
一文详解如何使用Java获取PDF页面信息

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸（宽高）四、获取页面旋转角度五、判断
阅读更多...
Ubuntu 24.04启用root图形登录的操作流程

Ubuntu 24.04启用root图形登录的操作流程

《Ubuntu24.04启用root图形登录的操作流程》Ubuntu默认禁用root账户的图形与SSH登录,这是为了安全,但在某些场景你可能需要直接用root登录GNOME桌面,本文以Ubuntu2... 目录一、前言二、准备工作三、设置 root 密码四、启用图形界面 root 登录1. 修改 GDM 配
阅读更多...
Spring Boot中的路径变量示例详解

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...
C++中assign函数的使用

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)
阅读更多...
MySql基本查询之表的增删查改+聚合函数案例详解

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入（单行/多行及冲突处理）,SELECT实现数据检索（列选择、条件过滤、排序分页）,UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更
阅读更多...
Redis中Stream详解及应用小结

Redis中Stream详解及应用小结

《Redis中Stream详解及应用小结》RedisStreams是Redis5.0引入的新功能,提供了一种类似于传统消息队列的机制,但具有更高的灵活性和可扩展性,本文给大家介绍Redis中Strea... 目录1. Redis Stream 概述2. Redis Stream 的基本操作2.1. XADD
阅读更多...
Spring StateMachine实现状态机使用示例详解

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​，用于描述对象在其生命
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2