thinkphp租房网站开发,网站后台上图片后网页显示不正确,四川建设信息网,wordpress 行间距C进阶#xff1a;AVL树详解及模拟实现#xff08;图示讲解旋转过程#xff09;
之前在搜索二叉树最后早就埋下伏笔#xff0c;来介绍AVL树和红黑树#xff0c;今天就先来第一个吧 文章目录 1.AVL树介绍1.1概念介绍1.2核心性质 2.项目文件规划3.整体框架#xff08;节点和…C进阶AVL树详解及模拟实现图示讲解旋转过程
之前在搜索二叉树最后早就埋下伏笔来介绍AVL树和红黑树今天就先来第一个吧 文章目录 1.AVL树介绍1.1概念介绍1.2核心性质 2.项目文件规划3.整体框架节点和Tree4.AVL树的新节点插入4.1新节点插入当前节点的右子树的右子树——左旋转左旋 (Left Rotation)情况操作 4.2新节点插入当前节点的左子树的左子树——右旋转右旋 (Right Rotation)情况操作 4.3新节点插入当前节点的左子树的右子树——左右双旋左右双旋LR旋转 4.4新节点插入当前节点的右子树的左子树——右左双旋右左旋RL旋转 4.5组装完整版Insert 5.中序方便过会测试6.编写函数看是否满足要求6.1求高度6.2 平衡否 7.测试8.全部代码8.1 AVLTree.h8.2 test.cpp 1.AVL树介绍 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法人为规定 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度 1.1概念介绍
AVL树定义 解释AVL树是一种自平衡的二叉搜索树由G.M. Adelson-Velsky和E.M. Landis在1962年提出。强调AVL树中每个节点的平衡因子Balance Factor即左子树高度和右子树高度之差不超过1。 平衡因子 解释平衡因子的概念即一个节点的左子树高度减去右子树高度的值。平衡因子为{-1, 0, 1}时树是平衡的。 自平衡性质 说明AVL树具有自平衡性质即在插入或删除节点时会通过旋转操作来保持树的平衡。提及AVL树的平衡因子限制确保树的高度保持在对数级别。 1.2核心性质 严格平衡 强调AVL树的严格平衡性质即每个节点的左右子树高度差不超过1。严格平衡性质保证了AVL树的高度近似于对数级别保证了高效的插入、删除和查找操作。 插入和删除操作 介绍当插入或删除节点时AVL树如何通过旋转操作来保持平衡。解释插入和删除操作可能会导致树失去平衡需要通过单旋转、双旋转等操作进行调整。 时间复杂度 说明AVL树的插入、删除和查找操作的时间复杂度都是O(log n)其中n为树中节点的数量。强调AVL树在动态数据集合中的高效性适用于需要频繁更新的场景。
2.项目文件规划 头文件AVLTree.h进行模拟的编写 源文件test.cpp进行测试检查代码逻辑是否满足期望 3.整体框架节点和Tree
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;//父亲节点int _bf; // balance factor 平衡因子pairK, V _kv;//每个节点里存一个pairAVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv)//都直接在初始化列表里初始化了{}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;//名字太长了叫Node也更好理解
public:private:Node* _root nullptr;//给上缺省值
};
4.AVL树的新节点插入 基本步骤 查找插入位置 首先我们需要找到新节点应该插入的位置。从根节点开始按照二叉搜索树的性质逐级向左或向右比较键值直到找到一个合适的位置。插入新节点 找到插入位置后我们创建一个新的节点并将其插入到树中。如果树为空则新节点成为树的根节点。否则将新节点插入到合适的位置使得树仍然保持二叉搜索树的性质。更新平衡因子 在插入新节点后需要沿着插入路径更新所有受影响节点的平衡因子。平衡因子是指节点的左右子树的高度差。如果插入导致某个节点的平衡因子超出范围通常是 -1、0、1则需要进行旋转操作来恢复平衡。平衡调整 如果插入操作破坏了 AVL 树的平衡性我们需要进行一系列的旋转操作来重新平衡树。旋转操作包括单旋转和双旋转具体的旋转方式取决于插入节点的位置以及平衡因子的情况。旋转后继续向上 插入节点后可能需要对父节点、祖父节点等进行旋转操作直到树恢复平衡为止。 bool Insert(const pairK, V kv){if (_root nullptr)//如果是空树{_root new Node(kv);return true;//插入成功}Node* cur _root;Node* parent nullptr;while (cur)//这里开始找位置{if (kv.first cur-_kv.first)//小于往左走{parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;//不能有相等的}}//开始把新节点链接上cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//更新平衡因子while (parent ! nullptr)//cur到跟节点停下{if (cur parent-_left)//在左就--{parent-_bf--;}else//在右{parent-_bf;}//开始检查父亲节点的情况if (parent-_bf 0){break;//直接停止}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent cur-_parent;//向上走}else if (parent-_bf 2 || parent-_bf -2){//破坏了规则了开始旋转}else{// 会到这说明插入之前AVL树就有问题assert(false);}}}更新平衡因子过程 更新的原则如下 如果新节点插入到父节点的左侧则父节点的平衡因子减一。如果新节点插入到父节点的右侧则父节点的平衡因子加一。 更新后需要检查父节点的平衡因子是否发生变化如果发生变化则继续向上检查祖先节点的平衡因子直到根节点或者到达一个平衡因子为 ±1 的节点为止。根据更新后节点的平衡因子情况可以采取以下处理措施 如果节点的平衡因子为 0表示节点所在子树的高度没有变化不会影响祖先节点的平衡因子更新结束。如果节点的平衡因子为 ±1表示节点所在子树的高度变化本来是0现在变成 ±1子树高度变了会影响祖先节点的平衡因子需要继续向上更新祖先节点的平衡因子。如果节点的平衡因子为 ±2表示节点所在子树违反了平衡规则需要进行平衡调整操作如旋转然后更新结束。 4.1新节点插入当前节点的右子树的右子树——左旋转 左旋 (Left Rotation) 左旋的情况是当一个节点的右子树过高需要进行左旋来降低右子树的高度同时保持树的平衡。 情况 新节点插入到当前节点的右子树的右子树中导致当前节点的平衡因子为 2。在双旋的过程中当左子树的平衡因子为 -1右子树的平衡因子为 1。 操作 左旋是指将当前节点向左旋转使得当前节点的右子树的左子树成为当前节点的右子树同时将当前节点成为其右子树的左子树。 A B/ \ / \T1 B A T3/ \ / \T2 T3 T1 T2 void RotateL(Node* parent){Node* subR parent-_right;//要成为根的Node* subRL subR-_left;//要成为30的右子树parent-_right subRL;if (subRL ! nullptr)subRL-_parent parent;subR-_left parent;Node* pparent parent-_parent;//存一下新根才能链接parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent)//parent在pp的左那我新的跟subR也要左{ppnode-_left subR;}else//同理{ppnode-_right subR;}subR-_parent ppnode;}//更新平衡因子parent-_bf 0;subR-_bf 0;}4.2新节点插入当前节点的左子树的左子树——右旋转 右旋 (Right Rotation) 右旋的情况是当一个节点的左子树过高需要进行右旋来降低左子树的高度同时保持树的平衡。 情况 新节点插入到当前节点的左子树的左子树中导致当前节点的平衡因子为 -2。在双旋的过程中当左子树的平衡因子为 -1右子树的平衡因子为 1。 操作 右旋是指将当前节点向右旋转使得当前节点的左子树的右子树成为当前节点的左子树同时将当前节点成为其左子树的右子树。 A B/ \ / \B T3 T1 A/ \ / \
T1 T2 T2 T3 void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf 0;parent-_bf 0;}4.3新节点插入当前节点的左子树的右子树——左右双旋 当新节点插入当前节点的左子树的右子树时会触发左右双旋操作LR旋转。这种情况发生在当前节点的左子树的右子树上插入了新节点导致当前节点的平衡因子不平衡可能为2或-2且当前节点的左子树的右子树的平衡因子为正值1。为了恢复 AVL 树的平衡性需要先对当前节点的左子树进行一次左旋操作然后再对当前节点进行一次右旋操作。 左右双旋LR旋转 具体步骤如下 对当前节点的左子树进行一次左旋操作。对当前节点进行一次右旋操作。 示例 假设当前节点为 A新节点插入在 A 的左子树的右子树的情况下左右双旋操作如下 A A C/ \ / \ / \B T4 左旋后 C T4 右旋后 B A/ \ --------- / \ --------- / \ / \T1 C B T3 T1 T2 T3 T4/ \ / \T2 T3 T1 T2void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//存一下后面要更新bfRotateL(parent-_left);RotateR(parent);if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}4.4新节点插入当前节点的右子树的左子树——右左双旋 右左旋RL旋转 右左旋操作发生在节点的右子树过深导致平衡因子为 -2 且其右子节点的平衡因子为 1 的情况下。具体步骤如下 对 A 的右子树进行一次左旋操作。再对 A 进行一次右旋操作。 示例 A A C/ \ / \ / \T1 B T1 C A B/ \ / \ / \ / \C T4 T2 B T1 T2 T3 T4/ \ / \T2 T3 T3 T4void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);subRL-_bf 0;if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){parent-_bf 0;subR-_bf 1;}else{parent-_bf 0;subR-_bf 0;}}4.5组装完整版Insert
bool Insert(const pairK, V kv){if (_root nullptr)//如果是空树{_root new Node(kv);return true;//插入成功}Node* cur _root;Node* parent nullptr;while (cur)//这里开始找位置{if (kv.first cur-_kv.first)//小于往左走{parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;//不能有相等的}}//开始把新节点链接上cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//更新平衡因子while (parent ! nullptr)//cur到跟节点停下{if (cur parent-_left)//在左就--{parent-_bf--;}else//在右{parent-_bf;}//开始检查父亲节点的情况if (parent-_bf 0){break;//直接停止}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent cur-_parent;//向上走}else if (parent-_bf 2 || parent-_bf -2){//破坏了规则了开始旋转if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else{RotateRL(parent);}break;//调整完后就平衡了也不用向上直接出去}else{// 会到这说明插入之前AVL树就有问题assert(false);}}}5.中序方便过会测试 void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first [ root-_bf ] endl;_InOrder(root-_right);}6.编写函数看是否满足要求 只要有一个节点的左子树与右子树的高度差距大于等于2那么就不满足了 从这里也能看出要写一个求高度函数更方便 6.1求高度 int Height(){_Height(_root);}int _Height(Node* root){if (root nullptr){return 0;}int right _Height(root-_right);int left _Height(root-_left);return right left ? right 1 : left 1;}这段代码实现了 AVL 树的高度计算和平衡性检查功能。 _Height 函数: 这个函数用于计算给定树的高度。递归地计算左右子树的高度然后返回较大的子树高度加上 1。这个函数被用于计算整棵树的高度。 Height 函数: 这个函数是对外提供的接口用于获取 AVL 树的高度。它调用 _Height 函数并传入根节点返回整棵 AVL 树的高度。 6.2 平衡否 bool IsBalance(){int height 0;return _IsBlance(_root, height);}bool _IsBlance(Node* root, int h){if (root nullptr){h 0;return true;}int leftHeight 0, rightHeight 0;if (!_IsBlance(root-_left, leftHeight)|| !_IsBlance(root-_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) 2){cout root-_kv.first 不平衡 endl;return false;}h leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}_IsBalance 函数: 这个函数用于检查 AVL 树的平衡性。它递归地检查树的每个节点计算左右子树的高度并比较它们的差值如果差值大于等于 2则表示不平衡。此外还检查每个节点的平衡因子是否正确即右子树高度减去左子树高度等于节点的平衡因子。如果平衡因子异常则表示树不平衡。 IsBalance 函数: 这个函数是对外提供的接口用于检查整棵 AVL 树的平衡性。它调用 _IsBalance 函数并传入根节点返回整棵 AVL 树是否平衡的结果。 这些函数的实现是 AVL 树的重要部分用于确保 AVL 树保持平衡性和正确性。 7.测试
void TestAVLTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));cout e - t.IsBalance() endl;}t.InOrder();cout t.IsBalance() endl;
}8.全部代码
8.1 AVLTree.h
#pragma oncetemplateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;//父亲节点int _bf; // balance factor 平衡因子pairK, V _kv;//每个节点里存一个pairAVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv)//都直接在初始化列表里初始化了{}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;//名字太长了叫Node也更好理解
public:void RotateL(Node* parent){Node* subR parent-_right;//要成为根的Node* subRL subR-_left;//要成为30的右子树parent-_right subRL;if (subRL ! nullptr)subRL-_parent parent;subR-_left parent;Node* ppnode parent-_parent;//存一下新根才能链接parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent)//parent在pp的左那我新的跟subR也要左{ppnode-_left subR;}else//同理{ppnode-_right subR;}subR-_parent ppnode;}//更新平衡因子parent-_bf 0;subR-_bf 0;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf 0;parent-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//存一下后面要更新bfRotateL(parent-_left);RotateR(parent);if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);subRL-_bf 0;if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){parent-_bf 0;subR-_bf 1;}else{parent-_bf 0;subR-_bf 0;}}bool Insert(const pairK, V kv){if (_root nullptr)//如果是空树{_root new Node(kv);return true;//插入成功}Node* cur _root;Node* parent nullptr;while (cur)//这里开始找位置{if (kv.first cur-_kv.first)//小于往左走{parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;//不能有相等的}}//开始把新节点链接上cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//更新平衡因子while (parent ! nullptr)//cur到跟节点停下{if (cur parent-_left)//在左就--{parent-_bf--;}else//在右{parent-_bf;}//开始检查父亲节点的情况if (parent-_bf 0){break;//直接停止}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent cur-_parent;//向上走}else if (parent-_bf 2 || parent-_bf -2){//破坏了规则了开始旋转if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else{RotateRL(parent);}break;//调整完后就平衡了也不用向上直接出去}else{// 会到这说明插入之前AVL树就有问题assert(false);}}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first [ root-_bf ] endl;_InOrder(root-_right);}int Height(){_Height(_root);}int _Height(Node* root){if (root nullptr){return 0;}int right _Height(root-_right);int left _Height(root-_left);return right left ? right 1 : left 1;}bool IsBalance(){int height 0;return _IsBlance(_root, height);}bool _IsBlance(Node* root, int h){if (root nullptr){h 0;return true;}int leftHeight 0, rightHeight 0;if (!_IsBlance(root-_left, leftHeight)|| !_IsBlance(root-_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) 2){cout root-_kv.first 不平衡 endl;return false;}h leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}private:Node* _root nullptr;//给上缺省值
};void TestAVLTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));cout e - t.IsBalance() endl;}t.InOrder();cout t.IsBalance() endl;
}
8.2 test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
using namespace std;
#includeassert.h#includeAVLTree.h
int main()
{TestAVLTree1();return 0;
}今天就到这里啦下一次肯定是红黑树啦
