图源:文心一言
考研笔记整理1w+字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝
第1版:查资料、写BUG、画导图、画配图~🧩🧩
参考用书:王道考研《2024年 数据结构考研复习指导》
参考用书配套视频:7.3_2 平衡二叉树_哔哩哔哩_bilibili
特别感谢: Chat GPT老师、文心一言老师~
📇目录
📇目录
🦮思维导图
🧵基本概念
⏲️定义
🌰推算举栗
⌨️代码实现
🧵分段代码
🔯P0:调用库文件
🔯P1:定义结点
🔯P2:读取、写入结点的高度
🔯P3:计算结点的平衡因子
🔯P4:结点旋转操作
🔯P5:调整平衡操作
🔯P6:插入结点
🔯P0-P6附录:构造二叉树
🔯P7:寻找最小结点
🔯P8:结点删除
🔯P9:树的遍历
🔯P10:main函数
🧵完整代码
🔯P0:完整代码
🔯P1:执行结果
🔚结语
🦮思维导图
备注:
- 思维导图为整理王道教材第7章 查找的所有内容;
- 本篇仅涉及到平衡二叉排序树(AVL)的代码;
- 系列博文有朴素二叉排序树的说明🌸数据结构07:查找[C++][朴素二叉排序树BST],后期会在博文列表中整理红黑树的相关内容[交可爱Ada小助手布置的红黑树作业],也可能会增加B树、线性查找的相关内容~ //咳咳,上篇博文800阅读+2个赞+2个收藏足以让一个菜鸟博主开心得老~泪~纵~横~了~~
🧵基本概念
⏲️定义
- 平衡二叉排序树,若树非空,满足下列特性:
- 是一棵朴素二叉排序树🌸数据结构07:查找[C++][朴素二叉排序树BST];
- 在插入和删除结点时,要保证任意结点的左、右子树高度差的绝对值不能超过1。
树的插入操作:
- 与结点进行比较,小于则向左子树遍历,大于则向右子树遍历,直到遍历为空结点时,为叶子结点的预插入路径。
- 需要检查插入结点后是否会导致树不平衡。如果导致不平衡,需要调整子树的形态,直到其满足平衡二叉树定义为止。
平衡树的定义,可见🌸数据结构05:树与二叉树[C++]
🌰推算举栗
- 输入序列为{15、3、7、10、9、8}:
- 插入结点时,若不调整平衡度,有时容易形成度为1的长树,如左图;
- 插入结点时,若调整平衡度,可每次近似形成度为2的宽树,如右图~
// 备注:至于左侧这棵树调整为右侧这棵树的过程,我们会在本博文代码块“插入”操作中介绍~
- ASL:平均查找长度,计算方式为 Σ(第 i 层结点数 x i 的层高)/ (结点个数),表示整棵树所有查找过程中,进行关键字比较次数的平均值~
- 通过图中比较,可知:
- 左侧树的查找:接近链表,与顺序查找相似,时间复杂度近似O(n);
- 右侧树的查找:接近平衡树,与折半查找相似,时间复杂度近似O(log n);
- 因此,朴素二叉排序树的查找的时间复杂度接近O(log n)~
下面我们以图中左侧的小树为例,说明如何创建及遍历平衡二叉排序树~
图源:文心一言
⌨️代码实现
🧵分段代码
🔯P0:调用库文件
- 输入输出流文件iostream{本代码用于输入与输出};
- 动态数组的向量文件vector{本代码用于创建树结点的动态数组};
- 基础算法函数文件algorithm{本代码用于计算比较结点子树的高度}~
#include <iostream>
#include <vector>
#include <algorithm>
🔯P1:定义结点
相比朴素二叉排序树,平衡二叉排序树需要增加结点的1个属性height:以当前结点为根结点的子树高度,以保证树的平衡性~
struct AVLNode {
int data; //数据域
int height; //子树高度
AVLNode* left; //左孩子指针
AVLNode* right; //右孩子指针
AVLNode(int value) : data(value), height(1), left(nullptr), right(nullptr) {}
}; //将构造函数的参数value赋给data,height初始化为1,左left、右孩子right置空
树的高度计算有点类似于这样子:查询左、右子树的高度,选择较高的子树+1作为本结点的高度~
🔯P2:读取、写入结点的高度
- 读取树的高度:查询结点中的node属性~
- 写入树的高度:查询左子树的高度与右子树的高度,左、右子树中更高的值,并+1返回到本结点的高度~
// 读取结点的高度
int getHeight(AVLNode* node) {
if (node == nullptr)
return 0;
return node->height; //查询结点node中height属性的高度
}
// 更新结点的高度
void updateHeight(AVLNode* node) {
if (node == nullptr)
return;
node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1; //将左子树、右子树中更高的height赋值到当前结点
}
🔯P3:计算结点的平衡因子
- 结点平衡因子 = 左子树高度 - 右子树高度;
int getBalanceFactor(AVLNode* node) {
if (node == nullptr)
return 0;
return getHeight(node->left) - getHeight(node->right); //返回左子树高度-右子树高度
}
🔯P4:结点旋转操作
当子树的高度不平衡时(子树的平衡度>|1|),会出现度为1的现象,需要对树进行调整,目的是让树变宽;而平衡调整的基本操作是旋转,如下——
- 左子树不平衡:当前结点移动到右子树的位置,在图中类似于右旋的操作~
- 右子树不平衡:当前结点移动到左子树的位置,在图中类似于左旋的操作~
如果我没有理解错的话,非常简单版本的左旋、右旋,大概是这样的——
注意:括号内是平衡因子,计算公式=左子树高-右子树高~
// 右旋操作
AVLNode* rotateRight(AVLNode* node) {
AVLNode* leftChild = node->left; //定义左孩子结点
node->left = leftChild->right; //将当前结点的左指针指向左子结点的右指针
leftChild->right = node; //将左孩子结点的右指针指向当前结点
updateHeight(node); //更新当前结点高度
updateHeight(leftChild); //更新左子结点高度
return leftChild; //返回左子结点
}
// 左旋操作
AVLNode* rotateLeft(AVLNode* node) {
AVLNode* rightChild = node->right; //定义右孩子结点
node->right = rightChild->left; //将当前结点的右指针指向右子结点的左指针
rightChild->left = node; //将右孩子结点的左指针指向当前结点
updateHeight(node); //更新当前结点高度
updateHeight(rightChild); //更新右子结点高度
return rightChild; //返回右子结点
}
🔯P5:调整平衡操作
封装旋转的操作以后,此处我们正式介绍一下,当树出现不平衡时应该怎么调整~
因为是二叉树,只有两个孩子,所以插入结点可以汇总为四种情况——
- 左左型:插入到结点左子树的左子树,导致不平衡,需要右旋;
- 左右型:插入到结点左子树的右子树,导致不平衡,需要先左旋后右旋;
- 右左型:插入到结点右子树的左子树,导致不平衡,需要先右旋后左旋;
- 右右型:插入到结点右子树的右子树,导致不平衡,需要左旋;
考虑到左左型、右右型互为镜像操作 ,左右型、右左型互为镜像操作,此处以左左型与左右型举栗简单说明树的旋转调整过程~
左左型举栗:以下图为例,稍微复杂一点的左左型树,例如结点1插在结点2的左孩子导致不平衡,根结点向右旋转的操作分为3步:
- 结点4挂到结点5的左孩子;
- 结点5挂到结点3的右孩子;
- 更新子树高度,返回根结点~
以上都是调用P4右旋结点的操作完成~
注意:此处新增结点无论是挂在结点2的左孩子或是右孩子,都属于左左型;根据二叉排序树的性质,挂在结点2的左孩子数值m满足“m<2”,挂在结点2右孩子数值n满足“2<n<3”~
左右型举栗:以下图为例,稍微复杂一点的左右型树,例如结点3插在结点4的左孩子导致不平衡,需要根结点的左孩子先向左旋转,根结点再向右旋转:
- 结点2左旋,使结点4可以挂在结点5的下方,具体操作如下:
- 结点3挂到结点2的右孩子;
- 结点2挂到结点4的左孩子;
- 结点4挂到结点5的左孩子;
- 结点5右旋,使整棵树达到平衡,此处操作同左左型旋转~
- 更新子树高度,返回根结点~
注意:此处新增结点无论是挂在结点4的左孩子或是右孩子,都属于左右型;根据二叉树的性质,挂在结点4的左孩子数值m满足“2<m<4”,挂在结点4右孩子数值n满足“4<n<5”~
// 平衡操作
AVLNode* balanceNode(AVLNode* node) {
if (node == nullptr)
return nullptr;
updateHeight(node);
// 检查平衡因子
int balanceFactor = getBalanceFactor(node);
// 左左型,进行右旋
if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0)
return rotateRight(node);
// 右右型,进行左旋
if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0)
return rotateLeft(node);
// 左右型,先左旋再右旋
if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// 右左型,先右旋再左旋
if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
// 结点平衡,无需调整
return node;
}
🔯P6:插入结点
同朴素二叉树,采用递归的方式创建树,插入的结点通常为叶节点,然后完成调整平衡:
- 若二叉排序树为空,则创建根结点;若结点为空,则插入结点。
- 若二叉树不为空:
- 关键字 = 根结点值,树中已有此元素;
- 关键字<根结点值,继续遍历左子树;
- 关键字>根结点值,继续遍历右子树。
AVLNode* insertNode(AVLNode* root, int data) {
if (root == nullptr)
return new AVLNode(data);
if (data < root->data)
root->left = insertNode(root->left, data);
else if (data > root->data)
root->right = insertNode(root->right, data);
else
return root; // 重复值,不进行插入
return balanceNode(root);
}
🔯P0-P6附录:构造二叉树
本来想封装个构造二叉树的函数,但是封装函数在调用插入结点函数时一直在报奇怪的编译错误,因此本次代码在main中写入,实际操作就是把一个数组的内的元素分别执行插入结点的操作~
AVLNode* root = nullptr;
std::vector<int> data = {15, 3, 7, 10, 9, 8};
// 插入结点
for (int i = 0; i < data.size(); i++) {
root = insertNode(root, data[i]);
}
具体的创建过程嗯...大概是下图这样的(括号内依然为平衡因子)~
🔯P7:寻找最小结点
利用二叉排序树左<根<右的性质,采用递归方式一直向左寻找,就可以找到最小值结点~
AVLNode* findMinNode(AVLNode* node) {
if (node == nullptr || node->left == nullptr) //如果结点或其左孩子不为空
return node; //返回结点
return findMinNode(node->left); //否则,递归调用本函数向左查询
}
🔯P8:结点删除
传入树的根结点root和关键字data,此处偷懒采用递归的方式删除 {执行效率很低,胜在代码少好理解,不然就又要人工左旋、右旋,如果不平衡性向上传导又得旋,旋转这么多,实在是太太太头晕啦😢😢} ,可分为以下4种情况考虑——
// PS:考研的同学可以参考王道视频,我记得好像是有删除的单独章节说明...如果需要我整理非递归删除的话也可以在评论区留言,有时间我试试...
- 特殊情况:
- 根结点为空,则直接返回空指针;
- 删除的数据 < 根节点:
- 递归调用
deleteNode
函数,将左子树作为新的根节点进行操作;- 删除的数据 > 根节点:
- 递归调用
deleteNode
函数,将右子树作为新的根节点进行操作;- 删除的数据 = 根节点:
- 树仅有根结点,直接删除,将根指针设为空指针;
- 树仅有左孩子结点,交换与左孩子结点的位置,删除左孩子结点;
- 树仅有右孩子结点,交换与右孩子结点的位置,删除右孩子结点;
- 树具有双子树结点,找到右子树中的最小值节点,将其值赋给当前根节点。然后递归调用
deleteNode
函数,在右子树中删除最小值节点。- 执行删除后,使用balance函数调整平衡。
AVLNode* deleteNode(AVLNode* root, int data) {
if (root == nullptr) //根结点为空
return root;
if (data < root->data) //删除数据 < 根结点
root->left = deleteNode(root->left, data); //左子树递归调用deletenode函数
else if (data > root->data) //删除数据 > 根结点
root->right = deleteNode(root->right, data); //右子树递归调用deletenode函数
else { //删除数据 = 根结点
if (root->left == nullptr && root->right == nullptr) { //仅有根结点
delete root;
root = nullptr;
} else if (root->left == nullptr) { //根结点仅有右子树
AVLNode* temp = root;
root = root->right; //交换根结点与右子树
delete temp; //删除根结点
} else if (root->right == nullptr) { //根结点仅有左子树
AVLNode* temp = root;
root = root->left; //交换根结点与左子树
delete temp; //删除根结点
} else { //根结点具有双子树
AVLNode* minRight = findMinNode(root->right); //寻找右子树的最小值
root->data = minRight->data; //右子树的最小值替换根结点
root->right = deleteNode(root->right, minRight->data); //右子树递归调用deletenode函数
}
}
return balanceNode(root); //执行平衡子树的操作
}
🔯P9:树的遍历
传入树的根结点内存地址,由于二叉树遵循:“左<根<右” 的原则,因此可以通过二叉树的中序遍历完成,此处采用递归方式完成~
void inOrderTraversal(AVLNode* root) {
if (root == nullptr)
return;
InOrderTraversal(root->lchild); //遍历左子树
std::cout << root->data << " "; //输出当前结点的值
InOrderTraversal(root->rchild); //遍历右子树
}
敲黑板中序遍历这个已经写过很多次此处不再赘述了~ 🌸数据结构05:树与二叉树[C++]
🔯P10:main函数
main函数除了P0~P9的函数调用,就创建了1棵树,以及示意性地增加删除结点的操作~
int main() {
AVLNode* root = nullptr;
std::vector<int> data = {15, 3, 7, 10, 9, 8}; //树中结点
// 以插入结点的方式创建树
for (int i = 0; i < data.size(); i++) {
root = insertNode(root, data[i]);
}
// 中序遍历输出
std::cout << "中序遍历结果: ";
inOrderTraversal(root);
std::cout << std::endl;
// 删除结点7
root = deleteNode(root, 7);
// 中序遍历输出
std::cout << "删除结点后的中序遍历结果: ";
inOrderTraversal(root);
std::cout << std::endl;
return 0;
}
🧵完整代码
🔯P0:完整代码
按照惯例,为了凑本文的字数,我这里贴一下整体的代码,删掉了细部注释~🫥🫥
// 头文件
#include <iostream>
#include <vector>
#include <algorithm>
// 二叉平衡树结点定义与初始化
struct AVLNode {
int data;
int height;
AVLNode* left;
AVLNode* right;
AVLNode(int value) : data(value), height(1), left(nullptr), right(nullptr) {}
};
// 读取结点的高度
int getHeight(AVLNode* node) {
if (node == nullptr)
return 0;
return node->height;
}
// 写入结点的高度
void updateHeight(AVLNode* node) {
if (node == nullptr)
return;
node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1;
}
// 计算结点的平衡因子
int getBalanceFactor(AVLNode* node) {
if (node == nullptr)
return 0;
return getHeight(node->left) - getHeight(node->right);
}
// 右旋操作
AVLNode* rotateRight(AVLNode* node) {
AVLNode* leftChild = node->left;
node->left = leftChild->right;
leftChild->right = node;
updateHeight(node);
updateHeight(leftChild);
return leftChild;
}
// 左旋操作
AVLNode* rotateLeft(AVLNode* node) {
AVLNode* rightChild = node->right;
node->right = rightChild->left;
rightChild->left = node;
updateHeight(node);
updateHeight(rightChild);
return rightChild;
}
// 平衡操作
AVLNode* balanceNode(AVLNode* node) {
if (node == nullptr)
return nullptr;
updateHeight(node);
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0)
return rotateRight(node);
if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0)
return rotateLeft(node);
if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}
// 插入结点
AVLNode* insertNode(AVLNode* root, int data) {
if (root == nullptr)
return new AVLNode(data);
if (data < root->data)
root->left = insertNode(root->left, data);
else if (data > root->data)
root->right = insertNode(root->right, data);
else
return root; // 重复值,不进行插入
return balanceNode(root);
}
// 查找最小结点
AVLNode* findMinNode(AVLNode* node) {
if (node == nullptr || node->left == nullptr)
return node;
return findMinNode(node->left);
}
// 删除结点
AVLNode* deleteNode(AVLNode* root, int data) {
if (root == nullptr)
return root;
if (data < root->data)
root->left = deleteNode(root->left, data);
else if (data > root->data)
root->right = deleteNode(root->right, data);
else {
if (root->left == nullptr && root->right == nullptr) {
delete root;
root = nullptr;
} else if (root->left == nullptr) {
AVLNode* temp = root;
root = root->right;
delete temp;
} else if (root->right == nullptr) {
AVLNode* temp = root;
root = root->left;
delete temp;
} else {
AVLNode* minRight = findMinNode(root->right);
root->data = minRight->data;
root->right = deleteNode(root->right, minRight->data);
}
}
return balanceNode(root);
}
// 中序遍历
void inOrderTraversal(AVLNode* root) {
if (root == nullptr)
return;
inOrderTraversal(root->left);
std::cout << root->data << " ";
inOrderTraversal(root->right);
}
int main() {
AVLNode* root = nullptr;
std::vector<int> data = {15, 3, 7, 10, 9, 8};
for (int i = 0; i < data.size(); i++) {
root = insertNode(root, data[i]);
}
std::cout << "中序遍历结果: ";
inOrderTraversal(root);
std::cout << std::endl;
root = deleteNode(root, 7);
std::cout << "删除结点后的中序遍历结果: ";
inOrderTraversal(root);
std::cout << std::endl;
return 0;
}
🔯P1:执行结果
运行结果如下图所示~
🔚结语
博文到此结束,写得模糊或者有误之处,欢迎小伙伴留言讨论与批评,督促博主优化内容,不限于以下内容~😶🌫️😶🌫️文章来源:https://www.toymoban.com/news/detail-502021.html
- 有错误:这段注释南辕北辙,理解错误,需要更改~
- 难理解:这段代码雾里看花,需要更换排版、增加语法、逻辑注释或配图~
- 不简洁:这段代码瘠义肥辞,好像一座尸米山,需要更改逻辑;如果是C++语言,调用某库某语法还可以简化~
- 缺功能:这段代码败絮其中,能跑,然而不能用,想在实际运行或者通过考试需要增加功能~
- 跑不动:这不可能——好吧,如果真不能跑,告诉我哪里不能跑我再回去试试...
博文若有帮助,欢迎小伙伴动动可爱的小手默默给个赞支持一下~🌟🌟文章来源地址https://www.toymoban.com/news/detail-502021.html
到了这里,关于数据结构07:查找[C++][平衡二叉排序树AVL]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!