酒生产企业网站建设的目的,高清免费素材网站,响应式网页设计最方便快速,家用电脑做网站目录
前言
一、AVL树的概念
二、AVL树节点的定义
三、AVL树的插入
四、AVL树的旋转
4.1 左单旋
4.2 右单旋
4.3 左右双旋
4.4 右左双旋
五、AVL树的验证
六、AVL树的性能
七、完整代码 前言 前面对 map/multimap/set/multiset 进行了简单的介绍#xff0c;在其文…目录
前言
一、AVL树的概念
二、AVL树节点的定义
三、AVL树的插入
四、AVL树的旋转
4.1 左单旋
4.2 右单旋
4.3 左右双旋
4.4 右左双旋
五、AVL树的验证
六、AVL树的性能
七、完整代码 前言 前面对 map/multimap/set/multiset 进行了简单的介绍在其文档介绍中发现这几个容器有个共同点是其底层都是按照红黑树二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树AVL树来实现
一、AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。 因此两位俄罗斯的数学家G.M.Adelson-Velskii和 E.M.Landis 在1962年发明了一种解决上述问题的方法 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度这棵树叫 AVL树 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)如果一棵二叉搜索树是高度平衡的它就是AVL树如果它有n个结点其高度可保持在O(logN)搜索时间复杂度O(logN)注意树中每个结点左右子树高度之差的绝对值不超过1AVL树接近于满二叉树满二叉树的每个结点左右子树高度之差均为0
二、AVL树节点的定义 AVL树这里直接使用键值对即 KV模型使用键值对是为了方便后面实现 set 和 map。AVL树节点的定义增加了一个指向父节点的指针变成了三叉链结构并且每个节点都增加了一个平衡因子一般是右子树高度 - 左子树高度平衡因子的初始化设置为0即可
//K:key V:Value
templateclass K, class V
struct AVLTreeNode
{//构造函数AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr), _parent(nullptr),_bf(0){}//成员变量pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factor 平衡因子
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:private:Node* _root nullptr;
};三、AVL树的插入 AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子
接下来按两个步骤进行解释
1进行插入节点
因为AVL树本身就是一棵二叉搜索树因此寻找结点的插入位置是非常简单的按照二叉搜索树的插入规则
待插入结点的key值比当前结点小就插入到该结点的左子树待插入结点的key值比当前结点大就插入到该结点的右子树待插入结点的key值与当前结点的 key 值相等就插入失败2更新平衡因子 插入完成后需要更新平衡因子 需要更新平衡因子的判断条件是是取决于该结点的左右子树的高度是否发生了变化 所以我们插入结点后需要倒着往上更新平衡因子更新规则如下
新增结点在parent的右边parent的平衡因子 新增结点在parent的左边parent的平衡因子 --
比如下图进行插入一个新节点祖先节点的平衡因子都可能发生变化 所以每更新完一个结点的平衡因子后都需要进行以下判断 如果 parent 的平衡因子等于-1或者1表明还需要继续往上更新平衡因子如果 parent 的平衡因子等于0表明无需继续往上更新平衡因子了如果parent的平衡因子等于 -2 或者 2表明此时以 parent 结点为根结点的子树已经不平衡了需要进行旋转处理注 parent 不是这三种情况插入有问题
平衡因子分析如下 parent的平衡因子更新后为-1或1只有0经过 -- 或 操作后会变成 -1/1说明新结点的插入使得 parent的左子树或右子树增高了即改变了以parent为根结点的子树的高度从而会影响parent的父结点的平衡因子因此需要继续往上更新平衡因子0只有-1/1经过 或 -- 操作后会变成0说明新结点插入到了parent左右子树当中高度较矮的一棵子树插入后使得 parent 左右子树的高度相等了此操作并没有改变以parent为根结点的子树的高度从而不会影响parent 的父结点的平衡因子因此无需继续往上更新平衡因子-2或2此时parent结点的左右子树高度之差的绝对值已经超过1了不满足AVL树的要求因此需要进行旋转处理 当parent的平衡因子为 -2或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-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else//cur-kv.first kv.first要插入值已经存在插入失败{return false;}}cur new Node(kv);//插入if (parent-_kv.first kv.first)//插入到parent左边{parent-_right cur;cur-_parent parent;}else//插入到parent右边{parent-_left cur;cur-_parent parent;}//进行更新平衡因子while (parent)//parent 为空说明已经更新到根节点{if (parent-_left cur)//新节点插入在parent左边{parent-_bf--;}else//新节点插入在parent右边{parent-_bf;}//继续更新平衡因子的依据根据子树的高度是否变化// 1parent-_bf 0 说明之前parent-_bf是 1 或者 -1说明之前parent一边高一边低// 这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新// 2parent-_bf 1 或 -1 说明之前是 parent-_bf 0两边一样高现在插入一边更高了// parent所在子树高度变了继续往上更新// 3parent-_bf 2 或 -2说明之前 parent-_bf 1 或者 -1现在插入严重不平衡违反规则// 需要就地处理 -- 旋转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)//第三种情况{// 旋转// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//旋转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);//双旋转右单旋后左单旋}break;}else//不是上面三种情况插入有问题{assert(false);}}return true;
}
四、AVL树的旋转
4.1 左单旋
左单旋的步骤如下
让 subR 的左子树作为parent的右子树让parent作为subR的左子树让subR作为整个子树的根更新平衡因子
以下图片为了方便演示用的都是抽象图即代表无数种情况
旋转示意图如下 旋后满足二叉搜索树的性质
subR的左子树当中结点的值本身就比 parent 的值大因此可以作为 parent 的右子树parent 及其左子树当中结点的值本身就比 subR 的值小因此可以作为 subR 的左子树
然后进行更新平衡因子平衡因子全部置为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;//记录parent节点的前一个节点subR-_left parent;parent-_parent subR;if (ppNode nullptr)//即subR已经是根节点{_root subR;_root-_parent nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode-_left parent)//parent原本在 ppNode 的左边{ppNode-_left subR;}else//parent原本在 ppNode 的右边{ppNode-_right subR;}subR-_parent ppNode;}//旋转完成更新平衡因子parent-_bf subR-_bf 0;
}
注意 结点是三叉链结构改变结点关系时需要跟着改变父指针的指向
4.2 右单旋
右单旋的步骤如下
让 subL 的右子树作为 parent 的左子树让 parent 作为 subL 的右子树让 subL 作为整个子树的根更新平衡因子
旋转示意图如下
注图片也是抽象图涵盖无数种情况 右单旋后满足二叉搜索树的性质
subL 的右子树当中结点的值本身就比 parent 的值小因此可以作为 parent 的左子树parent 及其右子树当中结点的值本身就比 subL 的值大因此可以作为 subL 的右子树然后进行更新平衡因子平衡因子全部置为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节点的前一个节点subL-_right parent;parent-_parent subL;if (ppNode nullptr)//即subL已经是根节点{_root subL;subL-_parent nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode-_left parent)//parent原本在 ppNode 的左边{ppNode-_left subL;}else//parent原本在 ppNode 的右边{ppNode-_right subL;}subL-_parent ppNode;}//旋转完成更新平衡因子parent-_bf subL-_bf 0;
}
注意 结点是三叉链结构改变结点关系时需要跟着改变父指针的指向
4.3 左右双旋
左右双旋的步骤如下
以 subL 为旋转点进行左单旋以 parent 为旋转点进行右单旋更新平衡因子
旋转示意图如下
1插入新节点 2 以 subL 为旋转点进行左单旋 注双旋转后平衡因子是不对的需要后序更新平衡因子
3以 parent 为旋转点进行右单旋 注双旋转后平衡因子是不对的需要后序更新平衡因子 左右双旋后满足二叉搜索树的性质左右双旋后实际上就是让 subLR 的左子树和右子树分别作为subL和parent的右子树和左子树再让subL和parent分别作为subLR的左右子树最后让 subLR 作为整个子树的根结合图理解
4更新平衡因子 左右双旋之后需要进行更新平衡因子正确更新平衡因子的关键是记录没有旋转之前 subLR 节点的平衡因子该平衡因子用于判断以下三种情况 subLR 的平衡因子为1时说明 subLR 的右子树是新增节点左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、-1、0subLR 的平衡因子为-1时说明 subLR 的左子树是新增节点左右双旋后 parent、subL、subLR 的平衡因子分别更新为1、0、0subLR 的平衡因子为0时说明 subLR 自己就是新增节点左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0如图
1 subLR -1 2 subLR 1 3 subLR 0 注意 subLR 自己就是新增节点时其他情况都不会存在 subLR 不是这三种情况插入有问题
左右双旋的代码如下
//双旋转左单旋后右单旋
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//用于判断平衡因子的更新RotateL(parent-_left);RotateR(parent);//需要更新平衡因子if (bf -1)//subLR 的左子树新增{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else if (bf 1)//subLR 的右子树新增{subL-_bf -1;parent-_bf 0;subLR-_bf 0;}else if (bf 0)//subLR 自己就是新增{subL-_bf 0;parent-_bf 0;subLR-_bf 0;}else//不是上面三种情况插入有问题{assert(false);}
}
4.4 右左双旋
右左双旋的步骤如下
以 subR 为旋转点进行右单旋以 parent 为旋转点进行左单旋更新平衡因子
旋转示意图如下
1插入新节点 2以 subR 为旋转点进行右单旋 3以 parent 为旋转点进行左单旋 注双旋转后平衡因子是不对的需要后序更新平衡因子 右左双旋后满足二叉搜索树的性质右左双旋后实际上就是让subRL的左子树和右子树分别作为parent和subR的右子树和左子树再让parent和subR分别作为subRL的左右子树最后让subRL作为整个子树的根结合图理解
4更新平衡因子 右左双旋之后需要进行更新平衡因子正确更新平衡因子的关键是记录没有旋转之前 subLR 节点的平衡因子该平衡因子用于判断以下三种情况与左右双旋一致右左双旋就是在另一边 subLR 的平衡因子为1时说明 subLR 的右子树是新增节点左右双旋后 parent、subL、subLR 的平衡因子分别更新为 -1、0、0subLR 的平衡因子为-1时说明 subLR 的左子树是新增节点左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、1、0subLR 的平衡因子为0时说明 subLR 自己就是新增节点左右双旋后parent、subL、subLR的平衡因子分别更新为 0、0、0平衡因子更新如图
1 subLR 1 2 subLR -1 3 subLR 0 注意 subLR 自己就是新增节点时其他情况都不会存在 subLR 不是这三种情况插入有问题
右左双旋的代码如下
//双旋转右单旋后左单旋
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;//用于判断平衡因子的更新RotateR(parent-_right);RotateL(parent);//需要更新平衡因子if (bf -1)//subRL 的左子树新增{subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 1)//subRL 的右子树新增{subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf 0)//subLR 自己就是新增{subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else//不是上面三种情况插入有问题{assert(false);}
}
五、AVL树的验证 AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
1验证其为二叉搜索树
如果中序遍历可得到一个有序的序列就说明为二叉搜索树
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);
}
2验证其为平衡树
每个节点子树高度差的绝对值不超过1进行验证节点的平衡因子是否计算正确结果为 true 平衡因子正常
//判断平衡因子是否异常
bool IsBalance()
{return IsBalance(_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(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);
}
注AVL树其他接口就不实现了掌握插入即可面试也比较关注AVL树的插入即AVL树如何进行调平衡
六、AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 logN以2为底。 但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。 因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合
七、完整代码 AVLTree.h #pragma once//K:key V:Value
templateclass K, class V
struct AVLTreeNode
{//构造函数AVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr), _parent(nullptr),_bf(0){}//成员变量pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factor 平衡因子
};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-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else//cur-kv.first kv.first要插入值已经存在插入失败{return false;}}cur new Node(kv);//插入if (parent-_kv.first kv.first)//插入到parent左边{parent-_right cur;cur-_parent parent;}else//插入到parent右边{parent-_left cur;cur-_parent parent;}//进行更新平衡因子while (parent)//parent 为空说明已经更新到根节点{if (parent-_left cur)//新节点插入在parent左边{parent-_bf--;}else//新节点插入在parent右边{parent-_bf;}//继续更新平衡因子的依据根据子树的高度是否变化// 1parent-_bf 0 说明之前parent-_bf是 1 或者 -1说明之前parent一边高一边低// 这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新// 2parent-_bf 1 或 -1 说明之前是 parent-_bf 0两边一样高现在插入一边更高了// parent所在子树高度变了继续往上更新// 3parent-_bf 2 或 -2说明之前 parent-_bf 1 或者 -1现在插入严重不平衡违反规则// 需要就地处理 -- 旋转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)//第三种情况{// 旋转// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//旋转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);//双旋转右单旋后左单旋}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;//记录parent节点的前一个节点subR-_left parent;parent-_parent subR;if (ppNode nullptr)//即subR已经是根节点{_root subR;_root-_parent nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode-_left parent)//parent原本在 ppNode 的左边{ppNode-_left subR;}else//parent原本在 ppNode 的右边{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节点的前一个节点subL-_right parent;parent-_parent subL;if (ppNode nullptr)//即subL已经是根节点{_root subL;subL-_parent nullptr;}else//subR不是根节点{//与上一个节点进行链接if (ppNode-_left parent)//parent原本在 ppNode 的左边{ppNode-_left subL;}else//parent原本在 ppNode 的右边{ppNode-_right subL;}subL-_parent ppNode;}//旋转完成更新平衡因子parent-_bf subL-_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)//subLR 的左子树新增{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else if(bf 1)//subLR 的右子树新增{subL-_bf -1;parent-_bf 0;subLR-_bf 0;}else if (bf 0)//subLR 自己就是新增{subL-_bf 0;parent-_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(parent-_right);RotateL(parent);//需要更新平衡因子if (bf -1)//subRL 的左子树新增{subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 1)//subRL 的右子树新增{subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf 0)//subLR 自己就是新增{subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else//不是上面三种情况插入有问题{assert(false);}}//void InOrder(){_InOrder(_root);}//判断平衡因子是否异常bool IsBalance(){return IsBalance(_root);}
private: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(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;
};Test.cpp #include iostream
using namespace std;
#include assert.h
#include AVLTree.hvoid TestAVLTree1()
{//int arr[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int t;for (auto e : arr){t.Insert(make_pair(e, e));}t.InOrder();
}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));//cout t.IsBalance() endl;}//判断平衡因子是否异常cout t.IsBalance() endl;
}int main()
{//TestAVLTree1();TestAVLTree2();return 0;
}
----------------我是分割线---------------
文章到这里就结束了下一篇即将更新
