WordPress网站修改,做基因表达热图的网站,开发三味是啥,视频软件#x1f308;个人主页#xff1a;秋风起#xff0c;再归来~#x1f525;系列专栏#xff1a;C从入门到起飞 #x1f516;克心守己#xff0c;律己则安
目录 1. AVL的概念
2. AVL树的实现 2.1 AVL树的结构 2.2 AVL树的插⼊
AVL树插⼊⼀个值的⼤概过程
个人主页秋风起再归来~系列专栏C从入门到起飞 克心守己律己则安
目录 1. AVL的概念
2. AVL树的实现 2.1 AVL树的结构 2.2 AVL树的插⼊
AVL树插⼊⼀个值的⼤概过程
平衡因⼦更新
插⼊结点及更新平衡因⼦的代码实现
2.3 旋转
2.3.1 旋转的原则
2.3.2 右单旋 2.3.3 右单旋代码实现
2.3.4 左单旋
2.3.5 左单旋代码实现
2.3.6 左右双旋
2.3.7左右双旋代码实现
2.3.8 右左双旋
2.3.9 右左双旋代码实现
2.4 AVL树的查找
2.5 AVL树平衡检测
3. 源码
4、完结散花 1. AVL的概念
• AVL树是最先发明的⾃平衡⼆叉查找树AVL是⼀颗空树或者具备下列性质的⼆叉搜索树它的 左右⼦树都是AV树且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树 通过控制⾼度差去控制平衡。
• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家他们在1962 年的论⽂《An algorithm or the organization of information》中发表了它。
• AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念每个结点都有⼀个平衡因⼦任何 结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度也就是说任何结点的平衡因⼦等于0/1/-1 AVL树并不是必须要平衡因⼦但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡 就像⼀个⻛向标⼀样。
• 思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树要求⾼度差不超过1⽽不是⾼度差是0呢0不是更 好的平衡吗画画图分析我们发现不是不想这样设计⽽是有些情况是做不到⾼度差是0的。⽐ 如⼀棵树是2个结点4个结点等情况下⾼度差最好就是1⽆法作为⾼度差是0
• AVL树整体结点数量和分布和完全⼆叉树类似⾼度可以控制在 那么增删查改的效率也可 以控制在相⽐⼆叉搜索树有了本质的提升。 2. AVL树的实现 2.1 AVL树的结构
节点的结构
templateclass K,class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNode* _parent;AVLTreeNode* _right;AVLTreeNode* _left;int _bf;//平衡因子AVLTreeNode(const pairK,V kv):_kv(kv), _parent(nullptr), _right(nullptr),_left(nullptr),_bf(0){}
};
树的结构
templateclass K, class V
class AVLTree
{
public:typedef AVLTreeNodeK,V Node;//......private:Node* _rootnullptr;
}; 2.2 AVL树的插⼊
AVL树插⼊⼀个值的⼤概过程
1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。
2. 新增结点以后只会影响祖先结点的⾼度也就是可能会影响部分祖先结点的平衡因⼦所以更新 从新增结点-根结点路径上的平衡因⼦实际中最坏情况下要更新到根有些情况更新到中间就可 以停⽌了具体情况我们下⾯再详细分析。
3. 更新平衡因⼦过程中没有出现问题则插⼊结束
4. 更新平衡因⼦过程中出现不平衡对不平衡⼦树旋转旋转后本质调平衡的同时本质降低了⼦树 的⾼度不会再影响上⼀层所以插⼊结束
平衡因⼦更新
更新原则
• 平衡因⼦右⼦树⾼度-左⼦树⾼度
• 只有⼦树⾼度变化才会影响当前结点平衡因⼦。
• 插⼊结点会增加⾼度所以新增结点在parent的右⼦树parent的平衡因⼦新增结点在 parent的左⼦树parent平衡因⼦--
• parent所在⼦树的⾼度是否变化决定了是否会继续往上更新
更新停⽌条件
• 更新后parent的平衡因⼦等于0更新中parent的平衡因⼦变化为-1-0或者1-0说明更新前 parent⼦树⼀边⾼⼀边低新增的结点插⼊在低的那边插⼊后parent所在的⼦树⾼度不变不会 影响parent的⽗亲结点的平衡因⼦更新结束。 • 更新后parent的平衡因⼦等于1或-1更新前更新中parent的平衡因⼦变化为0-1或者0--1说 明更新前parent⼦树两边⼀样⾼新增的插⼊结点后parent所在的⼦树⼀边⾼⼀边低parent所 在的⼦树符合平衡要求但是⾼度增加了1会影响arent的⽗亲结点的平衡因⼦所以要继续向上 更新。 • 更新后parent的平衡因⼦等于2或-2更新前更新中parent的平衡因⼦变化为1-2或者-1--2说 明更新前parent⼦树⼀边⾼⼀边低新增的插⼊结点在⾼的那边parent所在的⼦树⾼的那边更⾼ 了破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理旋转的⽬标有两个
1、把 parent⼦树旋转平衡。
2、降低parent⼦树的⾼度恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新插⼊结束。 插⼊结点及更新平衡因⼦的代码实现 bool insert(const pairK, V kv){//如果树为空直接在根插入if (_root nullptr){_root new Node(kv);return true;}//树不为空先按照搜索树规则找到插入位置Node* parent nullptr;Node* cur _root;while (cur){//插入的key小就往左走if (kv.first cur-_kv.first){parent cur;cur cur-_left;}//大就往右走else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else//不支持键值冗余{return false;}}//找到在parent插入的位置了cur new Node(kv);if (kv.first parent-_kv.first)parent-_left cur;elseparent-_right cur;//不要忘记链接新增节点的parentcur-_parent parent;//开始更新平衡因子while (parent){if (parent-_left cur)parent-_bf--;elseparent-_bf;//_bf从1或-1到0,不会影响祖先节点if (parent-_bf 0){break;}//_bf从0到1或-1会影响祖先节点继续向上更新else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}//平衡破坏旋转恢复平衡else if (parent-_bf 2 || parent-_bf -2){//旋转逻辑//........break;//旋转完后该节点的平衡因子为0无需向上更新}else//非预想平衡因子直接断死{assert(false);}}return true;}
2.3 旋转
2.3.1 旋转的原则
1. 保持搜索树的规则
2. 让旋转的树从不满⾜变平衡其次降低旋转树的⾼度 旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。
说明下⾯的图中有些结点我们给的是具体值如10和5等结点这⾥是为了⽅便讲解实际中是什 么值都可以只要⼤⼩关系符合搜索树的规则即可。
2.3.2 右单旋
具象图 抽象图 2.3.3 右单旋代码实现
//右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;Node* pParent parent-_parent;parent-_left subLR;if(subLR)//如果不为空subLR-_parent parent;subL-_right parent;parent-_parent subL;if (pParent nullptr){_root subL;subL-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}parent-_bf subL-_bf 0;
}
2.3.4 左单旋
具象图 抽象图 2.3.5 左单旋代码实现
//左单旋
void RotateL(Node* parent)
{Node* pParent parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;subR-_left parent;parent-_parent subR;parent-_right subRL;if (subRL)subRL-_parent parent;if (pParent nullptr){_root subR;subR-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}parent-_bf subR-_bf 0;
}
2.3.6 左右双旋
具象图 抽象图 2.3.7左右双旋代码实现
//左右双旋
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;parent-_bf 1;subLR-_bf 0;}else if(bf 1){subL-_bf -1;parent-_bf 0;subLR-_bf 0;}else if (bf 0){subL-_bf 0;parent-_bf 0;subLR-_bf 0;}else{assert(false);}
}
2.3.8 右左双旋 2.3.9 右左双旋代码实现
//右左双旋
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 1;parent-_bf 0;subRL-_bf 0;}else if (bf 1){subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf 0){subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else{assert(false);}
}
2.4 AVL树的查找
按⼆叉搜索树逻辑实现即可搜索效率为O(logN)
//查找
Node* find(const K key)
{Node* cur _root;while (cur){if (cur-_kv.first key){return cur;}else if (key cur-_kv.first){cur cur-_left;}else{cur cur-_right;}}return nullptr;
}
2.5 AVL树平衡检测
我们实现的AVL树是否合格我们通过检查左右⼦树⾼度差的的程序进⾏反向验证同时检查⼀下结点 的平衡因⼦更新是否出现了问题。
//中序遍历
Node* _Inorder(Node* root)
{if (root nullptr)return nullptr;_Inorder(root-_left);cout { root-_kv.first , root-_kv.second } endl;_Inorder(root-_right);return 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;
}
//计算节点的数量
int _Size(Node* root)
{if (root nullptr)return 0;int CountL _Size(root-_left);int CountR _Size(root-_right);return CountL CountR 1;
}
//判断是否是AVL树
bool _IsBalanceTree(Node* root)
{//空树也是AVL树if (root nullptr)return true;int LHeight _Height(root-_left);int RHeight _Height(root-_right);int ret RHeight - LHeight;if (abs(ret) 2){cout root-_kv.first 高度差异常 endl 高度差为 ret endl;return false;}if (ret ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);
}
#includeAVLTree.h
#includevectorvoid TestRotate()
{AVLTreeint, int t;// 常规的测试⽤例 //int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例 int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.insert({ e,e });}t.Inorder();cout t.IsBalanceTree() endl;
}
void TestTreeBalance()
{const int N 1000;srand((unsigned int)time(nullptr));AVLTreeint, int t;vectorint v;for (int i 0; i N; i){v.push_back(rand() i);}for (auto e : v){t.insert({ e,e });}cout t.Height() endl;;cout t.Size() endl;cout t.IsBalanceTree() endl;
}int main()
{//TestRotate();TestTreeBalance();return 0;
} 3. 源码
#pragma once
#includeassert.h
#includeiostream
using namespace std;templateclass K,class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNode* _parent;AVLTreeNode* _right;AVLTreeNode* _left;int _bf;//平衡因子AVLTreeNode(const pairK,V kv):_kv(kv), _parent(nullptr), _right(nullptr),_left(nullptr),_bf(0){}
};templateclass K, class V
class AVLTree
{
public:typedef AVLTreeNodeK,V Node;//插入bool insert(const pairK, V kv){//如果树为空直接在根插入if (_root nullptr){_root new Node(kv);return true;}//树不为空先按照搜索树规则找到插入位置Node* parent nullptr;Node* cur _root;while (cur){//插入的key小就往左走if (kv.first cur-_kv.first){parent cur;cur cur-_left;}//大就往右走else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else//不支持键值冗余{return false;}}//找到在parent插入的位置了cur new Node(kv);if (kv.first parent-_kv.first)parent-_left cur;elseparent-_right cur;//不要忘记链接新增节点的parentcur-_parent parent;//开始更新平衡因子while (parent){if (parent-_left cur)parent-_bf--;elseparent-_bf;//_bf从1或-1到0,不会影响祖先节点if (parent-_bf 0){break;}//_bf从0到1或-1会影响祖先节点继续向上更新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 parent-_left-_bf -1){RotateR(parent);}//纯粹右边高进行左单旋else if (parent-_bf 2 parent-_right-_bf 1){RotateL(parent);}//不纯粹左边高进行左右双旋else if (parent-_bf -2 parent-_left-_bf 1){RotateLR(parent);}//不纯粹右边高进行右左双旋else if (parent-_bf 2 parent-_right-_bf -1){RotateRL(parent);}break;//旋转完后该节点的平衡因子为0无需向上更新}else//非预想平衡因子直接断死{assert(false);}}return true;}//查找Node* find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){return cur;}else if (key cur-_kv.first){cur cur-_left;}else{cur cur-_right;}}return nullptr;}//中序遍历void Inorder(){_Inorder(_root);}//计算树的高度int Height(){return _Height(_root);}//计算树的节点个数int Size(){return _Size(_root);}//判断是否是AVL树bool IsBalanceTree(){return _IsBalanceTree(_root);}private://右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* pParent parent-_parent;parent-_left subLR;if(subLR)//如果不为空subLR-_parent parent;subL-_right parent;parent-_parent subL;if (pParent nullptr){_root subL;subL-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}parent-_bf subL-_bf 0;}//左单旋void RotateL(Node* parent){Node* pParent parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;subR-_left parent;parent-_parent subR;parent-_right subRL;if (subRL)subRL-_parent parent;if (pParent nullptr){_root subR;subR-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}parent-_bf subR-_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;parent-_bf 1;subLR-_bf 0;}else if(bf 1){subL-_bf -1;parent-_bf 0;subLR-_bf 0;}else if (bf 0){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){subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 1){subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf 0){subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else{assert(false);}}//中序遍历Node* _Inorder(Node* root){if (root nullptr)return nullptr;_Inorder(root-_left);cout { root-_kv.first , root-_kv.second } endl;_Inorder(root-_right);return 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;}//计算节点的数量int _Size(Node* root){if (root nullptr)return 0;int CountL _Size(root-_left);int CountR _Size(root-_right);return CountL CountR 1;}//判断是否是AVL树bool _IsBalanceTree(Node* root){//空树也是AVL树if (root nullptr)return true;int LHeight _Height(root-_left);int RHeight _Height(root-_right);int ret RHeight - LHeight;if (abs(ret) 2){cout root-_kv.first 高度差异常 endl 高度差为 ret endl;return false;}if (ret ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}private:Node* _rootnullptr;
};
4、完结散花
好了这期的分享到这里就结束了~
如果这篇博客对你有帮助的话可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话可以点点关注避免找不到我了呢~
我们下期不见不散~~
