河北建设网站,个人注册公司需要什么,seo实战指导,东莞模板建站平台上期博客我们讲解了set/multiset/map/multimap的使用#xff0c;下面我们来深入到底层#xff0c;讲解其内部结构#xff1a;
目录
一、AVL树的概念
二、AVL树的实现
2.1 节点的定义
2.2 数据的插入
2.2.1 平衡因子的调整
2.2.1.1 调整平衡因子的规律
2.2.2 子树的旋…上期博客我们讲解了set/multiset/map/multimap的使用下面我们来深入到底层讲解其内部结构
目录
一、AVL树的概念
二、AVL树的实现
2.1 节点的定义
2.2 数据的插入
2.2.1 平衡因子的调整
2.2.1.1 调整平衡因子的规律
2.2.2 子树的旋转调整
2.2.2.1 左单旋
2.2.2.2 右单旋
2.2.2.3 左右双旋
2.2.2.4 右左双旋
2.3 AVL树的检查验证
2.4 测试代码
三、AVL树实现的完整代码 一、AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
● 它的左右子树都是AVL树
● 左右子树高度之差简称平衡因子不是每种AVL树都有平衡因子平衡因子只是AVL树实现的一种方式的绝对值不超过1下图的平衡因子计算公式为节点的右子树高度-左子树高度
下图是一个AVL树 二、AVL树的实现
2.1 节点的定义
这次我们直接实现K-V模型的二叉树
templateclass Key,class Val
class AVLTreeNode
{
public:AVLTreeNodeKey, Val* _left;AVLTreeNodeKey, Val* _right;AVLTreeNodeKey, Val* _parent;//多一个指针指向其父节点,方便我们的后续操作pairKey, Val _kv;int _bf;//balance factor(平衡因子)AVLTreeNode(pairKey, Val kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};2.2 数据的插入
AVL树的数据插入需要遵循二叉搜索树的规律
templateclass Key, class Val
class AVLTree
{
public:typedef AVLTreeNodeKey, Val Node;bool Insert(const pairKey,Val kv){Node* cur _root, * 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{cout 插入的值重复 endl;return false;}}cur new Node(kv);cur-_parent parent;//将插入的节点连接上二叉树if (parent nullptr){_root cur;}else if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}return true;}private:AVLTreeNodeKey, Val* _root nullptr;
};但是成功插入数据后就结束了吗在AVL树中可没有这么简单我们需要更新其插入节点的父节点的平衡因子来保证这课树的整体结构还是一个AVL树。
2.2.1 平衡因子的调整
下面我们来讨论一下更新父节点平衡因子的操作 我们看到上面的二叉树现在向其中插入一个键值为8的数据 插入后我们发现其插入节点的父节点平衡因子需要修改那就要修改一下 修改其父节点后我们发现其父节点的父节点的平衡因子也需要调整那再调整一下吧 但是本次调整过后平衡因子出现了2这个数值但是平衡因子只能是1/0/-1说明这时该节点下的子树已经不满足AVL树的结构了这时要对其子树进行旋转来调整该树的结构至于怎么旋转我们在下面会详细讲解经过旋转过后子树肯定是满足AVL树的结构的所以就并不再检查进行旋转的节点父节点平衡因子了 那我们再看看另一种情况我们向下面的二叉树中插入键值为6的数据
插入后我们发现需要修改其父节点的平衡因子 修改后我们发现其父节点的平衡因子为0为0时就意味着子树的高度没有发生变化我们就没有必要再向上更新其父节点的平衡因子了 2.2.1.1 调整平衡因子的规律
所以总结一下上述规律我们插入节点后肯定是要调整其父节点的平衡因子的那调整父节点的平衡因子后什么时候要向上调整其父节点的父节点爷爷节点的平衡因子呢
这里有三种情况 当父节点的平衡因子调整过后为1或-1时此时说明其节点所在的子树的高度发生了变化变为1或-1前平衡因子只可能是0说明插入之前子树两边的高度是相同的这时在插入一个节点会导致其中一颗子树的高度发生变化这时需要再继续向上调整其父节点的平衡因子 当父节点的平衡因子调整过后为2或-2时该节点的子树不平衡需要处理这颗旋转处理子树旋转实质是是将该节点所在的子树的高度降1所以旋转过后不影响子树的高度变化此时就不需要再向上更新其父节点的平衡因子了 当父节点的平衡因子调整过后为0时变为0前平衡因子只可能是1或-1说明插入之前一边高一边低但是插入节点是在矮的那边其子树的高度不变说明所在的子树高度不变不用继续向上更新 我们用代码来实现一下平衡因子的调整
templateclass Key, class Val
class AVLTree
{
public:typedef AVLTreeNodeKey, Val Node;bool Insert(const pairKey,Val kv){Node* cur _root, * 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{cout 插入的值重复 endl;return false;}}cur new Node(kv);cur-_parent parent;//将插入的节点连接上二叉树if (parent nullptr){_root cur;}else if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}//向上调整各节点的平衡因子while (parent){if (parent-_left cur){--parent-_bf;//更新平衡因子}else{parent-_bf;//更新平衡因子}//根据父节点的平衡因子的情况决定师傅继续向上调整各节点的平衡因子if (parent-_bf 1 || parent-_bf -1)//平衡因子为1或1继续向上更新{parent parent-_parent;cur cur-_parent;}else if (parent-_bf 2 || parent-_bf -2)//平衡因子为2或-2,树的结构不平衡旋转parent节点所在子树{//旋转parent所在的子树}else if (parent-_bf 0)//平衡因子为0,插入结束{break;}else//出现其他的情况说明树的根据有问题报错退出{cout 树的结构出错了 endl;assert(0);exit(-1);}}return true;}private:AVLTreeNodeKey, Val* _root nullptr;
}; 2.2.2 子树的旋转调整
当某个节点的平衡因子变为2或-2时我们需要对其所在的子树进行旋转调整
下面我们分情况来讨论
2.2.2.1 左单旋
下面的图代表的是一棵AVL树其中52和60表示的两个节点A、B、C分别为高度为h的AVL子树 下面向C子树中插入数据使其高度发生变化 现在键值为52的节点平衡因子变为2下面我们要将这棵子树旋转 我们可以看到旋转的过程是这样的
B子树变成52的右子树-52变成60的左子树-60变成整颗树的根
上面这种需要旋转的树的根节点平衡因子为2并且其根节点右孩子节点的平衡因子为1这种情况下的旋转我们将其称为左单旋
下面我们就用代码实现一下左单旋
void RotateL(Node* parent)//左单旋
{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_right subRL;//更新parent的右节点if (subRL)//防止该节点为空{subRL-_parent parent;//更新subRL的父节点}parent-_parent subR;//更新parent的父节点subR-_left parent;//subR的左子树置为parentsubR-_parent pparent;//更新subR的父节点if (pparent nullptr)//旋转的是整棵树{_root subR;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}}subR-_bf parent-_bf 0;//更新平衡因子
}
下图是画出了代码所表示的节点 2.2.2.2 右单旋
再来看到另一种情况 下面向子树A中插入数据使其高度发生变化 现在键值为60的节点平衡因子变为-2下面我们要将这棵子树旋转 我们可以看到旋转的过程是这样的
B子树变成60的左子树-60变成52的右子树-52变成整颗树的根
上面这种需要旋转的树的根节点平衡因子为-2并且其根节点左孩子节点的平衡因子为-1这种情况下的旋转我们将其称为右单旋
下面我们用代码实现一下右单旋
void RotateR(Node* parent)//右单旋
{Node* subL parent-_left;Node* subLR subL-_right;Node* pparent parent-_parent;parent-_left subLR;//更新parent的左节点if (subLR)//防止该节点为空{subLR-_parent parent;//更新subLR的父节点}parent-_parent subL;//更新parent的父节点subL-_right parent;//subL的右子树置为parentsubL-_parent pparent;//更新subL的父节点if (pparent nullptr)//旋转的是整棵树{_root subL;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}}subL-_bf parent-_bf 0;//更新平衡因子
}
下图画出了代码所表示的节点 2.2.2.3 左右双旋
接着来看到稍微复杂一点的情况下面的图代表的是一棵AVL树其中99、66和88表示的是三个节点A、D分别为高度为h的AVL子树B、C分别为高度为h-1的AVL子树 现在我们向B子树中插入数据使其高度发生变化 现在键值为99的节点平衡因子变为-2下面我们要将这棵子树旋转
下面先将66所在子树进行左单旋 再让99所在子树右单旋 上面这种需要旋转的树的根节点平衡因子为-2并且其根节点左孩子节点的平衡因子为1这种情况下的两次旋转我们将其称为左右双旋
但是我们要注意的是当新增节点在C子树上时通过左右双旋调整后的结果又不一样 我们可以看到因为新增节点的位置发生了变化最终导致了各节点的平衡因子出现了差异
除了这两种情况还有一种当h为0的极端情况 所以我们在用代码实现的时要注意
void RotateLR(Node* parent)//左右双旋
{Node* subL parent-_left;Node* subLR subL-_right;int subLR_bf subLR-_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据RotateL(subL);//调用左单旋RotateR(parent);//调用右单旋if (subLR_bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (subLR_bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (subLR_bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else{assert(false);}
} 2.2.2.4 右左双旋
最后我们只剩一种情况了需要旋转的树的根节点平衡因子为-2并且其根节点右孩子节点的平衡因子为-1
下面我们来分析 我们向上面这棵树中的C子树插入数据使其高度发生变化 现在键值为66的节点平衡因子变为2下面我们要将这棵子树旋转
下面先将99所在子树进行右单旋 再将66所在子树进行左单旋
这样先右旋再左旋的情况我们将其称做右左双旋
和左右双旋一样新增节点的位置发生变化会导致各节点的平衡因子出现差异当新增节点在B子树上时通过左右双旋调整后的结果又不一样 另外还有h为0的特殊情况 好了分析到这里使用代码实现也就不是问题了
void RotateRL(Node* parent)//右左双旋
{Node* subR parent-_right;Node* subRL subR-_left;int subRL_bf subRL-_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据RotateR(subR);//调用右单旋RotateL(parent);//调用左单旋if (subRL_bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (subRL_bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (subRL_bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else{assert(false);}
} 2.3 AVL树的检查验证
下面我们来实现一个函数来检查自己所创建的AVL树是否符合规则
int _CountHeight(Node* root)//计算树的高度
{if (root nullptr)return 0;int leftnum _CountHeight(root-_left);int rightnum _CountHeight(root-_right);return leftnum rightnum ? leftnum 1 : rightnum 1;
}
bool _IsBalance(Node* root)
{if (root nullptr)return true;int leftH _CountHeight(root-_left);int rightH _CountHeight(root-_right);if (rightH - leftH ! root-_bf)//检查当前节点平衡因子是否正确{cout root-_kv.first 节点平衡因子异常 endl;return false;}return abs(leftH - rightH) 2 _IsBalance(root-_left) _IsBalance(root-_right);//检查左右子树高度之差的绝对值是否小于2
}
bool IsBalance()//检查是否为AVL树
{return _IsBalance(_root);
}
2.4 测试代码
void Test_AVLTree()
{const size_t N 5000;AVLTreeint, int t;for (size_t i 0; i N; i){size_t x rand() i;t.Insert(make_pair(x, x));}t.InOrder();cout t.IsBalance() endl;cout t.CountHeight() endl;
}
运行效果 三、AVL树实现的完整代码
#pragma once
#includeiostream
#includecassertusing namespace std;templateclass Key,class Val
class AVLTreeNode
{
public:AVLTreeNodeKey, Val* _left;AVLTreeNodeKey, Val* _right;AVLTreeNodeKey, Val* _parent;//多一个指针指向其父节点,方便我们的后续操作pairKey, Val _kv;int _bf;//balance factor(平衡因子)AVLTreeNode(const pairKey, Val kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};templateclass Key, class Val
class AVLTree
{typedef AVLTreeNodeKey, Val Node;public:bool Insert(const pairKey,Val kv){Node* cur _root, * 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{cout 插入的值重复 endl;return false;}}cur new Node(kv);cur-_parent parent;//将插入的节点连接上二叉树if (parent nullptr){_root cur;}else if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}//向上调整各节点的平衡因子while (parent){if (parent-_left cur){--parent-_bf;//更新平衡因子}else{parent-_bf;//更新平衡因子}//根据父节点的平衡因子的情况决定师傅继续向上调整各节点的平衡因子if (parent-_bf 1 || parent-_bf -1)//平衡因子为1或1继续向上更新{parent parent-_parent;cur cur-_parent;}else if (parent-_bf 2 || parent-_bf -2)//平衡因子为2或-2,树的结构不平衡旋转parent节点所在子树{//旋转parent所在的子树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{assert(false);}break;}else if (parent-_bf 0)//平衡因子为0,插入结束{break;}else//出现其他的情况说明树的根据有问题报错退出{cout 树的结构出错了 endl;assert(0);exit(-1);}}return true;}void InOrder()//中序遍历{_InOrder(_root);cout endl;}int CountHeight()//计算树的高度{return _CountHeight(_root);}bool IsBalance()//检查是否为AVL树{return _IsBalance(_root);}private:void RotateL(Node* parent)//左单旋{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_right subRL;//更新parent的右节点if (subRL)//防止该节点为空{subRL-_parent parent;//更新subRL的父节点}parent-_parent subR;//更新parent的父节点subR-_left parent;//subR的左子树置为parentsubR-_parent pparent;//更新subR的父节点if (pparent nullptr)//旋转的是整棵树{_root subR;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}}subR-_bf parent-_bf 0;//更新平衡因子}void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;Node* pparent parent-_parent;parent-_left subLR;//更新parent的左节点if (subLR)//防止该节点为空{subLR-_parent parent;//更新subLR的父节点}parent-_parent subL;//更新parent的父节点subL-_right parent;//subL的右子树置为parentsubL-_parent pparent;//更新subL的父节点if (pparent nullptr)//旋转的是整棵树{_root subL;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}}subL-_bf parent-_bf 0;//更新平衡因子}void RotateLR(Node* parent)//左右双旋{Node* subL parent-_left;Node* subLR subL-_right;int subLR_bf subLR-_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据RotateL(subL);//调用左单旋RotateR(parent);//调用右单旋if (subLR_bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if(subLR_bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (subLR_bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else{assert(false);}}void RotateRL(Node* parent)//右左双旋{Node* subR parent-_right;Node* subRL subR-_left;int subRL_bf subRL-_bf;//记录该节点的平衡因子来做旋转结束后的修改平衡因子的依据RotateR(subR);//调用右单旋RotateL(parent);//调用左单旋if (subRL_bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (subRL_bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (subRL_bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}void _InOrder(Node* root){if (root NULL)//如果是空树就直接结束{return;}_InOrder(root-_left);//先递归遍历其左子树cout root-_kv.first ;//再遍历其根节点_InOrder(root-_right);//最后递归遍历其右子树}int _CountHeight(Node* root)//计算树的高度{if (root nullptr)return 0;int leftnum _CountHeight(root-_left);int rightnum _CountHeight(root-_right);return leftnum rightnum ? leftnum 1 : rightnum 1;}bool _IsBalance(Node* root){if (root nullptr)return true;int leftH _CountHeight(root-_left);int rightH _CountHeight(root-_right);if (rightH - leftH ! root-_bf)//检查当前节点平衡因子是否正确{cout root-_kv.first 节点平衡因子异常 endl;return false;}return abs(leftH - rightH) 2 _IsBalance(root-_left) _IsBalance(root-_right);//检查左右子树高度之差的绝对值是否小于2}
private:AVLTreeNodeKey, Val* _root nullptr;
};
