织梦后台点击网站主页,湖南常德市简介,厦门做网站维护的公司,站点和网站的区别【C模拟实现】手撕AVL树 目录 【C模拟实现】手撕AVL树AVL树的介绍#xff08;百度百科#xff09;AVL树insert函数的实现代码验证是否为AVL树AVL树模拟实现的要点易忘点AVL树的旋转思路 作者#xff1a;爱写代码的刚子 时间#xff1a;2023.9.10 前言#xff1a;本篇博客将…【C模拟实现】手撕AVL树 目录 【C模拟实现】手撕AVL树AVL树的介绍百度百科AVL树insert函数的实现代码验证是否为AVL树AVL树模拟实现的要点易忘点AVL树的旋转思路 作者爱写代码的刚子 时间2023.9.10 前言本篇博客将会介绍AVL树的模拟实现(模拟AVL树的插入)以及如何去验证是否为AVL树 AVL树的介绍百度百科
AVL树本质上还是一棵二叉搜索树它的特点是 本身首先是一棵二叉搜索树。 带有平衡条件每个结点的左右子树的高度之差的绝对值平衡因子最多为1。
也就是说AVL树本质上是带了平衡功能的二叉查找树二叉排序树二叉搜索树。
AVL树insert函数的实现代码
templateclass K,class V
class AVLTreeNode
{
public: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
{typedef AVLTreeNodeK,V Node;
public:AVLTree():_root(nullptr){}bool insert(const pairK,V kv){if(_rootnullptr){_rootnew Node(kv);return true;}else{Node* cur_root;Node* parentnullptr;//设计parent指针是必要的while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_left;}else if(cur-_kv.firstkv.first){parentcur;curcur-_right;}else{return false;}}curnew Node(kv);//判断新加入的节点是父节点的左子树还是右子树if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;while(parent){//及时调整父节点的平衡因子if(parent-_leftcur){--parent-_bf;}else{parent-_bf;}if(parent-_bf0)//当父节点的平衡因子为0时停止调整{break;}else if(parent-_bf-1||parent-_bf1){curparent;parentparent-_parent;}else if(parent-_bf2||parent-_bf-2)//处理异常情况{//出现问题的情况if(parent-_bf-2cur-_bf-1){_RotateR(parent);//右单旋}else if(parent-_bf2cur-_bf1){_RotateL(parent);//左单旋}else if(parent-_bf-2cur-_bf1){ _RotateLR(parent);//左右双旋}else if(parent-_bf2cur-_bf-1){_RotateRL(parent);//右左双旋}else{assert(false);}break;}else{assert(false);}}}return true;} void _RotateR(Node* parent)//右单旋的实现{Node*curparent-_left;Node*curRightcur-_right;Node*ppnodeparent-_parent;cur-_rightparent;parent-_leftcurRight;if(curRight)//curRight可能是nullptr{curRight-_parentparent;}parent-_parentcur;//处理ppnodeif(parent_root)//parent为头节点时需要单独处理{_rootcur;cur-_parentnullptr;}else{if(ppnode-_leftparent){ppnode-_leftcur;}else{ppnode-_rightcur;}cur-_parentppnode;}parent-_bfcur-_bf0;}void _RotateL(Node* parent){Node* curparent-_right;Node* curLeftcur-_left;Node* ppnodeparent-_parent;cur-_leftparent;parent-_rightcurLeft;if(curLeft){curLeft-_parentcur;}parent-_parentcur;if(parent_root){_rootcur;cur-_parentnullptr;}else{if(ppnode-_leftparent){ppnode-_leftcur;}else{ppnode-_rightcur;}cur-_parentppnode;}parent-_bfcur-_bf0;}void _RotateLR(Node* parent){Node* curparent-_left;Node* curRightcur-_right;int bfcurRight-_bf;_RotateL(cur);_RotateR(parent);//最好再处理一下平衡因子减少耦合度if(bf0)//单链情况下{parent-_bf0;cur-_bf0;curRight-_bf0;}else if(bf-1){parent-_bf1;curRight-_bf0;cur-_bf0;}else if(bf1){parent-_bf-1;curRight-_bf0;cur-_bf0;}else{assert(false);}}void _RotateRL(Node* parent){Node* curparent-_right;Node* curLeftcur-_left;int bfcurLeft-_bf;_RotateR(cur);_RotateL(parent);if(bf0){parent-_bf0;curLeft-_bf0;cur-_bf0;}else if(bf1){parent-_bf0;curLeft-_bf-1;cur-_bf0;}else if(bf-1){parent-_bf0;curLeft-_bf1;cur-_bf0;}else{assert(false);}}private:Node* _root;
};
验证是否为AVL树
int _Height(Node* root){if(rootnullptr){return 0;}int leftHeight_Height(root-_left);int rightHeight_Height(root-_right);return leftHeightrightHeight?leftHeight1:rightHeight1;}bool _Isbalance(){return _Isbalance(_root);}bool _Isbalance(Node* root){if(rootnullptr){return true;}int right_Height(root-_right);int left_Height(root-_left);if(root-_bf!right-left){cout平衡因子异常root-_bf right leftendl;return false;}return abs(right-left)2_Isbalance(root-_left)_Isbalance(root-_right);}根据AVL树的特性引入两个成员函数_Height函数用于计算二叉树的高度 以下为验证结果
AVL树模拟实现的要点
易忘点
一定要时刻注意_parent指针的修改尤其旋转函数中需要判断旋转后的二叉树的根节点是否还有父亲节点如果有需要在旋转前先保存之后再链接上。
AVL树的旋转思路
新增在左parent平衡因子减减新增在右parent平衡因子加加更新后parent平衡因子 0说明parent所在的子树的高度不变不会再影响祖先不用再继续沿着到eot的路径往上更新更新后parent平衡因子 1 0r -1说明parent所在的子树的高度变化会再影响祖先需要继续沿着到root的路径往上更新更新后更新后parent平衡因子 2 or -2说明parent所在的子树的高度变化且不平衡对parent所在子树进行旋转让他平衡更到根节点插入结束 由于AVL树画图较为麻烦作者先不画了可以看看其他大佬的博客一些需要注意的地方已经写在代码注释里了AVL树的删除之后有机会可以模拟实现一下。 AVL树的调试较为麻烦模拟实现可以提高自己的调试能力。
