深圳网站建设app开发,WordPress 任务管理,.net网站开发代码,山东网站空间文章目录一、AVL树的概念二、AVL树节点的定义三、AVL树的插入四、AVL树的旋转1.左单旋2.右单旋3.左右双旋4.右左双旋五、进行验证六、AVLTree的性能个人简介#x1f4dd; #x1f3c6;2022年度博客之星Top18;#x1f3c6;2022社区之星Top2;的#x1f947;C/C领域优质创作者…
文章目录一、AVL树的概念二、AVL树节点的定义三、AVL树的插入四、AVL树的旋转1.左单旋2.右单旋3.左右双旋4.右左双旋五、进行验证六、AVLTree的性能个人简介 2022年度博客之星Top18;2022社区之星Top2;的C/C领域优质创作者; 阿里云专家博主;华为云云享专家;腾讯云年度进取作者;掘金成长之星; 一、AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。
因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 平衡因子 右子树高度-左子树高度 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在O(log2N) 搜索时间复杂度O(log2N) 二、AVL树节点的定义
节点结构三叉链结构左、右、父以及平衡因子bf构造函数左右为空平衡因子初始化为0
templateclass K,class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;//balance factorAVLTreeNode(const pairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};三、AVL树的插入
AVL树在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。步骤过程 找到插入的位置根据二叉搜索树的做法 进行插入判断插入的位置是parent的左还是右 更新平衡因子如果不平衡的话就要进行旋转 找到插入位置比较节点大小即可
插入的节点key值 当前位置的key值往右子树走插入的节点key值 当前位置的key值往左子树走插入的节点key值等于当前位置的key值不能插入返回false
插入之后与二叉搜索树不同的是我们还需要去进行平衡因子的更新调平衡
如果新增加的在右平衡因子加加
如果新增加的在左平衡因子减减
更新一个结点之后我们需要去进行判断子树的高度是否发生了变化
1.如果parent的平衡因子是0说明之前parent的平衡因子是1或-1说明之前parent一边高、一边低这次插入之后填入矮的那边parent所在的子树高度不变不需要继续往上更新
2.如果parent的平衡因子是1或者-1说明之前parent的平衡因子是0两边一样高插入之后一边更高parent所在的子树高度发生变化继续往上更新
3.平衡因子是2或-2说明之前parent的平衡因子是1或-1现在插入严重不平衡违反规则需要进行旋转处理
最坏的情况下需要一直更新到根root 我们更新平衡因子时第一个更新的就是parent,如果parent-_bf1或parent-_bf-1需要继续往上进行平衡因子的更新向上迭代直到parent为空的情况
else if (parent-_bf 1 || parent-_bf -1)
{cur parent;parent parent-_parent;
}当parent-_bf 2或parent-_bf-2时我们就需要进行旋转了
如果parent的平衡因子是2cur的平衡因子是1时说明右边的右边比较高我们需要进行左单旋
如果parent的平衡因子是-2cur的平衡因子是-1时说明左边的左边比较高我们需要进行右单旋
如果parent的平衡因子是-2cur的平衡因子是1时我们需要进行左右双旋
如果parent的平衡因子是2cur的平衡因子是-1时我们需要进行右左双旋
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){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if(parent-_bf2||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 -2cur-_bf1){RotateLR(parent);}//右左双旋else if (parent-_bf 2cur-_bf -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}四、AVL树的旋转
在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种。
旋转规则
1.让这颗子树左右高度差不超过1
2.旋转过程中继续保持它是搜索树
3.更新调整孩子节点的平衡因子
4.让这颗子树的高度根插入前保持一致
1.左单旋
新节点插入较高右子树的右侧—右右左单旋
抽象图 a/b/c是高度为h的AVL子树代表多数情况h0,其中h可以等于0、1、2…不过都可以抽象成h处理情况都一样此时parent等于2subR等于1。
具体左旋的步骤 subRL成为parent的右子树注意subL和parent的关系调整parent的右以及subRL的父subRL可能为空 parent成为subR的左子树调整parent的父与subR的左 subR成为相对的根节点调整subR与ppNode注意parent是不是整棵树的root如果是则让subR为_root,同时让_root-_parent置为空 更新平衡因子 左旋调整subR的左子树值subRL本身就比parent的值要大所以可以作为parent的右子树;而parent及其左子树当中结点的值本身就比subR的值小所以可以作为subR的左子树。
**更新平衡因子bf:**subR与parent的bf都更新为0 代码实现左旋转
//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}parent-_bf subR-_bf 0;}2.右单旋
新节点插入较高左子树的左侧—左左右单旋
有了前面左旋的基础我们在来看右旋就没有那么费劲了 a/b/c是高度为h的AVL树右旋旋转动作b变成60的左边60变成30的右边30变成子树的根。 30比60小b值是处于30和60之间此时作为60的左边是没有问题的。
有了这个图在结合前面左单旋的基础我们就能很快实现我们的右单旋代码
//右单旋
void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppNode parent-_parent;parent-_parent subL;subL-_right parent;//if(_rootparent)if (ppNode nullptr){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}subL-_bf parent-_bf 0;}3.左右双旋
新节点插入较高左子树的右侧—左右先左单旋再右单旋 a/d是高度为h的AVL树b/c是高度为h-1的AVL树。
以30为轴点进行左单旋b变成30的右边30变成60的左边60变成子树根 以90为轴点进行右单旋c变成90的左边90变成60的右边60变成子树的根 左右双旋以subL为轴点左旋以parent为轴点进行右旋在进行平衡因子的更新(最大的问题)
我们从总体的角度来看左右双旋的结果就是就是把subLR的左子树和右子树分别作为subL和parent的右子树和左子树同时subL和parent分别作为subLR的左右子树最后让subLR作为整个子树的根
subLR的左子树作为subL的右子树因为subLR的左子树结点比subL的大
subLR的右子树作为parent的左子树因为subLR的右子树结点比parent的小
平衡因子的更新重新判断识别插入节点是在b还是在c根据subLR平衡因子的初始情况进行分类
如果subLR初始平衡因子是-1时左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0插入在b 如果subLR的初始平衡因子是1时左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0插入在c 如果subLR初始平衡因子是0时左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0subLR自己新增 代码实现
//左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR -_bf;RotateL(parent-_left);RotateR(parent);//更新平衡因子if (bf -1)//b插入,subLR左子树新增{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else if (bf 1)//c插入subLR右子树新增{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf 0)//subLR自己新增加{parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else{assert(false);}}4.右左双旋
新节点插入较高右子树的左侧—右左先右单旋再左单旋
插入 subR为轴点进行右单旋 parent为轴进行左单旋 既右左双旋 右左双旋后根据subRL 初始平衡因子的不同分为三种情况分别对应subRL 0、1、-1情况与左右双旋情况类似。
void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else{assert(false);}}五、进行验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确 如果是空树是AVL树高度差不大于2并且递归左右子树的高度差都不大于2也是AVL树判断平衡因子和该点的高度差是否相等
//求高度
int Height(Node* root){if (root nullptr)return 0;int lh Height(root-_left);int rh Height(root-_right);return lh rh ? lh 1 : rh 1;}
//判断平衡
bool IsBalance(Node* root){if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2 IsBalance(root-_left) IsBalance(root-_right);}六、AVLTree的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log2( N) 。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。 因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合. 送上源码
#pragma once
#include iostream
#include assert.h
#include time.h
using namespace std;
templateclass K,class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;//balance factorAVLTreeNode(const pairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template class K,class V
struct 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){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if(parent-_bf2||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 -2cur-_bf1){RotateLR(parent);}//右左双旋else if (parent-_bf 2cur-_bf -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}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* ppNode parent-_parent;parent-_parent subL;subL-_right parent;//if(_rootparent)if (ppNode nullptr){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}subL-_bf parent-_bf 0;}//左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR -_bf;RotateL(parent-_left);RotateR(parent);//更新平衡因子if (bf -1)//b插入,subLR左子树新增{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else if (bf 1)//c插入subLR右子树新增{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf 0)//subLR自己新增加{parent-_bf 0;subL-_bf 0;subLR-_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);if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else{assert(false);}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}int Height(Node* root){if (root nullptr)return 0;int lh Height(root-_left);int rh Height(root-_right);return lh rh ? lh 1 : rh 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2 IsBalance(root-_left) IsBalance(root-_right);}
private:Node* _root nullptr;
};//测试
void TestAVLTree()
{//int a[] { 8,3,1,10,6,4,7,14,13 };//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };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;
}void TestAVLTree2()
{srand(time(0));const size_t N 100000;AVLTreeint, int t;for (size_t i 0; i N; i){size_t x rand();t.Insert(make_pair(x, x));}//t.InOrder();cout t.IsBalance() endl;
}本篇结束…
