如何在AVL树中高效插入并保持平衡：一步步掌握旋转与平衡因子 —— 平衡因子以及AVL结构篇

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;                   // 平衡因子

    // 构造函数
    AVLTreeNode(const pair<K, V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _bf(0)
    {}
};

template<class K, class V>
class AVLTree 
{
    typedef AVLTreeNode<K, V> Node;  // 节点类型
public:

    // 其他操作（插入、删除、查找等）可以在此添加
    //	旋转
    
	/**/   旋转的详细讲解在下一篇文章，有兴趣的读者可以前往下一篇进行查看**

private:
    Node* _root;  // 根节点指针
};

	bool Insert(const pair<K, V>& kv) 
	{
        if (_root == nullptr) 
        {
            _root = new Node<K, V>(kv);
            return true;
    	}

        Node<K, V>* parent = nullptr;
        Node<K, V>* cur = _root;

        // 寻找插入位置
        while (cur) 
        {
            parent = cur;
            if (kv.first < cur->_kv.first) 
            {
                cur = cur->_left;
            } 
            else if (kv.first > cur->_kv.first) 
            {
                cur = cur->_right;
            } 
            else 
            {
                return false;  // 键值已存在
            }
        }

        // 创建新的节点并连接到父节点
        cur = new Node<K, V>(kv);
        if (kv.first < parent->_kv.first) 
        {
            parent->_left = cur;
        } 
        else 
        {
            parent->_right = cur;
        }
        cur->_parent = parent;

        // 更新平衡因子并处理不平衡
        while (parent) 
        {
            if (cur == parent->_left) 
            {
                parent->_bf--;  // 左子树高，平衡因子减1
            } 
            else 
            {
                parent->_bf++;  // 右子树高，平衡因子加1
            }
			//平衡因子 = 右子树 - 左子树

            // 如果平衡因子为0，结束更新
            if (parent->_bf == 0) 
            {
                break;
            }

            // 如果平衡因子为±1，继续向上更新
            if (parent->_bf == 1 || parent->_bf == -1) 
            {
                cur = parent;
                parent = parent->_parent;
            }
            // 如果平衡因子为±2，说明不平衡，进行旋转处理
            else if (parent->_bf == 2 || parent->_bf == -2) 
            {
                // 旋转处理
                /**/   旋转的详细讲解在下一篇文章，有兴趣的读者可以前往下一篇进行查看**
                if (parent->_bf == -2 && cur->_bf == -1)//左高（在左子树）——右旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)//右高（在左子树）——左旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)//左高（在右子树）——左右旋
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)//右高（在左子树）——右左旋
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
                break;
            } 
            else 
            {
                assert(false);  // 应该不会发生
            }
        }

        return true;
    }

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;
        }
    }

    // 如果遍历结束仍未找到目标节点，返回 nullptr
    return nullptr;
}