乐享校园网站建设策划书,申请号的网站,邓州市建设局网站,鞍山58招聘每一个不曾起舞的日子都是对生命的辜负 AVL树前言#xff1a;一.AVL树的概念二.AVL树的结构2.1 AVL树节点的定义2.2 AVL树的结构2.3 AVL树的插入2.4 AVL树的验证2.5 AVL树的删除(了解)三.AVL树的旋转#xff08;重要#xff09;3.1 左单旋3.2 右单旋3.3 左右双旋3.4 右左双旋… 每一个不曾起舞的日子都是对生命的辜负 AVL树前言一.AVL树的概念二.AVL树的结构2.1 AVL树节点的定义2.2 AVL树的结构2.3 AVL树的插入2.4 AVL树的验证2.5 AVL树的删除(了解)三.AVL树的旋转重要3.1 左单旋3.2 右单旋3.3 左右双旋3.4 右左双旋四.AVL树完整代码AVLTree.hTest.c五. AVL树的性能前言 前面对map/multimap/set/multiset进行了简单的介绍在其文档介绍中发现这几个容器有个共同点是其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。 平衡树有AVL树、红黑树本篇就来了解一下AVL树。 一.AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。一棵AVL树或者是空树或者是具有以下性质的二叉搜索树(可以调整是因为相同数据的二叉搜索树不止一种形状) 它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 平衡因子 right - left 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在O(log2n)O(log_2 n)O(log2n)搜索时间复杂度O(log2nlog_2 nlog2n)。
二.AVL树的结构
2.1 AVL树节点的定义
对于AVL树相比普通的二叉搜索树最主要的就是多了一个平衡因子保持AVL高度平衡的结构。而为了能够更加便捷的操作平衡因子除了左右节点的指针还要新增一个父亲节点指针即三叉链的结构因为左右子树的增加节点就会导致父亲节点平衡因子的变化
templateclass K, class V
struct AVLTreeNode//三叉链
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factor 平衡因子AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};2.2 AVL树的结构
#pragma once
templateclass K, class V
struct AVLTreeNode//三叉链
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factor 平衡因子AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};templateclass K, class V
struct AVLTree
{typedef AVLTreeNodeK, V Node;
public://一系列的成员函数……// 1.插入// 2.
private:Node* _root;
};2.3 AVL树的插入
对于AVL树的插入来说本质上还是二叉搜索树因此大致的插入逻辑还是像普通的搜索树一样即比根小向左遍历比根大向右遍历如果遇到相同节点就插入失败返回false如果没遇到遇到空的地方就直接插入。
但与普通二叉搜索树不同的是我们在插入节点的过程中要时时刻刻注意AVL树的结构即通过我们新增的成员平衡因子_bf而为了便于访问这个平衡因子相比较普通的搜索树也就增加了指向父亲节点的指针即三叉链的结构。但需要注意的是如果插入了新节点这样不仅会导致父亲节点平衡因子的变化同样也有可能父亲的父亲节点也会跟着变化下面试着举2个例子
例1
对于这种情况来说新增了一个cur节点恰好能够使parent的平衡因子变成0我们知道平衡因子右子树的高度-左子树的高度我们可以看出parent的值从-1或者1变成0整颗树没有任何一个子树的高度发生了变化因此插入一个节点不影响任何子树的高度即parent的平衡因子变成0就不需要继续向上遍历检索上面父亲节点的平衡因子了。
例2 新增插入节点时都必须去检索。对于这种情况向上遍历的平衡因子并且根据变化的结构去修改平衡因子如果平衡因子变成了不属于[-1, 1]的范围那就说明这颗子树的结构出现了问题此时就需要将这颗子树进行旋转使其结构满足所有平衡因子都属于[-1, 1]的范畴。如何旋转由于旋转过于复杂后面会单独展示。 那再缕清一下插入的思路 第一步寻找插入点
此步骤与普通的二叉搜索树的规则几乎相同唯一区别是由于多了一个parent指针parent初始化为nullptr因此在搜索的时候parent也需要不断变化。
第二步更新平衡因子
parent的平衡因子会随着插入节点而发生变化parent一旦变化那parent的parent也会发生变化因此需要一个循环使平衡因子顺着自己的parent指针不断遍历并且判断是否需要更改。
第三步判断平衡因子的范围
平衡因子如果变成0说明之前的parent-_bf是1或-1说明之前parent一边高一边低这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新可以跳出循环。平衡因子如果变成1或者-1说明插入之前parent-_bf 0两遍一样高现在插入后一边更高了parent所在子树高度变了需要继续往上更新平衡因子如果变成 2或者-2说明之前parent-_bf是1或-1现在插入后严重不平衡违反了左右高度差不超过1的规则就需要就地处理即旋转这颗子树旋转需要注意 让这颗子树旋转之后的高度差不超过1。旋转过程中需要保持仍是搜索树。更新调整孩子节点的平衡因子。让这颗子树的高度和插入前保持一致。
Insert代码
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){//新增在右parent-_bf//新增在左parent-_bf--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-_bf 2 || parent-_bf -2){//需要旋转这个子树代码和情况过多在三.AVL树的旋转中展示}else{assert(false);}}return true;}看完这部分代码直接看下一个一级标题AVL树的旋转。看完旋转之后再回来按照顺序依次看。 2.4 AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确
代码如下
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);
}2.5 AVL树的删除(了解) 因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不错与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。可以想象成插入的反向思考具体实现可参考《算法导论》或《数据结构-用面向对象方法与C描述》殷人昆版。 删除太难了别学了。
三.AVL树的旋转重要 旋转就是降低高度。 在2.3的插入中我们说到了一旦平衡因子超出了指定的范围就会导致子树左右高度差发生变化导致结构不再是高度平衡的状态此时这个子树就需要旋转旋转到没插入前的高度。对于旋转有很多种情况因此我把他单独拿出来作为一个大标题的形式来描述。
先不进行分类随便举个例子看看
可以看出旋转后的特征
让这颗子树旋转之后的高度差不超过1。旋转过程中需要保持仍是搜索树。更新调整孩子节点的平衡因子。让这颗子树的高度和插入前保持一致。
但实际上我们的AVL树可能会非常的复杂因此并不像上面的例子那么简单。
因此如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转根据不同的插入情况分为四种左单旋、右单旋、先左单旋再右单旋、先右单旋再左单旋。上面的例子就属于左单旋。
注插入的节点名字为cur。
3.1 左单旋
新节点插入较高右子树的右侧—右右左单旋 a, b, c都为AVL树且高度为h. 对于此图实际上是一个抽象图即a,b,c的高度都不是一个确切的数字。但从图中我们可以看出在c插入节点导致高度变化为h1这个时候30的平衡因子就变成了2。那为什么会左旋从抽象的角度来看对于高度平衡的AVL树右边过高我们就需要考虑不让右面高从绳子的角度来说右边过长那就将中间节点再往右移动对于这个模型也一样我们考虑根节点往右移动即将60作为根节点此时左子树就会往下可以看出这是一个将左子树往下压的过程通过这种角度的思考就不难对这种树进行旋转。
既然有了抽象的左旋从学习的角度同样要将这种AVL树的旋转具象化 如果h0那情况就正如我们一开始随便举的例子一样如果是根节点的1平衡因子不符合条件那就将右孩子通过旋转变成根节点右孩子的左孩子给到原来根节点的右孩子节点这样就完成了旋转同时满足了条件。 如果h1唯一与上面的情况不同的是平衡因子首先不满足条件的节点可能不会是根节点因此这种情况我们只需将这个不满足条件的节点作为需要旋转的子树的根就和上面的步骤一样。最后这个子树的新根的parent指针再连接回去。需要注意的细节问题是节点的parent指针。 如果h2那么情况就会变的很复杂因此上述抽象的结构我们提前将c确定形状在这我们具体实例化一下 对于红色的a, b来说都有三种的选择因此当h2时插入之前的组合情况就会有3*39种的结果在这种情况之下在c的任何一个子树下插入都会引发30这个节点的旋转而c的孩子节点有四个位置可以插入那一共就是9*436种情况。h继续增加只会更多因此也没必要将这么多种情况都画出来因为这些情况都属于上面抽象图的衍生都可以调用左旋转。 左单旋平衡因子的条件
if (parent-_bf 2 cur-_bf 1)
{RotateL(parent);//左单旋
}知道旋转的方法之后我们还需要将这种情况的具体步骤给总结出来
左单旋代码
void RotateL(Node* parent)//左单旋
{//1.记录subR, subRLNode* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)//subRL不为空则需要连接到parent{subRL-_parent parent;}subR-_left parent;Node* ppNode parent-_parent;//记录保存parent-_parent subR;if (ppNode nullptr)//说明根节点变化{_root subR;_root-_parent nullptr;}else//如果是局部子树{//判断ppNode之前是左连接还是右连接if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}//最后更新平衡因子:一定都为0parent-_bf subR-_bf 0;
}3.2 右单旋 新节点插入较高左子树的左侧—左左右单旋 右单旋平衡因子的条件
if (parent-_bf -2 cur-_bf -1)
{RotateR(parent);//右单旋
}和左单旋的思想是一样的只不过是将赋值的左右反过来。这里就直接上代码了
void RotateR(Node* parent)//右单旋
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;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.3 左右双旋
新节点插入较高左子树的右侧—左右先左单旋再右单旋 就如上面的抽象图我们仍然需要对其有所见解才能进一步分析并写出代码通过观察发现对具象的三个节点原本是折线通过左旋变成直线后发现就可以通过右旋从而实现AVL树的结构了。当然这么说还是过于敷衍下面将h具象化看看例子
如果h0则h-1的部分为-1但我们可以同样的认为他是不存在节点的如果h1和上面的情况几乎相似同3.1左单旋叙述的一样只是子树部分旋转需要注意parent指针这种情况是最普遍的。如果h2情况就如左单旋的h2的情况一样有非常多的情况出现因此这里只需明白抽象的具体树的旋转规则就可以了。 左右双旋平衡因子的条件
if (parent-_bf -2 cur-_bf 1)
{RotateLR(parent);
}下面来看看左右双旋的具体步骤 对于左右双旋上面的步骤不难看出先左旋parent的左孩子之后再右单旋旋转parent复用前面的左单旋和右单旋的代码即可。 但是关键还要修改旋转节点对应的平衡因子由于左单旋和右单旋改变了原有的平衡因子因此我们需要在左右单旋之前将需要改变的节点及对应的平衡因子的值给保留起来保留的目的是需要根据原有的平衡因子的值将旋转后对应的值进行改变。 如果插入后subLR-_bf -1即subLR的左子树插入上图就是这样旋转后的parent-_bf 1subL-_bf 0subLR-_bf 0 如果插入后subLR-_bf 1即subLR的右子树插入那么旋转后的parent-_bf 0subL-_bf -1subLR-_bf 0 如果插入后的subLR-_bf 0说明subLR本身就是新增节点则这三个平衡因子都为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){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf -1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else if (bf 0)//自己新增{subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else{assert(false);}
}可以看出左右双旋的平衡因子的更新才是关键。 3.4 右左双旋
新节点插入较高右子树的左侧—右左先右单旋再左单旋 正如右单旋按照左单旋的思路右左双旋就按照左右双旋的思路。 按照不同的情况画图就能准确的判断平衡因子的变化。 void RotateRL(Node* parent)//右左双旋
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);//右节点右旋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树完整代码
AVLTree.h
#pragma oncetemplateclass K, class V
struct AVLTreeNode//三叉链
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factor 平衡因子AVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};templateclass 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){//新增在右parent-_bf//新增在左parent-_bf--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-_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 if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else{cout parent-_kv.first : parent-_bf : cur-_bf endl;assert(false);}break;}else{assert(false);}}return true;}void RotateL(Node* parent)//左单旋{//1.记录subR, subRLNode* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)//subRL不为空则需要连接到parent{subRL-_parent parent;}Node* ppNode parent-_parent;//记录保存subR-_left parent;parent-_parent subR;if (ppNode nullptr)//说明根节点变化{_root subR;_root-_parent nullptr;}else//如果是局部子树{//判断ppNode之前是左连接还是右连接if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}//最后更新平衡因子:一定都为0parent-_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;subL-_right parent;parent-_parent subL;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){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf -1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else if (bf 0){subL-_bf 0;subLR-_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(parent-_right);//右节点右旋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);}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:void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}Node* _root nullptr;
};void TestAVLTree()
{//int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };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();}Test.c
#includeiostream
#includemap
#includestring
#includeassert.h
using namespace std;
#includeAVLTree.hint main()
{TestAVLTree();return 0;
}五. AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log2(N)log_2 (N)log2(N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
