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。

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3
阅读更多...
Springboot处理跨域的实现方式(附Demo)

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》：本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.
阅读更多...
Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE？1.2 SSE 的优点1.3 适用场景2. Spring WebFlu
阅读更多...
基于SpringBoot实现文件秒传功能

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.
阅读更多...
Java利用JSONPath操作JSON数据的技术指南

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath？3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4
阅读更多...
SpringBoot日志配置SLF4J和Logback的方法实现

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一：初识日志三、案例二：使用Lombok输出日志四、案例三：配置Logback一
阅读更多...
springboot security快速使用示例详解

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》：本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s
阅读更多...
Python如何使用__slots__实现节省内存和性能优化

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景：内存吃得满满的类__slots__：你的内存管理小助手举个大概的例子：看看效果如何？1.
阅读更多...
Python+PyQt5实现多屏幕协同播放功能

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述：突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专
阅读更多...
Python中随机休眠技术原理与应用详解

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2