AVL树实现（1）

AVL树实现（1）

1.AVL树的概念

• AVL树是最先发明的自平衡二叉查树，AVL是一颗空树，或者具备下列性质的二叉搜索树:它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization ofinformation》中发表了它。
• AVL树实现这里我们引入一个平衡因子(balance factor)的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1,AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。
• 思考一下为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢?0不是更好的平衡吗?画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如一棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0
• AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在log，那么增删查改的效率也可以控制在 O(log)，相比二叉搜索树有了本质的提升。

下面的两棵树，左边是AVL树，右边不是，因为我们插入了一个1

那么对于我们的10来说，右边是2，左边是0，那么2-0=2，就不满足AVL树的要求

2.AVL树的插入

1.插入一个值按二叉搜索树规则进行插入。

2.新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。

.更新平衡因子过程中没有出现问题，则插入结束

更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树4的高度，不会再影响上一层，所以插入结束。

插入的话就是比根节点大的话就往右子树走

比根节点小的话就往左子树走

更新原则

• 平衡因子=右子树高度-左子树高度
• 只有子树高度变化才会影响当前结点平衡因子。
• 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子--
• parent所在子树的高度是否变化决定了是否会继续往上更新

右边的高度是在插入1之前是0，左边高度是0

但是插入1后，左边高度变成了1，右边的高度还是0

这个平衡因子就从0变成了-1了

那么这个10这个节点也是会改变的，之前的右边是1，现在是2

左边之前是0，现在还是0，那么平衡因子是2

是否继续更新取决于parent所在的子树是否变化

更新停止条件

• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。
• 更新后parent的平衡因子等于1或 -1，更新前更新中parent的平衡因子变化为0->1或者 0->-1，说明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。
• 更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个:1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
• 不断更新，更新到根，跟的平衡因子是1或-1也停止了。

也可能影响到根节点的

在搜索树的插入基础之上我们进行AVL的数的插入操作

我们需要进行额外操作的是我们的平衡因子的更新操作

存在种情况，一种是你当前节点的平衡因子是-1或者1

第二种是0

第三种是2

第四种是其他报错情况了

每种情况有不同的解决方法

下面是插入的代码

但是我们没有对这个当平衡因子是2的情况进行完整的代码书写，因为我们的旋转操作还没学会

    bool Insert(ct pair<K, V>& kv)
    {
        if (_root == nullptr)//如果根节点是空的话，那么我们就创建一个节点
        {
            _root = new ode(kv);
            return true;
        }
        //树不是空的话
        ode* parent = nullptr;
        ode* 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;
            }
            //如果节点的值相等的话，那么我们直接返回false
            else
            {
                return false;
            }
        }
        //我们先利用循环到对应的位置，然后我们就进行节点的插入操作
        cur = new ode(kv);//先申请一个节点---这个是我们增的节点
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;//当前节点的父亲节点的指针就指向了parent
        //那么我们的新增的节点的平衡因子是0，那么这个是会影响到哪些节点呢？

        //更新平衡因子
        while (parent)//最坏的情况是更新到根节点，只要parent不为空的话那么我们持续进行更新操作
        {
            //所以的节点都有父亲，唯独一个节点没有父亲（根节点）
            if (cur == parent->_right)//如果插入在右边的话，那么parent的平衡因子要加加
            {
                parent->_bf++;
            }
            else//在根节点的左边,平衡因子--
            {
                parent->_bf--;
            }
            //平衡因子变成了0，那么就说明左右高度不变
            if (parent->_bf==0)//如果平衡因子更新到0了，那么我们直接break就行了
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
                //如果平衡因子是1或者是-1，那么我们就需要继续往上面进行更新
            {
                cur = parent;//我们先让当前的cur指向我们的parent
                parent = parent->_parent;//然后让parent走到我们父亲的父亲节点
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                //需要进行旋转操作
            }
            else//其他情况就是之前就出问题了
            {
                assert(false);//通过 assert(false) 强制中断，可以避免程序运行出错结果。
            }
        }


        return true;
    }    

.AVL树的右转

1.保持搜索树的规则

2.让旋转的树从不满足变平衡，其次降低旋转树的高度

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。说明:下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什么值都可以，只要大小关系符合搜索树的性质即可。

本图1展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图/图4/图5进行了详细描述。

在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。

旋转核心步骤，因为5<b子树的值<10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。

我们从第二幅图进行插入的操作，我们的左边的高度就变高了

那么我们现在进行调整操作，我们将b变成10的左子树，因为b比5大比10小，那么当10的左子树是合理的

并且我们让10当5的右子树，因为10大于5，那么也是合理的

下面的几幅图都是将5的右边变成了10的左边

右单旋代码

    //坑：
    /*
    1.我们需要对这个parent进行更新的操作，subLR的父亲以及我们父亲的新父亲
    2.我们存在这个subLR为空的情况的，如果不是空的话那么我们就进行下面的操作
    */
    //我们旋转之后我们还是需要保存在搜索树的特点的
    void RoatteR(ode* parent)
    {
        //对需要进行改动的节点进行标记
        //分别是父亲节点的左孩子，父亲节点的左孩子的右孩子
        //这个subL就是插入节点的父亲节点
        ode* subL = parent->_left;//我们这里将5命名为subL,将b命名为subR
        ode* subLR = subL->_right;

        parent->_left = subLR;//我们让subLR变成parent的左边
        //将subLR的父亲进行更新操作
        if (subLR)//这个subLR可能是空的,如果是空的咱们就不能进行里面的操作
        {
            subLR->_parent = parent;
        }
        //我们需要保证我们的_root进行更新，那么我们就需要一个虚拟的节点进行标记了
        ode* ppode = parent->_parent;//就是一开始父亲节点的父亲了
        subL->_right = parent;//parent变成subL的右边
        parent->_parent = subL;
        //操作完的话我们是需要将parent进行更新的
        //if (ppode == nullptr)
        //如果我们的父亲节点还是parent的话，那么我嫩就进行更新喜爱
        if(parent==_root)//更新下_root节点
        {
            _root = subL;
            subL->_parent = nullptr;//更新下subL的父亲节点，根节点是没有父亲的
        }
        //else就说明他不是根
        else//就是我们的parent上面还有父亲节点存在的
        {
            if (ppode->_left == parent)
            {
                ppode->_left = subL;
            }
            if (ppode->_right == parent)
            {
                ppode->_right = subL;
            }
            subL->_parent = ppode;


        }
        //最后旋转结束了，无论是什么情况这个平衡因子都是0
        parent->_bf = 0;
        subL->_bf = 0;
    }