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。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2