C++AVL树

template<class T>
struct AVLTreeNode
{
	//三叉链
	AVLTreeNode<T>* _left;
	AVLTreeNode<T>* _right;
	AVLTreeNode<T>* _parent;
	
	int _bf;//平衡因子
	T _kv;//T可以是key也可以是pair<K,V>类型便于封装成map或set

	AVLTreeNode(const T& t)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(t)
	{}
};

pair<Node*, bool> Insert(const pair<K,V>& kv)
{
    if (_root == nullptr)//空树的情况
    {
        _root = new Node(kv);
        return make_pair(_root, true);
    }
    //插入需要链接父子节点，但是插入的位置是空节点，需要另一个指针记录父结点
    Node* cur = _root, *parent = _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else//找到了相同的
        {
            return make_pair(cur,false);
        }
    }
    //找到插入位置，创建链接节点
    cur = new Node(kv);
    Node* newnode = cur;//记录新结点地址，便于返回
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    cur->_parent = parent;

    //向上更新平衡因子
    while (cur != _root)
    {
        if (parent->_right == cur)
        {
            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)//子树已经不平衡了,需要进行旋转处理
        {
            if (parent->_bf == -2)
            {
                if (cur->_bf == -1)//右单旋
                {
                    RotateR(parent);
                }
                else//左右双旋
                {
                    RotateLR(parent);
                }
            }
            else
            {
                if (cur->_bf == 1)//右单旋
                {
                    RotateL(parent);
                }
                else//右左双旋
                {
                    RotateRL(parent);
                }
            }
            break;
        }
        else//已经出错了
        {
            assert(false);
        }
    }
    return make_pair(newnode, true);
}

// 左单旋
void RotateL(Node* parent)
{
    //记录节点信息
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* parentP = parent->_parent;

    //修改链接关系
    parent->_right = subRL;
    if (subRL)//避免为空节点的情况
        subRL->_parent = parent;

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

    //讨论父节点的情况
    if (parent == _root)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (parentP->_left == parent)
        {
            parentP->_left = subR;
        }
        else
        {
            parentP->_right = subR;
        }
        subR->_parent = parentP;
    }

    //更新平衡因子
    subR->_bf = parent->_bf = 0;
}

// 右单旋
void RotateR(Node* parent)
{
    //记录节点信息
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* parentP = parent->_parent;

    //修改链接关系
    parent->_left = subLR;
    if (subLR)//避免为空节点的情况
        subLR->_parent = parent;

    subL->_right = parent;
    parent->_parent = subL;

    //讨论父节点的情况
    if (parent == _root)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (parentP->_left == parent)
        {
            parentP->_left = subL;
        }
        else
        {
            parentP->_right = subL;
        }
        subL->_parent = parentP;
    }

    //更新平衡因子
    subL->_bf = parent->_bf = 0;
}

// 左右双旋
void RotateLR(Node* parent)
{
    //记录节点地址和平衡因子
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    int bf = subLR->_bf;
    //旋转
    RotateL(subL);
    RotateR(parent);

    //处理平衡因子
    if (bf == -1)//新增节点为subLR的左子树
    {
        subLR->_bf = 0;
        parent->_bf = 1;
        subL->_bf = 0;
    }
    else if (bf == 1)//新增节点为subRL的右子树
    {
        subL->_bf = -1;
        parent->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == 0)//新增节点就是subRL
    {
        subLR->_bf = 0;
        parent->_bf = 0;
        subL->_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);

    //处理平衡因子
    if (bf == -1)//新增节点为subLR的左子树
    {
        subRL->_bf = 0;
        parent->_bf = 0;
        subR->_bf = 1;
    }
    else if (bf == 1)//新增节点为subLR的右子树
    {
        subRL->_bf = 0;
        parent->_bf = -1;
        subR->_bf = 0;
    }
    else if (bf == 0)//新增节点就是subLR
    {
        subRL->_bf = 0;
        parent->_bf = 0;
        subR->_bf = 0;
    }
    else //旋转之前就已经存在错误了
    {
        assert(false);
    }
}

void _InOrder(Node* root)
{
    if (root == nullptr)
        return;

    _InOrder(root->_left);
    cout << root->_kv.first << " : " << root->_kv.second << endl;
    _InOrder(root->_right);
}

//验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* root)
{
    //空树
    if (root == nullptr)
        return true;
	//比较高度
    int heightL = _Height(root->_left);
    int heightR = _Height(root->_right);
    //检查平衡因子是否有误
    if (heightR - heightL != root->_bf)
    {
        cout << "平衡因子错误：" << root->_kv.first << endl;
        return false;
    }

    return abs(heightR - heightL) < 2
        && _IsAVLTree(root->_left)
        && _IsAVLTree(root->_right);//递归检查左右子树
}
//高度
size_t _Height(Node* root)
{
    //空节点
    if (root == nullptr)
        return 0;

    size_t left = _Height(root->_left);
    size_t right = _Height(root->_right);

    return left > right ? left + 1 : right + 1;
}