网站制作方案策划简历,东城做企业网站多少钱,服务器怎么运行网站,电影网站建设方案ppt 作者简介#xff1a;დ旧言~#xff0c;目前大二#xff0c;现在学习Java#xff0c;c#xff0c;c#xff0c;Python等 座右铭#xff1a;松树千年终是朽#xff0c;槿花一日自为荣。 目标#xff1a;能直接手撕AVL树。 毒鸡汤#xff1a;放弃自… 作者简介დ旧言~目前大二现在学习JavaccPython等 座右铭松树千年终是朽槿花一日自为荣。 目标能直接手撕AVL树。 毒鸡汤放弃自己相信别人这就是失败的原因。 望小伙伴们点赞收藏✨加关注哟 前言
相信大家肯定听过在C大名鼎鼎的两颗树这两颗树分别是AVL树和红黑树学过的小伙伴听到都是瑟瑟发抖像一些大厂中可能会考手撕AVL树或红黑树。学习这两棵树确实难度很大正所谓难度越大动力就越大那本篇我们学习这两棵树的一颗树--AVL树。
⭐主体
学习AVL树咱们按照下面的图解 AVL树的概念
在计算机科学中AVL树是最早被发明的自平衡二叉查找树。在AVL树中任一节点对应的两棵子树的最大高度差为1因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。
AVL树的定义 一棵空的树是AVL树如果T是一棵非空的二叉树T(L)和T(R)分别是其左子树高和右子树高那么当T满足以下条件时T是一棵AVL树|h(L)-h(R)|1其中h(L)和h(R)分别是T(L)和T(R)的高简称平衡因子 AVL树的状态 AVL树的特性 一棵n个元素的AVL树其高度是O(logn)对于每一个nn0都存在一棵AVL树对一棵n元素的AVL搜索树在O(高度)O(logn)的时间内可以完成查找将一个新元素插入一棵n元素的AVL搜索树中可以得到一棵n1个元素的AVL树而且插入用时为O(logn)一个元素从一棵n元素的AVL搜索树中删除可以得到一棵n-1个元素的AVL树而且删除用时为O(logn) AVL树的结点 按照 KV 模型来构造 AVL 树需要把结点定义为 三叉链结构左、右、父。构造函数由于新构造结点的左右子树均为空树所以将新构造结点的平衡因子初始设置为 0 。 代码示例
// 创建AVL树的结点
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left; // 左子树AVLTreeNodeK, V* _right; // 右子树AVLTreeNodeK, V* _parent;// 父亲结点pairK, V _kv; // 存储的键值对int _bf; // 平衡因子右子树高度 - 左子树高度// 构造函数AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};
AVL树的插入
其实AVL树插入操作本质上比二叉搜索树的插入操作多了一个平衡操作
按照二叉搜索树的方式找到待插入的位置然后将新结点插入到该位置。调整节点的平衡因子如果出现不平衡则需要进行旋转。 当 AVL 树插入一个新结点以后需要更新插入结点的祖先的平衡因子因为新结点也就是叶子结点的平衡因子为 0但是它影响的是它的父亲它父亲的父亲…所以要更新到祖先结点。 上面的图就需要改变父亲爷爷的平衡因子我们知道树的状态有很多无法穷举但是我们也有规律可寻这个规律就在于我们的平衡因子所以我总结如下
如果新增结点插入在 parent 的右边只需要给 parent 的平衡因子 1 即可如果新增结点插入在 parent 的左边只需要给 parent 的平衡因子 -1 即可
当 parent 的平衡因子更新完以后可能出现三种情况0正负 1正负 2。
1parent 的平衡因子为 0 如果parent的平衡因子是0说明之前parent的平衡因子是1或-1说明之前parent一边高、一边低这次插入之后填入矮的那边parent所在的子树高度不变不需要继续往上更新。如图 2如果 parent 的平衡因子为正负 1 如果parent的平衡因子是1或者-1说明之前parent的平衡因子是0两边一样高插入之后一边更高parent所在的子树高度发生变化继续往上更新。 ①parent为1 ②parent为 -1 3如果 parent 的平衡因子为正负 2 平衡因子是2或-2说明之前parent的平衡因子是1或-1现在插入严重不平衡违反规则需要进行旋转处理 如果parent的平衡因子是2cur的平衡因子是1时说明右边的右边比较高我们需要进行左单旋如果parent的平衡因子是-2cur的平衡因子是-1时说明左边的左边比较高我们需要进行右单旋如果parent的平衡因子是-2cur的平衡因子是1时我们需要进行左右双旋如果parent的平衡因子是2cur的平衡因子是-1时我们需要进行右左双旋 这里我们就举一个栗子 代码实现
public:// 插入函数bool Insert(const pairK, V kv){// 如果AVL树是空树把插入节点直接作为根节点if (_root nullptr){_root new Node(kv);_root-_bf 0;return true;}// 1.按照二叉搜索树的规则插入Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first) // 待插入节点的key值大于当前节点的key值{// 往右子树走parent cur;cur cur-_right;}else if (cur-_kv.first kv.first) // 待插入节点的key值小于当前节点的key值{// 往左子树走parent cur; cur cur-_left;}else // 待插入节点的key值等于当前节点的key值{return false; // 插入失败返回false}}// 2.当循环结束说明cur找到了空的位置那么就插入cur new Node(kv); // 构造一个新节点if (parent-_kv.first kv.first) // 如果新节点的key值大于当前parent节点的key值{// 就把新节点链接到parent的右边parent-_right cur;}else // 如果新节点的key值小于当前parent节点的key值{// 就把新节点链接到parent的左边parent-_left cur;}cur-_parent parent; // 别忘了把新节点里面的_parent指向parent(因为我们定义的是一个三叉链)// 3.更新平衡因子,如果出现不平衡,则需要进行旋转while (parent) // 最远要更新到根节点去{if (cur parent-_right) // 如果cur插在parent的右边说明parent的右子树增高{parent-_bf; // 那么parent的平衡因子要}else // 如果cur插在parent的左边说明parent的左子树增高{parent-_bf--; // 那么parent的平衡因子要--}// 判断是否更新结束或者是否需要进行旋转if (parent-_bf 0) // 如果parent的bf等于0说明左右子树高度一致就更新结束(原因是新插入的节点把parent左右子树中矮的那一边给填补了{// 高度不变,更新结束break;}else if (parent-_bf 1 || parent-_bf -1) // 继续往上更新平衡因子(插入节点导致某一边变高了说明parent所在的子树高度改变了){// 子树的高度变了就要继续往上更新祖先cur cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2) // 说明插入节点导致本来高的一边又变高了子树不平衡了那么此时需要做旋转处理{// 旋转的四种处理方式// 1.左单旋// 2.右单旋// 3.左右双旋// 4.右左双旋// 旋转完成跳出break;}else{// 如果程序走到了这里说明在插入节点之前AVL树就存在不平衡的子树也就是存在平衡因子 2的节点// 所以这里加一个断言进行处理assert(false);}}// 插入成功返回truereturn true;}AVL树的旋转
在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同采用不同的旋转方法。 AVL树的旋转分为四种 左单旋LL右单旋RR左右双旋LR右左双旋RL 旋转规则 让这颗子树左右高度差不超过1旋转过程中继续保持它是搜索树更新调整孩子节点的平衡因子让这颗子树的高度根插入前保持一致 左单旋
左单旋的步骤如下
先让 subR 的左子树subRL作为 parent 的右子树。然后让 parent 作为 subR 的左子树。接下来让 subR 作为整个子树的根。最后更新平衡因子
我们就以下面的抽象图来看看左单旋如何实现 代码示例
// 左单旋右边高需要左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* ppNode parent-_parent; // 先保存parent的parent// 1.建立parent和subRL之间的关系parent-_right subRL;if (subRL) // 如果subRL节点不为空那么要更新它的parent{subRL-_parent parent;}// 2.建立subR和parent之间的关系subR-_left parent;parent-_parent subR;// 3.建立ppNode和subR之间的关系分情况讨论parent是整颗树的根还是局部子树if (parent _root) // 当parent是根节点时{_root subR; // subR就变成了新的根节点_root-_parent nullptr; // 根节点的的parent为空}else // 当parent是整个树的局部子树时{if (parent ppNode-_left) // 如果parent在ppNode的左边{ppNode-_left subR; // 那么subR就是parent的左子树}else // 如果parent在ppNode的右边{ppNode-_right subR; // 那么subR就是parent的右子树}subR-_parent ppNode; // subR的parent还要指向ppNode}// 更新平衡因子parent-_bf 0;subR-_bf 0;}右单旋
右单旋的步骤如下
先让 subL 的右子树subLR作为 parent 的左子树。然后让 parent 作为 subL 的右子树。接下来让 subL 作为整个子树的根。最后更新平衡因子。
我们就以下面的抽象图来看看右单旋如何实现 代码示例
// 右单旋左边高就右单旋void RotateR(Node* parent){Node* subL parent-_left; Node* subLR subL-_right;Node* ppNode parent-_parent;// 1.建立parent和subLR之间的关系parent-_left subLR;if (subLR) // 如果subLR节点不为空那么要更新它的parent{subLR-_parent parent;}// 2.建立subL和parent之间的关系subL-_right parent;parent-_parent subL;// 3.建立ppNode和subL之间的关系分情况讨论parent是整颗树的根还是局部子树if (parent _root) // 当parent是根节点时{_root subL; // subL就变成了新的根节点_root-_parent nullptr; // 根节点的的parent为空}else // 当parent是整个树的局部子树时{if (parent ppNode-_left) // 如果parent在ppNode的左边{ppNode-_left subL; // 那么subL就是parent的左子树}else // 如果parent在ppNode的右边{ppNode-_right subL; // 那么subL就是parent的右子树}subL-_parent ppNode; // subR的parent还要指向ppNode}// 更新平衡因子parent-_bf 0;subL-_bf 0;}左右单旋
左右单旋的步骤如下
先以 subL 为旋转点进行左单旋。然后以 parent 为旋转点进行右单旋。最后再更新平衡因子。
我们就以下面的抽象图来看看左右单旋如何实现 再次分类讨论 1当 subLR 原始平衡因子是 -1 时左右双旋后 parent、subL、subLR 的平衡因子分别更新为 1、0、0 2当 subLR 原始平衡因子是 1 时左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、-1、0 3当 subLR 原始平衡因子是 0 时说明 subLR 为新增结点左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、0、0 代码示例 // 左右双旋先左单旋再右单旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;// 1.先以subL为旋转点进行左单旋RotateL(parent-_left);// 2.再以parent为旋转点进行右单旋RotateR(parent);// 3.更新平衡因子if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else{// 如果走到了这里说明subLR的平衡因子在旋转前就有问题assert(false);}}右左单旋
右左单旋的步骤如下
先以 subR 为旋转点进行右单旋。然后以 parent 为旋转点进行左单旋。最后再更新平衡因子。
我们就以下面的抽象图来看看右左单旋如何实现 再次分类讨论 1当 subRL 原始平衡因子是 1 时左右双旋后 parent、subR、subRL 的平衡因子分别更新为 -1、0、0 2当 subRL 原始平衡因子是 -1 时左右双旋后 parent、subR、subRL 的平衡因子分别更新为 0、1、0 3当 subRL 原始平衡因子是 0 时说明 subRL为新增结点左右双旋后 parent、subR、subRL 的平衡因子分别更新为0、0、0 代码示例
// 右左双旋先右单旋再左单旋void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;// 1.先以subR为旋转点进行右单旋RotateR(parent-_right);// 2.再以parent为旋转点进行左单旋RotateL(parent);// 3.更新平衡因子if (bf 0){subRL-_bf 0;parent-_bf 0;subR-_bf 0;}else if (bf 1){subRL-_bf 0;parent-_bf -1;subR-_bf 0;}else if (bf -1){subRL-_bf 0;parent-_bf 0;subR-_bf 1;}else{// 如果走到了这里说明subRL的平衡因子在旋转前就有问题assert(false);}}AVL树的删除
这里的删除过于复杂我这里就直接上代码了如果对这里感兴趣的小伙伴们可以查阅资料。
// 删除函数bool Erase(const K key){//用于遍历二叉树Node* parent nullptr;Node* cur _root;//用于标记实际的删除结点及其父结点Node* delParentPos nullptr;Node* delPos nullptr;while (cur){if (key cur-_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (key cur-_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //找到了待删除结点{if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root)_root-_parent nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点无需进行平衡因子的更新操作}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //删除结点有祖先结点需更新平衡因子}else if (cur-_right nullptr) //待删除结点的右子树为空{if (cur _root) //待删除结点是根结点{_root _root-_left; //让根结点的左子树作为新的根结点if (_root)_root-_parent nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点无需进行平衡因子的更新操作}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //删除结点有祖先结点需更新平衡因子}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_kv.first minRight-_kv.first; //将待删除结点的key改为minRight的keycur-_kv.second minRight-_kv.second; //将待删除结点的value改为minRight的valuedelParentPos minParent; //标记实际删除结点的父结点delPos minRight; //标记实际删除的结点break; //删除结点有祖先结点需更新平衡因子}}}if (delParentPos nullptr) //delParentPos没有被修改过说明没有找到待删除结点{return false;}//记录待删除结点及其父结点用于后续实际删除Node* del delPos;Node* delP delParentPos;//更新平衡因子while (delPos ! _root) //最坏一路更新到根结点{if (delPos delParentPos-_left) //delParentPos的左子树高度降低{delParentPos-_bf; //delParentPos的平衡因子}else if (delPos delParentPos-_right) //delParentPos的右子树高度降低{delParentPos-_bf--; //delParentPos的平衡因子--}//判断是否更新结束或需要进行旋转if (delParentPos-_bf 0)//需要继续往上更新平衡因子{//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;}else if (delParentPos-_bf -1 || delParentPos-_bf 1) //更新结束{break; //delParent树的高度没有发生变化不会影响其父结点及以上结点的平衡因子}else if (delParentPos-_bf -2 || delParentPos-_bf 2) //需要进行旋转此时delParentPos树已经不平衡了{if (delParentPos-_bf -2){if (delParentPos-_left-_bf -1){Node* tmp delParentPos-_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos tmp; //更新根结点}else if (delParentPos-_left-_bf 1){Node* tmp delParentPos-_left-_right; //记录delParentPos左右旋转后新的根结点RotateLR(delParentPos); //左右双旋delParentPos tmp; //更新根结点}else //delParentPos-_left-_bf 0{Node* tmp delParentPos-_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf 1;delParentPos-_right-_bf -1;break; //更正}}else //delParentPos-_bf 2{if (delParentPos-_right-_bf -1){Node* tmp delParentPos-_right-_left; //记录delParentPos右左旋转后新的根结点RotateRL(delParentPos); //右左双旋delParentPos tmp; //更新根结点}else if (delParentPos-_right-_bf 1){Node* tmp delParentPos-_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos tmp; //更新根结点}else //delParentPos-_right-_bf 0{Node* tmp delParentPos-_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf -1;delParentPos-_left-_bf 1;break; //更正}}//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;//break; //error}else{assert(false); //在删除前树的平衡因子就有问题}}//进行实际删除if (del-_left nullptr) //实际删除结点的左子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_right;if (del-_right)del-_right-_parent parent;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent parent;}}else //实际删除结点的右子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent parent;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent parent;}}delete del; //实际删除结点return true;}AVL树的遍历
中序是递归遍历左 根 右由于涉及到传参所以需要写一个子函数。
代码实现 // 中序遍历void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left); // 走左cout root-_kv.first [ root-_bf ] endl; // 遍历根_InOrder(root-_right); // 走右}void InOrder(){_InOrder(_root);}
AVL树的查找
查找步骤
若 key 值小于当前结点的值则应该在该结点的左子树当中进行查找。若 key 值大于当前结点的值则应该在该结点的右子树当中进行查找。若 key 值等于当前结点的值则查找成功返回对应结点。
代码实现 // 查找元素Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return NULL;}
AVL树的高度
由于涉及到传参所以需要写一个子函数。
代码实现 // 计算树的高度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 Height(){return _Height(_root);}
AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分为下面两步
1验证其为二叉搜索树
如果中序遍历可得到一个有序的序列就说明为二叉搜索树
void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}
2验证其为平衡树
每个节点子树高度差的绝对值不超过 1注意节点中如果没有平衡因子节点的平衡因子是否计算正确
AVL树的高度
//求高度
int Height(Node* root){if (root nullptr)return 0;int lh Height(root-_left);int rh Height(root-_right);return lh rh ? lh 1 : rh 1;}
//判断平衡
bool IsBalance(Node* root){if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2 IsBalance(root-_left) IsBalance(root-_right);}AVL树优缺点
优点
平衡二叉树的优点不言而喻相对于二叉排序树BST而言平衡二叉树避免了二叉排序树可能出现的最极端情况斜树问题其平均查找的时间复杂度为 O ( l o g N ) O(logN)O(logN)
缺点
平衡二叉树为了保持平衡动态进行插入和删除操作的代价也会增加。因此出现了后来的红黑树
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过 1这样可以保证查询时高效的时间复杂度即O ( l o g N ) O(logN)O(logN)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑AVL树但一个结构经常修改就不太适合。
整体代码
#include iostream
#include assert.h
#includevector
#include time.h
using namespace std;// 创建AVL树的结点
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left; // 左子树AVLTreeNodeK, V* _right; // 右子树AVLTreeNodeK, V* _parent;// 父亲结点pairK, V _kv; // 存储的键值对int _bf; // 平衡因子右子树高度 - 左子树高度// 构造函数AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};templateclass 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) // 插入的元素大于cur就走右子树{parent cur;cur cur-_right;}else if (cur-_kv.first kv.first) // 插入的元素小于cur就走左子树{parent cur;cur cur-_left;}elsereturn false;}cur new Node(kv);// 创建一个结点// 链接if (parent-_kv.first kv.first)parent-_right cur;elseparent-_left cur;cur-_parent parent;// 循环判断插入结点的平衡因子和AVL树是否正确while (parent){// 判断插入的节点在父亲的右边还是左边if (cur parent-_left) // 在左边就父亲平衡因子减一parent-_bf--;else // 在右边就父亲平衡因子加一parent-_bf;if (parent-_bf 0) // 如果父亲的平衡因子为 0 该树就是健康的不用改变break;else if (parent-_bf 1 || parent-_bf -1) // 这时需要向上调整每个节点的平衡因子{cur 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) // 左右双旋{RotateLR(parent);}else // 右左双旋 {RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);}}}// 左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}parent-_bf 0;subR-_bf 0;}// 右单旋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;}subL-_bf 0;parent-_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){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}// 右左双旋void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);subRL-_bf 0;if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){parent-_bf 0;subR-_bf 1;}else{parent-_bf 0;subR-_bf 0;}}// 中序遍历void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left); // 走左cout root-_kv.first [ root-_bf ] endl; // 遍历根_InOrder(root-_right); // 走右}void InOrder(){_InOrder(_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 Height(){return _Height(_root);}// 判断是否平衡bool _IsBalance(Node* root, int height){if (root nullptr){height 0;return true;}int leftHeight 0, rightHeight 0;if (!_IsBalance(root-_left, leftHeight)|| !_IsBalance(root-_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) 2){cout root-_kv.first 不平衡 endl;return false;}if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}bool IsBalance(){int height 0;return _IsBalance(_root, height);}// 计算树的结点个数size_t _Size(Node* root){if (root NULL)return 0;return _Size(root-_left) _Size(root-_right) 1;}size_t Size(){return _Size(_root);}// 查找元素Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return NULL;}// 删除函数bool Erase(const K key){//用于遍历二叉树Node* parent nullptr;Node* cur _root;//用于标记实际的删除结点及其父结点Node* delParentPos nullptr;Node* delPos nullptr;while (cur){if (key cur-_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (key cur-_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //找到了待删除结点{if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root)_root-_parent nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点无需进行平衡因子的更新操作}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //删除结点有祖先结点需更新平衡因子}else if (cur-_right nullptr) //待删除结点的右子树为空{if (cur _root) //待删除结点是根结点{_root _root-_left; //让根结点的左子树作为新的根结点if (_root)_root-_parent nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点无需进行平衡因子的更新操作}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //删除结点有祖先结点需更新平衡因子}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_kv.first minRight-_kv.first; //将待删除结点的key改为minRight的keycur-_kv.second minRight-_kv.second; //将待删除结点的value改为minRight的valuedelParentPos minParent; //标记实际删除结点的父结点delPos minRight; //标记实际删除的结点break; //删除结点有祖先结点需更新平衡因子}}}if (delParentPos nullptr) //delParentPos没有被修改过说明没有找到待删除结点{return false;}//记录待删除结点及其父结点用于后续实际删除Node* del delPos;Node* delP delParentPos;//更新平衡因子while (delPos ! _root) //最坏一路更新到根结点{if (delPos delParentPos-_left) //delParentPos的左子树高度降低{delParentPos-_bf; //delParentPos的平衡因子}else if (delPos delParentPos-_right) //delParentPos的右子树高度降低{delParentPos-_bf--; //delParentPos的平衡因子--}//判断是否更新结束或需要进行旋转if (delParentPos-_bf 0)//需要继续往上更新平衡因子{//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;}else if (delParentPos-_bf -1 || delParentPos-_bf 1) //更新结束{break; //delParent树的高度没有发生变化不会影响其父结点及以上结点的平衡因子}else if (delParentPos-_bf -2 || delParentPos-_bf 2) //需要进行旋转此时delParentPos树已经不平衡了{if (delParentPos-_bf -2){if (delParentPos-_left-_bf -1){Node* tmp delParentPos-_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos tmp; //更新根结点}else if (delParentPos-_left-_bf 1){Node* tmp delParentPos-_left-_right; //记录delParentPos左右旋转后新的根结点RotateLR(delParentPos); //左右双旋delParentPos tmp; //更新根结点}else //delParentPos-_left-_bf 0{Node* tmp delParentPos-_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf 1;delParentPos-_right-_bf -1;break; //更正}}else //delParentPos-_bf 2{if (delParentPos-_right-_bf -1){Node* tmp delParentPos-_right-_left; //记录delParentPos右左旋转后新的根结点RotateRL(delParentPos); //右左双旋delParentPos tmp; //更新根结点}else if (delParentPos-_right-_bf 1){Node* tmp delParentPos-_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos tmp; //更新根结点}else //delParentPos-_right-_bf 0{Node* tmp delParentPos-_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf -1;delParentPos-_left-_bf 1;break; //更正}}//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;//break; //error}else{assert(false); //在删除前树的平衡因子就有问题}}//进行实际删除if (del-_left nullptr) //实际删除结点的左子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_right;if (del-_right)del-_right-_parent parent;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent parent;}}else //实际删除结点的右子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent parent;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent parent;}}delete del; //实际删除结点return true;}private:Node* _root nullptr;
};void TestAVLTree1()
{//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTreeint, int t;for (auto e : a){if (e 14){int x 0;}t.Insert(make_pair(e, e));cout e - t.IsBalance() endl;}t.InOrder();cout t.IsBalance() endl;
}void TestAVLTree2()
{const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);//cout v.back() endl;}size_t begin2 clock();AVLTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));//cout Insert: e - t.IsBalance() endl;}size_t end2 clock();cout Insert: end2 - begin2 endl;cout t.IsBalance() endl;cout Height: t.Height() endl;cout Size: t.Size() endl;size_t begin1 clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值for (size_t i 0; i N; i){t.Find((rand() i));}size_t end1 clock();cout Find: end1 - begin1 endl;
}结束语 今天内容就到这里啦时间过得很快大家沉下心来好好学习会有一定的收获的大家多多坚持嘻嘻成功路上注定孤独因为坚持的人不多。那请大家举起自己的小手给博主一键三连有你们的支持是我最大的动力回见。
