C++：AVL树

一.AVL树介绍

*1.AVL***树的概念 **

二叉搜索树虽可以缩短查找的效率，但**如果数据有序或接近有序二叉搜索树将退化为单支树，查 **

找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii

和E.M.Landis在1962年发明了一种解决上述问题的方法：

*当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过*1(需要对树中的结点进行调整)**，即可降低树的高度，从而减少平均 搜索长度。

2.AVL****树性质

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

*它的左右子树都是AVL*树 **

左右子树高度之差**(简称平衡因子)**的绝对值不超过1(-1/0/1)（即：树中任何一个子树高度差都不超过1）

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log2 n),搜索时间复杂度O(log2 n)

3.为什么设计高度差不超过1？

只有满二叉树才能保证每个子树高度差是0（2^h-1）
做不到相等，退而求其次，左右高度差不超过1

4.AVL相比满二叉树:

完全二叉树:最后一层缺一些节点
AVL二叉树:最后两层缺一些节点

5.AVL树图例

二.模拟实现AVL树

阶段一：左单旋

右边高--左旋转
旋转原则:
1、保持搜索树的规则
2、子树变平衡

#pragma once

template<class K, class V>
struct AVLTreeNode
{
    pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;

    // 右子树-左子树的高度差
    int _bf;  // balance factor

    AVLTreeNode(const pair<K, V>& kv)
        :_kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _bf(0)
    {}

    // AVL树并没有规定必须要设计平衡因子
    // 只是一个实现的选择，方便控制平衡
};

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv)
    {
        // 1、搜索树的规则插入
        // 2、看是否违反平衡规则，如果违反就需要处理：旋转
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_bf = 0;
            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->_right)
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }

            // 是否继续更新？
            if (parent->_bf == 0)  // 1 or -1  -》 0  插入节点填上矮的那边
            {
                // 高度不变，更新结束
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
                // 0  -》 1 或 -1  插入节点导致一边变高了
            {
                // 子树的高度变了，继续更新祖先
                cur = cur->_parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
                // -1 or 1  -》 2 或 -2  插入节点导致本来高一边又变高了
            {
                // 子树不平衡 -- 需要旋转处理
                // ...
            }
            else
            {
                // 插入之前AVL就存在不平衡子树，|平衡因子| >= 2的节点
                assert(false);
            }
        }

        return true;
    }
private:
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
            subRL->_parent = parent;

        Node* ppNode = parent->_parent;

        subR->_left = parent;
        parent->_parent = subR;

        if (parent == _root)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subR;
            }
            else
            {
                ppNode->_right = subR;
            }

            subR->_parent = ppNode;
        }
    }

private:
    Node* _root = nullptr;
};

void TestAVLTree()
{
    AVLTree<int, int> t;
    t.Insert(make_pair(1, 1));
    t.Insert(make_pair(2, 2));
    t.Insert(make_pair(3, 3));
}