centos nginx wordpress,网站的优化策略,官方网站建设银行年利息是多少钱,摄影师 网站 模板AVLTree模拟实现 1 前言2 AVL树的插入2.1 平衡因子不继续向上更新的情况2.2 平衡因子变为2或者-2#xff0c;发生旋转2.2.1 左单旋2.2.2 右单旋2.2.3 左右双旋2.2.4 右左双旋 3 代码 1 前言 二叉搜索树的不足#xff1a;如果出现极端情况#xff0c;效率会变得很低。 AVL发生旋转2.2.1 左单旋2.2.2 右单旋2.2.3 左右双旋2.2.4 右左双旋 3 代码 1 前言 二叉搜索树的不足如果出现极端情况效率会变得很低。 AVL二叉平衡搜索树 平衡因子右子树的高度 - 左子树的高度 平衡因子绝对值不超过1(-1, 0, 1) 1.平衡因子为什么不是0而是 -1 0 1 做不到两个节点的时候不能相等四个节点也做不到 AVL树的效率 增删查改高度次 O(log N) 满二叉树2^h - 1 N AVL树2^h - x N x的范围[1, 2^(h - 1) - 1]
2 AVL树的插入
2.1 平衡因子不继续向上更新的情况 插入的原则 新增在左parent的平衡因子– 新增在右parent的平衡因子 从这里可以看出当平衡因子的值为 -1 或者 1 的时候并不会停止向上更新。 只有当平衡因子更新为0的时候才不会继续往上更新了。
2.2 平衡因子变为2或者-2发生旋转 当平衡因子的值更新为 -2或者2的时候就代表这棵树不平衡了就需要进行旋转。这时候更新也停止了因为要进行旋转了 2.什么情况要继续往上更新更新结束的条件 更新后的parent平衡因子0说明parent所在的子树的高度不变不会再影响祖先不用再继续往上更新 更新后的parent平衡因子 1 或者 -1说明parent所在的子树的高度发生改变会影响祖先要继续往上更新 更新后的parent平衡因子 2 或者 -2说明parent所在的子树的高度发生改变且不平衡想办法调整平衡对parent所在子树进行旋转让他平衡 更新到根节点 -- 更新结束
2.2.1 左单旋
发生左单旋的情况(具体图某一种情况)
发生左单旋的抽象图(有很多种情况)
什么情况会发生左单旋 在右边高的情况下往右边插入。 转化成代码就是在插入之后parent-_bf 2 cur-_bf 1.这里parent-_bf 2说明是右边高如果parent-_bf -2说明是左边高。 总结 cur-left 比 parent大所以cur-left做parent的右没有问题 cur-left比cur小所以cur-left做cur的左没有问题
核心操作 parent-right cur-left cur-left parent;
2.2.2 右单旋
发生右单旋的情况具体图 发生右单旋的抽象图有很多种情况
旋转 右边高 -- 往左边旋转 左边高 -- 往右边旋转
旋转的时候要注意的问题 保持他是搜索树变成平衡树且降低这个子树的高度 2.2.3 左右双旋
左右双旋的情况 当父节点左边高并且当前节点的右边高时就会发生左右双旋。 双旋平衡因子的更新 区分的关键看插入节点的父节点的平衡因子 平衡因子的三种情况h 0, h 0。h 0又分为两种情况插入节点是父节点的左子树或者插入节点是父节点的右子树 2.2.4 右左双旋
右左双旋 当父节点的右边高并且当前节点的左边高时就会发生右左双旋 如何分清是单旋还是双旋 单旋单纯的一边高左边高或者右边高 双旋有折现的产生。
3 代码
AVLTree.h
#pragma once
#include iostream
#include assert.h
using namespace std;template class K, class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;//new一个AVLTreeNode节点的时候就会调用这个构造函数// 如果传入参数就是kvAVLTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template class 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-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{assert(插入相同的节点);}}//走到这里找到了要插入的位置 -- 将cur插入进去cur new Node(kv);if (cur-_kv.first parent-_kv.first)parent-_left cur;elseparent-_right cur;//因为是三叉链所以cur的_parent指针还要指回去cur-_parent parent;//走到这里插入完成了。需要检查平衡因子判断是否平衡不平衡要进行旋转while (parent){//插入的位置是左孩子bf--;插入的位置是右孩子bfif (cur parent-_left)parent-_bf--;elseparent-_bf;//接下来要判断根据不同的平衡因子进行不同的更新的情况if (parent-_bf 0){break; //如果是0 就不用更新了}else if (parent-_bf -1 || parent-_bf 1) //如果插入之后parent的平衡因子等于-1或者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){//父节点右边高当前节点左边高 -- 右左双旋RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){//父节点左边高当前节点右边高 -- 左右双旋RotateLR(parent);}else{assert(平衡因子出错);}break;}else{assert(平衡因子出错);}}return true;}void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;//1.把curleft给parent的right -- parent的_right指向curleftparent-_right curleft;//判断curleft是否为空如果不为空就curleft的父节点指回去if (curleft){curleft-_parent parent;}//2.parent的right给cur的left -- cur的_left指向parentcur-_left parent;//3.判断parent是不是当前的根节点,如果是cur的_parent就为空。如果不是cur的_parent还要指向ppnodeNode* ppnode parent-_parent;//4.parent还要往回指因为是三叉链parent-_parent cur;if (parent _root) //如果是根节点{_root cur;cur-_parent nullptr;}else{//如果不是根节点就要判断是ppnode的左孩子还是右孩子if (ppnode-_left parent)ppnode-_left cur;elseppnode-_right cur;//往回指cur-_parent ppnode;}//更新平衡因子parent-_bf cur-_bf 0;}void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;//1.让parent的左指向cur的右parent-_left curright;if (curright){//第一次往回指curright-_parent parent;}//找到parent的父节点Node* ppnode parent-_parent;//2.cur的右指向parentcur-_right parent;//第二次往回指parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{parent-_parent cur;if (ppnode-_left parent)ppnode-_left cur;elseppnode-_right cur;//第三次往回指cur-_parent ppnode;}//更新平衡因子cur-_bf parent-_bf 0;}//左右双旋void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;RotateL(cur);RotateR(parent);//根据不同的情况修改平衡因子if (bf 0){cur-_bf 0;parent-_bf 0;curright-_bf 0;}else if (bf 1) //说明左边低右边高{parent-_bf 0;cur-_bf -1;curright-_bf 0;}else if (bf -1){parent-_bf 1;cur-_bf 0;curright-_bf 0;}else{assert(RotateLR false);}}void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf; //提前保存下来RotateR(cur);RotateL(parent);if (bf 0){cur-_bf 0;parent-_bf 0;curleft-_bf 0;}else if (bf 1) //说明插入的位置是curleft的右边{parent-_bf -1;cur-_bf 0;curleft-_bf 0;}else if (bf -1) //插入的位置是curleft的左边{parent-_bf 0;cur-_bf 1;curleft-_bf 0;}else{assert(RotateRL false);}}//bool Erase(const pairK, V key)//{//}int Height(){return Height(_root);}int Height(Node* root){if (root nullptr)return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr)return true;int leftHight Height(root-_left);int rightHight Height(root-_right);if (rightHight - leftHight ! root-_bf){cout 平衡因子异常: root-_kv.first - root-_bf endl;return false;}return abs(rightHight - leftHight) 2 IsBalance(root-_left) IsBalance(root-_right);}void Inorder(){_Inorder(_root);}private:void _Inorder(Node* cur){if (cur nullptr)return;_Inorder(cur-_left);cout cur-_kv.first : cur-_kv.second : cur-_bf endl;_Inorder(cur-_right);}
private:Node* _root nullptr;
};
Test_AVLTree.cpp
#include AVLTree.hvoid testAVL1()
{int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));}t.IsBalance();t.Inorder();
}int main()
{testAVL1();return 0;
}
