培训教材网站建设,网页游戏平台网站,wordpress 增加字体,成都中小企业网站建设公司我们上期提到了二叉搜索树#xff0c;只是简单的讲了一下原理#xff0c;那么今天我们就讲一下AVL树。 目录 AVL树的概念AVL树的实现AVL树的架构insert插入引用pair对象引进parent指针仅插入数据调节平衡因子情况1#xff1a;插入在父亲的右边#xff0c;父亲的平衡因子后…我们上期提到了二叉搜索树只是简单的讲了一下原理那么今天我们就讲一下AVL树。 目录 AVL树的概念AVL树的实现AVL树的架构insert插入引用pair对象引进parent指针仅插入数据调节平衡因子情况1插入在父亲的右边父亲的平衡因子后为0情况2插入在父亲的左边父亲的平衡因子--后为0情况3插入左或者右恰巧父亲不是0是-1/1情况4当父亲的平衡因子-2/2不需要在更新了证明不平衡了需要旋转。左边高右旋右边高左旋双旋转右左旋转先右旋然后左旋。左右双旋先左旋在右旋。 中序遍历判断是否平衡AVL树整体代码 AVL树的概念
其实大家应该很奇怪难道二叉搜索树不能存储数据吗为什么要有AVL树呢二叉搜索树有可能会有畸形的情况。像下图数据比较分散的话这棵树很正常如果我们插入的数相对有序就会变成右边那样畸形的树。 这个时候就需要人工干预这里的AVL数就可以更好的控制这个情况它有自己的平衡规则左右子树高度之差(平衡因子)绝对不超过1(-1,0,1)。如果不满足这个规则那么我们就旋转。
AVL树的实现
因为AVL树也是二叉搜索树的一种所以他也要满足二叉搜索树的条件然后在满足他自己的平衡规则。
AVL树的架构
其实数的节点架构和整体架构并没有变只是多了一个bf(平衡因子)用来调节平衡。
struct AVLTreeNode
{AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pairK, V _kv;int _bf;
};
templateclass K,class V
class AVLTree
{public:typedef AVLTreeNodeK,V Node;private:Node* _rootnullptr;
}insert插入
引用pair对象
这里与原来不同这里我们引入了一个pair对象那么pair是什么我们用pair来实现KV结构在库中的map也是用pair也完成KV结构的所以这里我们就用这pair。pair对象的first是K值second是V值。
引进parent指针
这里引用父指针是因为我们将来要旋转要不断向上调节平衡因子因为当我们插入某个值有可能引起平衡因子失衡。
仅插入数据
其实插入部分和我们之前写的一样只不过要注意的是我们的值存的是pair对象要像拿到K值需要 _kv.first拿到K值。一定要遵循二叉搜索树的规律左子树比根小右子树比根大。 if (_root nullptr){//插入第一个值Node* newNode new Node(kv);_root newNode;return true;}Node* newNode new Node(kv);Node* cur _root;Node* parent cur;while (cur){if (cur-_kv.first newNode-_kv.first){//大于在右边parent cur;cur cur-_right;}else if (cur-_kv.first newNode-_kv.first){//小于在左边parent cur;cur cur-_left;}else{//等于,二叉搜索树不允许冗余所以直接返回false。return false;}}if (parent-_kv.first newNode-_kv.first){//在左边parent-_left newNode;}else{//在右边parent-_right newNode;}newNode-_parent parent;调节平衡因子
情况1插入在父亲的右边父亲的平衡因子后为0
红色是我插入的数插入后它的parent12从-1加加后变成了0我们还需要向上更新吗答案是不需要向上更新为什么0表示左右子树的高度差为0也就说高度没有变所以我不需要再向上更新。 解释平衡因子原来是1/-1都表示这个树缺了一个节点当我们插入之后正好填上了这个节点但是高度并不变。看图我把15插入右子树这个高度没有变。
情况2插入在父亲的左边父亲的平衡因子–后为0
当我插入在左边那我们就需要给父亲的因子bf–。
情况3插入左或者右恰巧父亲不是0是-1/1
父亲的平衡因子1/-1父亲所在子树高度变了。高度变了继续向上更新。
情况4当父亲的平衡因子-2/2不需要在更新了证明不平衡了需要旋转。
这个时候就不满足AVL树的规则了就需要旋转。
左边高右旋
这个树就是左边高的情况你会发现parent为-2cur为-1这个情况就是左边比右边要高那么我们需要右旋。 右旋的口诀把cur的右边给parent的左边cur的右边链接parent在让parent的parent链接cur。会发现我们把原来的parent变成了cur的右边。并且现在是平衡的。
其实为什么要把cur的右边给parent呢是因为cur的右边时当前树最大的值cur给了parent链接到左边依然不会破坏二叉搜索树的规则。
void RotateR(Node* parent )
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}parent-_bf subL-_bf 0;
}右边高左旋
当我们插入红色节点的时候就会导致右边过高那么我们就需要左旋。
左旋的口诀让cur的左边给parent的右边链接然后让父亲变成cur的左边。 解释为什么要把cur左边的值给parent的右边cur当前位置是parent的右边cur的左边也是比parent大的值给parent的右边依然不影响二叉搜索树的规则。
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if(subRL)subRL-_parent parent;subR-_left parent;Node* pphead parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (pphead-_parent parent){pphead-_right subR;}else{pphead-_left subR;}subR-_parent pphead;}subR-_bf parent-_bf 0;
}双旋转
还有一种情况它并不是单纯的一边高用单旋并不能解决问题。当我们仅仅只是单旋会发现他有变成了形态不同但是问题一样的情况这个时候就需要双旋。
右左旋转先右旋然后左旋。
既然我们单旋解决不了问题我们可以把他变成一边高然后进行单旋。 如这个图我们可以对subR进行右旋后在对parent左旋就可以了。 右左双旋后 但是有个问题平衡因子我们应该如何更新你可能会说这种情况不是正好满足左旋/右旋后平衡因子变成0吗但是如果其他位置都有节点呢接下来我们抽象图给大家演示一下。 当我们插入节点的位置不同你会发现每一个平衡因子也不一样。如图我插在了右边。这个时候我通过右左双旋就会得到下图。如最右图的红色平衡因子应该变成这个情况。所以说插入的位置不同平衡因子也会不同。 如图假如我插在了左边。会发现平衡因子又不一样了。所以我们并不能用一个例子来概括所有。 那么我们应该怎么做呢其实从我们画图你会发现我们改变的只不过是parent 、subR、sunRL这三个节点的因子其他的并没有改变。并且跟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 0){//新插入的parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf 1){//右边插入的subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if(bf-1){//在左边插入的parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else{assert(false);}}左右双旋先左旋在右旋。
图下是左右双旋。
当然了我们依然需要分析平衡因子所以我们依然要分析插入在哪个位置。 如图当插入在右边。
如图当我们插在左边。 void RotateLR(Node* parent){//左右双旋//平衡因子需要单独调节Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//先左旋在右旋RotateL(parent-_left);RotateR(parent);//重新计算调节因子if (bf 0){//当且节点就是新插的subL-_bf 0;parent-_bf 0;subLR-_bf 0;}else if(bf1){//在当前节点的右边插入的parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if(bf -1){subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else{assert(false);}}中序遍历
因为二叉搜索树我们都是中序遍历因为中序遍历更接近有序。
void _Inorder(Node* root)
{if (root nullptr){return;}_Inorder(root-_left);cout root-_kv.first : root-_kv.secondendl;_Inorder(root-_right);
}判断是否平衡
什么时候不平衡是不是因子大于等于2的时候所以我们需要算左右树的高度相减如果超过2那就是不平衡。 bool _isBalance(Node* root){if (root nullptr){return true;}int left _Height(root-_left);int right _Height(root-_right);if (abs(left - right) 2) return false;//因子大于等于2的时候不平衡return _isBalance(root-_left) _isBalance(root-_right);}int _Height(Node* root){if (root nullptr)return 0;int left _Height(root-_left);int right _Height(root-_right);return max(left, right) 1;}AVL树整体代码
以下是整个AVL树所有的代码 问题为什么没有像库一样写删除呢答我们模拟实现其实是为了了解底层并不是要超过底层因为现有的库已经很好了我们没必要写一个。二叉搜索树很少用删除接口。所以这里没有实现。 #pragma once
#includeiostream
#includevector
#includestring
#includeassert.husing namespace std;
namespace KV
{templateclass K,class Vstruct AVLTreeNode{AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pairK, V _kv;int _bf;};templateclass K,class Vclass AVLTree{public:typedef AVLTreeNodeK,V Node;bool insert(const pairK, V kv){if (_root nullptr){//插入第一个值Node* newNode new Node(kv);_root newNode;return true;}Node* newNode new Node(kv);Node* cur _root;Node* parent cur;while (cur){if (cur-_kv.first newNode-_kv.first){//大于在右边parent cur;cur cur-_right;}else if (cur-_kv.first newNode-_kv.first){//小于在左边parent cur;cur cur-_left;}else{//等于,二叉搜索树不允许冗余所以直接返回false。return false;}}if (parent-_kv.first newNode-_kv.first){//在左边parent-_left newNode;}else{//在右边parent-_right newNode;}newNode-_parent parent;cur newNode;while (parent){if (parent-_left cur){cur-_parent-_bf--;}else if (parent-_right cur){cur-_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){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);}else{assert(false);}}else{//按道理说不可能有这种情况但是保不准会有bugassert(false);break;}}return true;}void Inorder(){_Inorder(_root);}int Height(){return _Height(_root);}bool isBalance(){return _isBalance(_root);}private:int _Height(Node* root){if (root nullptr)return 0;int left _Height(root-_left);int right _Height(root-_right);return max(left, right) 1;}bool _isBalance(Node* root){if (root nullptr){return true;}int left _Height(root-_left);int right _Height(root-_right);if (abs(left - right) 2) return false;return _isBalance(root-_left) _isBalance(root-_right);}void RotateRL(Node* parent){//右左双旋//平衡因子需要自己调节Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf 0){//新插入的parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf 1){//右边插入的subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if(bf-1){//在左边插入的parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else{assert(false);}}void RotateLR(Node* parent){//左右双旋//平衡因子需要单独调节Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//先左旋在右旋RotateL(parent-_left);RotateR(parent);//重新计算调节因子if (bf 0){//当且节点就是新插的subL-_bf 0;parent-_bf 0;subLR-_bf 0;}else if(bf1){//在当前节点的右边插入的parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if(bf -1){subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else{assert(false);}}void RotateR(Node* parent ){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}parent-_bf subL-_bf 0;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if(subRL)subRL-_parent parent;subR-_left parent;Node* pphead parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (pphead-_parent parent){pphead-_right subR;}else{pphead-_left subR;}subR-_parent pphead;}subR-_bf parent-_bf 0;}void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_kv.first : root-_kv.second 因子 root-_bf endl;_Inorder(root-_right);}Node* _rootnullptr;};
}
