AVL树的实现

AVL树

        avl其实并不算单独的树，它和map、set是密不可分的，逻辑上大体是相同的，不过它多了一个平衡因子的概念，也就是说，它是依靠平衡因子来决定自己是否失衡需要调整的。

我们可以看到它的结构和map、set并没有什么太大不同，不过多了一个bf的平衡因子和父节点。平衡因子的作用是为了决定自己是否失衡，而父节点则是决定了如果失衡，可以向上调整，类似于单链表进化成了双向链表。甚至于它的插入在不涉及旋转的部分都和前面的map/set一样。

还是老一套的插入，然后更改位置，只不过多了一个parent的修改。

旋转

单旋

这里才是AVL树的重头戏。我们插入之后，这棵树的平衡因子一定要更新，并且还不能只更新插入的那一个，得一直向上更新，来确保这棵树没有失衡。

到这一步都算是省事的插法，虽然略微失衡但是我们不需要去调整这棵树。

但是一旦有平衡因子更新到了2或者-2，就代表它失衡了，我们就得旋转来确保平衡。

我们先来了解旋转是怎么个原理的。

忽略我的垃圾画图技术，我们可以看出来这棵树虽然没有失衡，但是已经算亚健康了，所以假设我们在2的左边插入一个节点时，它就失衡了。

那么这就是完美的一边失衡，我们往右单旋就能解决问题，直接说太抽象了，看我画的图来了解怎么旋的。

首先把4给我们的根节点左边。

然后根节点变为3的右边，3成为新的根节点，这样就算旋转完了。

因为3在更新前就属于小于根节点的状态，并且它的右边大于3但是还是小于根节点5，所以它去替代3成为根节点的新左很合适。然后根节点再去当3的右也很合适。3就成为了新的根，这棵树就平衡了。并且我们可以发现旋转完之后高度恢复到了插入之前的状态，所以我们也不用向上调整，实在是方便。

但是代码就很麻烦，可以回忆一下双向链表的插入，需要改的地方有点多，这里就更多了。

//右单旋void RotateR(node* parent){//传入的当父节点//那么父的左我们称为subl//左的右称为sublrnode* subL = parent->_left;node* subLR = subL->_right;//然后就是第一步，把左的右也就是lr给parent的左当替代品parent->_left = subLR;//然后左的右变成parentsubL->_right = parent;//看着好像搞完了，但是实际上差远了，我们的parent指向还没改呢 乱套了//首先parent变了，那么我们还得先记录一下parent的parentnode* pparent = parent->_parent;//然后更新parent的parent为我们的subl parent->_parent = subL;//然后考虑一下lr可能本来就是空的情况会野指针 所以用if判断改parentif (subLR){subLR->_parent = parent;}//然后还得考虑parent可能是根的情况，那么subl就是新根了 也得改 并且subl的parent这种情况下就为空了if (_root == parent){_root = subL;subL->_parent = nullptr;}//不然parent就不是根else{//那我们还得分情况讨论，它是pparent左还是右 然后改过去if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;//最后根据旋转后的图所示，它旋转完之后的高度是降为0的 所以更新平衡因子parent->_bf = subL->_bf = 0;}}

我们可以看到说起来的操作好像简单，改改指向就好了，但是里面的弯弯绕绕是真多。

那有右单旋就有左单旋，它们的逻辑就是相反的。

//左单旋void RotateL(node* parent){node* subR = parent->_right;node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;node* pparent = parent->_parent;parent->_parent = subr;if (subRL){subRL->_parent = parent;}if (_root = parent){_root = subR;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;parent->_bf = subR->_bf = 0;}}

能写右就能写出左来。

双旋

到这都算是happy end，最恶心的是接下来的，它失衡，但是它不往一边失衡，这种情况一个单旋已经解决不了问题了，继续看图

这是一颗更牛马的失衡树，我们用单旋的逻辑会发现它咋旋都不能变到某一边失衡，所以我们需要左右结合一下，再用分置思维来先处理局部再处理整体。

先对3来个左旋，这样就变成一边失衡的情况了，再给它来个右旋

就又平衡了。这个双旋其实就是左右或者右左单旋一下就好，但是它的平衡因子才是不好搞的地方。我们得考虑到它的多种情况。

//左右双旋void RotateLR(node* parent){//还得先记录左和左的右node* subL = parent->_left;node* subLR = subL->_right;//但是旋完之后平衡因子就不准了 所以旋之前先记录//因为双旋的原因RL从孙子辈直接窜到爷爷辈去了int bf = subLR->_bf;//左旋右旋RotateL(parent->_left);RotateR(parent);//然后来判断平衡因子 如果等于0 好啊 旋之前就是平衡状态//也就是说可能亚健康插入个新节点 虽然整体失衡但是局部健康的情况if (bf == 0){//那这简直完美的一棵树 全等于0parent->_bf = subR->_bf = subRL->_bf = 0;}//不然就是我们推理的某一段从头到尾都失衡的情况 那么我们分为左或者右失衡//也就是往左或者右插入了一个节点 另一边为空的情况if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}// bf== 1的情况就是上面的图的情况 那么它旋完//我们只需要修改根 左 左的右 这三个地方的平衡因子就好else if(bf == 1){//咱看图平衡因子一目了然parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}}

bf = 0 的情况图 

一颗很完美的平衡因子都等于0的树

bf = -1的情况

那么右左双旋和单旋一样，逻辑相反。

//右左双旋void RotateRL(node* parent){node* subR = parent->_right;node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}

那么到这里，插入部分的核心已经都完成了。

收尾

找find

//findnode* 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;}

计算个数size

//计算节点个数int _size(node* root){if (root == nullptr){return 0;}return _size(root->_left) + _size(root->_right) + 1;}

判断是否是AVL树

//判断是否是AVL树bool _isBalanceTree(node* root){if (root == nullptr){//空树也是AVL树return true;}int lefthigh = _high(root->_left);int righthigh = _high(root->_right);int diff = righthigh - lefthigh;//如果计算的平衡因子和我们的平衡因子不一样就不是AVL树//且左右减的绝对值超过1也一定不是AVL树if (abs(diff) >= 2){cout << "高度不匹配" << endl;return false;}if (root->_bf != diff){cout << "平衡因子不匹配" << endl;return false;}//递归判断左右return _isBalanceTree(root->_left) && _isBalanceTree(root->_right);}

//高度int _high(node* root){if (root == nullptr){return 0;}int lefthigh = _high(root->_left);int righthigh = _high(root->_right);return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1;}

遍历 (中序)

//中序遍历void _inorder(node* root){if (root == nullptr){return;}_inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_inorder(root->_right);}