怎么用文本做网站,临沂网站公司,闵行集团网站建设,wordpress软件门户主题目录 AVL树概念
AVL树结构
AVL树插入
LL型 - 右单旋
RR型 - 左单旋
LR型 - 左右双旋
RL型 - 右左双旋
插入代码实现
AVL树测试 附AVL树实现完整代码 AVL树概念
前面的博客介绍了搜索二叉树#xff0c;二叉搜索树-CSDN博客
在某些特定的情况下#xff0c;⼆叉搜索树…目录 AVL树概念
AVL树结构
AVL树插入
LL型 - 右单旋
RR型 - 左单旋
LR型 - 左右双旋
RL型 - 右左双旋
插入代码实现
AVL树测试 附AVL树实现完整代码 AVL树概念
前面的博客介绍了搜索二叉树二叉搜索树-CSDN博客
在某些特定的情况下⼆叉搜索树是会退化成单链表的并且各种操作的效率也会明显的下降因此我们需要⼀些特别的⼿段保证这个⼆叉搜索树的“平衡”进⽽保证各种操作的 效率。这就是我们接下来要学习的平衡⼆叉树
为了保证⼆叉搜索树的性能规定在插⼊和删除结点时要保证任意结点的左、⼦树⾼度差的绝对值不超过1 这样的⼆叉树称为平衡⼆叉树(简称AVL树)。
其中结点左⼦树与右⼦树的⾼度差定义为该结点的平衡因⼦(⼀般是左⼦树的⾼度减去右⼦树的⾼ 度。当然反过来也是可以的
由此可⻅平衡⼆叉树中每⼀个结点的平衡因⼦只可能是 0/1/-1如下图所⽰结点上⽅的数字表⽰平衡因⼦。左图是⼀棵平衡⼆叉树右图不是⼀棵平衡⼆叉树 AVL树结构
我们采用三叉链的结构实现节点因为AVL树调平衡的过程需要向上找父节点因此需要存储父节点的指针信息
templateclass K, class V
struct AVLTreeNode
{//三叉链AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; //平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
private:Node* _root nullptr;
};
AVL树插入
在⼆叉搜索树中插⼊新结点之后插⼊路径的点中可能存在很多平衡因⼦的绝对值⼤于1的此时找到距离插⼊结点最近的不平衡的点以这个点为根的字树就是不平衡子树。如下图: 插⼊之后会导致三个结点失衡其中距离最近的 结点为根的⼦树就是最小不平衡子树。可以发现仅需让最⼩不平衡⼦树平衡所有结点就都平衡了感性认知如下:
1. 本来整棵树就是平衡⼆叉树如果来了⼀个结点导致失衡那么失衡结点的平衡因⼦只能是2或者 -2
2 .当我们把最⼩平衡⼦树调整平衡之后那么这棵⼦树的⾼度就会减 向上传递的过程中会让 整个路径⾥⾯的平衡因⼦都向0靠近⼀位原来的-2会变成-1原来的2会变成1整棵树就变得平衡了。
而最⼩不平衡⼦树的出现可以细分成4种情况因此调整策略也会分为4种情况讨论。为了方便叙述 设最小不平衡子树的根节点为T。 LL型 - 右单旋 LL 表示新结点由于插⼊在T结点的左孩⼦(L)的左⼦树(LL)中从⽽导致失衡。如下图所示: 此时需要将L右旋
• 将结点L向右上旋转代替结点T作为根结点
• 将节点T向右下旋转作为结点L的右⼦树的根结点
• 结点L的原右⼦树(LR)则作为结点T的左⼦树
旋转之后依旧满⾜平衡⼆叉树的特性LL L LR T R 案例下列AVL树中插⼊1 最⼩不平衡⼦树是以 13 为根的⼦树引起不平衡的原因是 13的左孩⼦的左⼦树上插⼊⼀个新的结点因此需要右旋⼀次。右旋的结点为10 代码实现:
void RotateR(Node *parent)
{Node *subL parent-_left;Node *subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node *parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}subL-_bf parent-_bf 0;
} RR型 - 左单旋 RR表⽰新结点由于插⼊在T结点的右孩⼦(R)的右⼦树(RR)中从⽽导致失衡。如下图所⽰ 此时需要⼀次向左的旋转操作将R左旋
• 将结点R向左上旋转代替结点T作为根结点
• 将节点T向左下旋转作为结点R的左⼦树的根结点
• 结点R的原左⼦树(RL)则作为结点T的右⼦树。 如下图 案例下列AVL树中插⼊64 最⼩不平衡⼦树是以 49 为根的⼦树引起不平衡的原因是 49 的右孩⼦的右⼦树上插⼊⼀个新的结 点因此需要左旋⼀次。左旋的结点为59 代码实现
void RotateL(Node *parent)
{Node *subR parent-_right;Node *subRL subR-_left;parent-_right subRL;subR-_left parent;// 旋转之后整棵子树的根变了, 需要重新链接Node *parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_bf 0;
} LR型 - 左右双旋 LR表⽰新结点由于插⼊在T结点的左孩⼦(L)的右⼦树(LR)中从⽽导致失衡。如下图所⽰ 此时需要两次旋转操作先将LR左旋再将LR右旋。
将LR左旋
• 将结点LR向左上旋转代替结点L作为根结点
• 将节点L向左下旋转作为结点LR的左⼦树的根结点
• 结点LR的原左⼦树(LRL)则作为结点L的右⼦树。
将LR右旋
• 将结点LR向右上旋转代替结点T作为根结点
• 将节点T向右下旋转作为结点LR的右⼦树的根结点
• 结点LR的原右⼦树(LRR)则作为结点T的左⼦树。 案例下列AVL树中插⼊1 最⼩不平衡⼦树是以49为根的⼦树引起不平衡的原因是49的左孩⼦的右⼦树上插⼊⼀个新的结点因此需要左旋⼀次然后右旋⼀次。旋转的结点为45 void RotateLR(Node *parent)
{Node *subL parent-_left;Node *subLR subL-_right;int bf subLR-_bf; // subLR不可能为nullptr因为subL的平衡因子是-1RotateL(subL);RotateR(parent);// 3、更新平衡因子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 subL-_bf parent-_bf 0;}else{assert(false); // 在旋转前树的平衡因子就有问题}
} RL型 - 右左双旋 RL表⽰新结点由于插⼊在T结点的右孩⼦(R)的左⼦树(RL)中从⽽导致失衡。如下图所⽰ 此时需要两次旋转操作先将RL右旋再将RL左旋。将RL右旋
• 将结点RL向右上旋转代替结点R作为根结点
• 将节点R向右下旋转作为结点RL的右⼦树的根结点
• 结点RL的原右⼦树(RLR)则作为结点R的右⼦树。
将RL左旋
• 将结点RL向左上旋转代替结点T作为根结点
• 将节点T向左下旋转作为结点RL的左⼦树的根结点
• 结点RL的原左⼦树(RLL)则作为结点T的右⼦树。 案例下列AVL树中插⼊52 最⼩不平衡⼦树是以49为根的⼦树引起不平衡的原因是49的右孩⼦的左⼦树上插⼊⼀个新的结点因此需要右旋⼀次然后再左旋⼀次。旋转的结点为55 代码实现
void RotateRL(Node *parent)
{Node *subR parent-_right;Node *subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){parent-_bf subR-_bf subRL-_bf 0;}else if (bf -1){parent-_bf 1;subRL-_bf 0;subR-_bf 0;}else if (bf 1){parent-_bf 0;subRL-_bf 0;subR-_bf -1;}else{assert(false);}
}
插入代码实现
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node *parent nullptr;Node *cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent){// 平衡因子的变化if (cur parent-_left){parent-_bf;}else{parent-_bf--;}if (parent-_bf 0) // 之前为-1/1, cur填到了较低的一边树高不变不需要继续调整了!{break;}else if (parent-_bf 1 || parent-_bf -1) // 之前为0, 当前树高1, 可能不再平衡了,向上调整!{cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2) // 失衡了, 需要重新调平衡{if (parent-_bf 2 cur-_bf 1){RotateR(parent);}else if (parent-_bf -2 cur-_bf -1){RotateL(parent);}else if (parent-_bf 2 cur-_bf -1){RotateLR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateRL(parent);}// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度恢复到跟插入前一样的高度所以对上一层没有影响不用继续更新break;}else{assert(false);}}return true;
}
● 首先和二叉搜索树一样先找到合适的插入位置再进行插入
● 插入后更新当前子树的平衡因子然后根据平衡因子的特点执行不同的操作
● 如果当前子树的平衡因子是0说明依旧平衡不需要调平衡如果当前子树的平衡因子是1/-1需要继续向上找最小不平衡子树如果当前子树的平衡因子是2/-2说明找到了最小不平衡子树根据平衡因子的特点执行不同的旋转操作只要最小不平衡子树调平衡了整棵树就平衡了直接跳出循环即可
AVL树测试
判断是否是平衡二叉树:
public:bool IsBalance(){return _IsBalance(_root);}private:bool _IsBalance(Node* root){if (root nullptr)return true;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);if (leftHeight - rightHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(leftHeight - rightHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);}int _Height(Node* root){if (root nullptr)return 0;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}
中序遍历
public:void InOrder(){_InOrder(_root);cout endl;}
private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}
main函数测试
#include iostream
#include assert.h
using namespace std;#include AVL.hvoid test1()
{int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout t.IsBalance() endl;
}void test2()
{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));}t.InOrder();cout t.IsBalance() endl;
}#include vector
void test3()
{const int N 30;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand());cout v.back() endl;}AVLTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));cout Insert: e - t.IsBalance() endl;}cout t.IsBalance() endl;
}int main()
{test1();test2();test3();return 0;
} 附AVL树实现完整代码
#pragma once
#includeassert.h
#include iostream
using namespace std;//AVL树
//1.本质还是一颗二叉搜索树
//2.增加了平衡因子任何一颗子树的左右子树高度差绝对值不超过1templateclass K, class V
struct AVLTreeNode
{//三叉链AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; //平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent) {//平衡因子的变化if (cur parent-_left){parent-_bf;}else{parent-_bf--;}if (parent-_bf 0) //之前为-1/1, cur填到了较低的一边树高不变不需要继续调整了!{break;}else if (parent-_bf 1 || parent-_bf -1) //之前为0, 当前树高1, 可能不再平衡了,向上调整!{cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2) //失衡了, 需要重新调平衡{if (parent-_bf 2 cur-_bf 1) {RotateR(parent);}else if (parent-_bf -2 cur-_bf -1){RotateL(parent);}else if (parent-_bf 2 cur-_bf -1){RotateLR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateRL(parent);}// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度恢复到跟插入前一样的高度所以对上一层没有影响不用继续更新break;}else{assert(false);}}return true;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;//旋转之后整棵子树的根变了, 需要重新链接Node* parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_bf 0;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}subL-_bf parent-_bf 0;}void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if(bf 0){parent-_bf subR-_bf subRL-_bf 0;}else if (bf -1){parent-_bf 1;subRL-_bf 0;subR-_bf 0;}else if (bf 1){parent-_bf 0;subRL-_bf 0;subR-_bf -1;}else{assert(false);}}//左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf; //subLR不可能为nullptr因为subL的平衡因子是-1RotateL(subL);RotateR(parent);//3、更新平衡因子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 subL-_bf parent-_bf 0;}else{assert(false); //在旋转前树的平衡因子就有问题}}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){return _IsBalance(_root);}private:bool _IsBalance(Node* root){if (root nullptr)return true;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);if (leftHeight - rightHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(leftHeight - rightHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);}int _Height(Node* root){if (root nullptr)return 0;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}
private:Node* _root nullptr;
};
