C++进阶：AVL树

◆博主名称少司府欢迎来到少司府的博客☆*: .. o(≧▽≦)o ..:*☆⭐数据结构系列个人专栏初阶数据结构_少司府的博客-CSDN博客⭐C系列个人专栏C初阶、C进阶⭐水滴石穿非一日功不唐捐终可期目录1.AVL树的概念1.1 AVL树1.2 平衡因子2.AVL树的实现2.1 AVL树的结构2.2 AVL树的插入2.2.1 插入的过程2.2.2 平衡因子的更新2.2.3 代码实现2.3 旋转2.3.1 旋转的规则2.3.2 右单旋2.3.3 左单旋2.3.4 左右双旋2.3.5 右左双旋2.4 AVL树查找1.AVL树的概念1.1 AVL树AVL树是最先发明的自平衡⼆叉搜索树AVL是⼀颗空树或者具备下列性质的⼆叉搜索树它的左右子树都是AVL树且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树 通过控制⾼度差去控制平衡。1.2 平衡因子AVL树实现这⾥我们引⼊⼀个平衡因子(balance factor)的概念每个结点都有⼀个平衡因⼦任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度也就是说任何结点的平衡因⼦等于0/1/-1AVL树并不是必须要平衡因⼦但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡就像⼀个⻛向标⼀样。2.AVL树的实现2.1 AVL树的结构templateclass K, class V struct AVLTreeNode { // 需要parent指针后续更新平衡因⼦可以看到 pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; // balance factor AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) { } }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: //... private: Node* _root nullptr; };2.2 AVL树的插入2.2.1 插入的过程1、插入⼀个值按⼆叉搜索树规则进⾏插⼊。2、新增结点以后只会影响祖先结点的⾼度也就是可能会影响部分祖先结点的平衡因⼦所以更新从新增结点-根结点路径上的平衡因⼦实际中最坏情况下要更新到根。3、更新平衡因⼦过程中没有出现问题则插⼊结束。4、更新平衡因⼦过程中出现不平衡对不平衡⼦树旋转旋转后调平衡的同时本质降低了⼦树的⾼度不会再影响上⼀层所以插⼊结束。2.2.2 平衡因子的更新更新规则1、平衡因子右子树⾼度-左子树⾼度2、只有⼦树⾼度变化才会影响当前结点平衡因⼦。3、插⼊结点会增加⾼度所以新增结点在parent的右⼦树parent的平衡因⼦新增结点在parent的左⼦树parent平衡因⼦--4、parent所在⼦树的⾼度是否变化决定了是否会继续往上更新停止更新条件1、更新后parent的平衡因⼦等于0新增的结点插⼊在低的那边插⼊后parent所在的⼦树⾼度不变不会影响parent的⽗亲结点的平衡因⼦更新结束。2、更新后parent的平衡因⼦等于1或-1说明更新前为0高度改变因此要向上更新3、更新后parent的平衡因⼦等于2或-2更新前是1或-1AVL树结构发生变化需要旋转处理2.2.3 代码实现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 { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 更新平衡因⼦ while (parent) { // 更新平衡因⼦ if (cur parent-_left) parent-_bf--; else 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) { // 不平衡了旋转处理 break; } else { // 插入之前平衡树就出问题了 assert(false); } } return true; }2.3 旋转2.3.1 旋转的规则1、保持搜索树的规则2、让旋转的树从不满⾜变平衡其次降低旋转树的⾼度2.3.2 右单旋1、本图展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景实际右单旋形态有很多种。2、旋转核⼼步骤因为5 b子树的值 10将b变成10的左⼦树10变成5的右⼦树5变成这棵树新 的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* pParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; _root-_parent nullptr; } else { if (pParent-_left parent) pParent-_left subL; else pParent-_right subL; subL-_parent pParent; } subL-_bf 0; parent-_bf 0; }2.3.3 左单旋本图展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树是⼀种概括抽象表⽰他代表了所有右单旋的场景实际右单旋形态有很多种具体跟上⾯左旋类似。void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parentParent nullptr) { _root subR; subR-_parent nullptr; } else { if (parent parentParent-_left) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } parent-_bf subR-_bf 0; }2.3.4 左右双旋1、通过下图可以看到左边⾼时如果插⼊位置不是在a⼦树⽽是插⼊在b⼦树b⼦树⾼度从h变 成h1引发旋转右单旋⽆法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边⾼但是插⼊在b⼦树中10为跟的⼦树不再是单纯的左边⾼对于10是左边⾼但是对于5是右边⾼需要⽤两次旋转才能解决以5为旋转点进⾏⼀个左单旋以10为旋转点进⾏⼀个右单旋这棵树 这棵树就平衡了。2、上图分别为左右双旋中h0和h1具体场景分析下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树因为 我们要对b的⽗亲5为旋转点进⾏左单旋左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置 不同平衡因⼦更新的细节也不同通过观察8的平衡因⼦不同这⾥我们要分三个场景讨论。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; subLR-_bf 0; parent-_bf 0; } else if (bf -1) { subL-_bf 0; subLR-_bf 0; parent-_bf 1; } else if (bf 1) { subL-_bf -1; subLR-_bf 0; parent-_bf 0; } else { assert(false); } }2.3.5 右左双旋跟左右双旋类似下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析另外我们需要把b⼦树的 细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树因为我们要对b的⽗亲15为旋转点进⾏右单 旋右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同平衡因⼦更新的细节也不同通 过观察12的平衡因⼦不同这⾥我们要分三个场景讨论。void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; RotateR(parent-_right); RotateL(parent); if (bf 0) { subR-_bf 0; subRL-_bf 0; parent-_bf 0; } else if (bf 1) { subR-_bf 0; subRL-_bf 0; parent-_bf -1; } else if (bf -1) { subR-_bf 1; subRL-_bf 0; parent-_bf 0; } else { assert(false); } }2.4 AVL树查找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 nullptr; }本期的分享就到这里如果觉得博主的文章比较对胃口的话可以点一个小小的关注~您的三连是我持续更新的动力~