C++平衡树之AVL树

2401_87151858

956人浏览 · 2025-11-13 15:46:51

2401_87151858 · 2025-11-13 15:46:51 发布

前置知识：二叉搜索树点击回顾

1、引入

为了保持平衡，AVL树在二叉搜索树之上增加了以下限制：
对于树中的任意节点，其左右子树的高度差的绝对值不超过1。

为此需要在节点中新增一个_h记录以该节点为根的子树的高度。

AVL树示例图：
在这里插入图片描述

2、AVL树节点定义

template<class T>
struct AVLtree_node
{
    T _val; // 权值
    int _h; // 以该节点为根的子树的高度（为了保持平衡）
    int _cnt;   // 值为_val的节点的个数（为了支持插入重复数据）
    int _size;  // 以该节点为根的子树的大小（为了可以查询树中排名第k的节点）
	// _cnt与_size是我想测试插入与删除操作是否有bug，但奈何没有充足的测试数据，只能补全代码，然后拿洛谷P6136【模板】普通平衡树（数据加强版）去验证
	
    AVLtree_node* _left;    // 左儿子
    AVLtree_node* _right;   // 右儿子
    AVLtree_node* _parent;  // 父节点
    AVLtree_node(const T& x = T())
        :_val(x)
        ,_h(1)
        ,_cnt(1)
        ,_size(1)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
    {}
};

template<class T>
class AVLtree
{
	typedef AVLtree_node<T> node;
	typedef AVLtree_node<T>* node_ptr;
protected:
	node* _root = nullptr;
};

3、查找权值为val的节点

与二叉搜索树类似，从根节点开始找，若val小于当前节点的权值，就去左子树找；若val大于当前节点的权值，就去右子树找；找到了就直接返回。代码如下

	// find返回值：
	// 1.找到了返回权值为val的节点；
	// 2.找不到则返回其应当插入位置的父节点
	node* find(const T& val)
	{
		node* cur = _root;
		node* p = nullptr;	// 记录cur的父节点
		while (cur)
		{
			p = cur;
			if (val < cur->_val)
				cur = cur->_left;
			else if (val > cur->_val)
				cur = cur->_right;
			else
				return cur;	// 找到目标节点时直接返回
		}
		return p;	// 找不到则返回目标值应插入的位置的父节点
	}

4、插入操作

插入过程与上篇讲的二叉搜索树类似，不过AVL树会进行平衡调整。
例如在上述示例图插入10
在这里插入图片描述

然后要维护树的高度
问：新插入的节点可能会改变哪些节点的高度？
答：其祖先节点。
所以我们从插入的节点开始，一路往上更新每个节点的高度

在这里插入图片描述

插入操作代码框架：

	// 申请空间（为什么不直接写成new node(val)呢？因为后续可能引入类似内存池的东西）
	node* get_node(const T& val) { return new node(val); }
	// 释放空间
	void del_node(node* x) { delete x; }
	
	void insert(const T& val)
	{
		if (!_root)
		{
			_root = get_node(val);
			return;
		}
		node* cur = find(val);
		if (cur->_val == val)
			cur->_cnt++;		// 支持插入重复元素
		else
		{
			// 到这里说明未找到，cur是val应插入的位置的父节点
			node* p = cur;
			cur = get_node(val);
			cur->_parent = p;
			if (val < p->_val) p->_left = cur;
			else p->_right = cur;
		}

		// 插入节点后还需往上更新
		update(cur);
	}

注意：向上更新时，如果当前节点的左右子树的高度差的绝对值超过1了，需旋转调整
例如在AVL树示例图中插入-1
在这里插入图片描述
然后维护高度

此时说明该树已经不那么平衡了，需要旋转调整，调整后再继续往上更新

往上更新的代码框架

	// 计算以x为根的子树的高度
	int height(node* x) { return x ? x->_h : 0; }

	// 计算以x为根的子树的大小
	int size(node* x) { return x ? x->_size : 0; }

	// 更新x的_h与_size
	void push_up(node* x)
	{
		if (x)
		{
			x->_h = max(height(x->_left), height(x->_right)) + 1;
			x->_size = size(x->_left) + size(x->_right) + x->_cnt;
		}
	}
    void update(node* p)
    {
        while(p)
        {
            node* g = p->_parent;
            int l = height(p->_left), r =height(p->_right);
            if(abs(l - r) <= 1)
                push_up(p);
            else       // 平衡破坏，需旋转调整
                balance(p);
            p = g;
        }
    }

5、旋转操作

（由于我不会制作动图，旋转过程最好自己揣摩揣摩，画画图）
在这里插入图片描述
旋转后该子树仍满足二叉搜索树的性质，且A、B、C的高度显然不会改变，需更新p与x的高度。

代码如下：

	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   ====>   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateR(node* p)	// 右旋
    {
        node* g = p->_parent;
        node* x = p->_left;
        p->_left = x->_right;
        if(x->_right) x->_right->_parent = p;

        x->_right = p;
        p->_parent = x;

        x->_parent = g;
        if(g){
            if(p == g->_left) g->_left = x;
            else g->_right = x;
        }
		// 注意需先更新p，再更新x
        push_up(p);
        push_up(x);
        
        // 注意可能需要更新根节点
        if(_root == p) _root = x;
    }

	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   <====   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateL(node* x)	// 左旋，与右旋类似
    {
        node* g = x->_parent;
        node* p = x->_right;
        x->_right = p->_left;
        if(p->_left) p->_left->_parent = x;

        p->_left = x;
        x->_parent = p;

        p->_parent = g;
        if(g){
            if(x == g->_left) g->_left = p;
            else g->_right = p;
        }
        push_up(x);
        push_up(p);
        if(_root == x) _root = p;
    }

6、失衡调整

由于插入/删除一个节点后，子树的高度至多变化1，失衡情况只有以下两类：
在这里插入图片描述
由于第一类与第二类对称，后面将以第一类为例。
需对A与B的高度进行分类讨论，下文中的 $H (x)$ 表示以 $x$ 为根的子树的高度

情况一： $\geq H(B)$ （直线型）

在这里插入图片描述

1.LL型

在这里插入图片描述

感性地了解旋转后的正确性：
由于 $\geq H(B)$ ，则 $H (A) = h + 1$ ，那么 $\leq H(B) \leq h+1$ ，旋转后， $\leq H(g) \leq h+2$ 。可得出 $g$ 与 $A$ 的高度差不超过1， $B$ 与 $C$ 的高度差不超过1

2.RR型（与LL型对称）

在这里插入图片描述

情况二： $\lt H(B)$ （折线型）

在这里插入图片描述

1.LR型

这里需要把B分的更细一点

在这里插入图片描述

感性地了解旋转后的正确性：
初始时由于 $H (B) = h + 1$ ，假设 $\ge H(F)$ ，则 $H (E) = h$ ，那么 $\le H(F) \le h$ 。旋转两次后， $H (P) = h + 1$ ， $H (g) = h + 1$ ，此时该子树的所有节点都满足左右子树高度差不超过1。

2.RL型（与LR型对称）

在这里插入图片描述

代码如下

    void balance(node* p)
    {
        int l = height(p->_left), r =height(p->_right);
        if(l > r)
        {
            int ll = height(p->_left->_left), lr = height(p->_left->_right);
            // LL型
            //     p
            //    /
            //   ●
            //  /
            // ●    
            if(ll >= lr) 
                rotateR(p);
            // LR型
            //     p
            //    /
            //   ●
            //    \ 
            //     ●
            else{
                rotateL(p->_left);
                rotateR(p);
            }
        }
        else{
            int rr = height(p->_right->_right), rl = height(p->_right->_left);
            // RR型
            //  p
            //   \
            //    ●
            //     \
            //      ●
            if(rr >= rl)
                rotateL(p);
            // RL型
            //  p
            //   \
            //    ●
            //    /
            //   ●
            else{
                rotateR(p->_right);
                rotateL(p);
            }
        }
    }

失衡调整内容参考 AVL 树 - OI Wiki

7、删除操作

与二叉搜索树类似，不过AVL树会进行平衡调整。
被删除的节点分三种情况

叶子节点：直接删除
被删除的节点只有一个儿子：用该儿子替代
被删除的节点有两个儿子：用前驱替代，再删除前驱。（当然也可以用后继）

（以上三种情况上篇已经讲过，这里不过多赘述点击回顾二叉搜索树的删除）

删除节点后，会影响其祖先节点的高度，需往上更新。更新过程与插入操作的更新几乎完全一样。因为插入/删除操作所引发的失衡情况非常类似，在第6点我们已经分析过失衡后该如何旋转调整，下面直接给出代码

	void erase(const T& val)
    {
        if(!_root) return;
        node* cur = find(val);
        if(cur->_val == val)
        {
            cur->_cnt--;
            if(cur->_cnt != 0) 
				update(cur); // 注意删除后_h虽然没变，但_cnt变了，导致子树的大小也会改的，此时也需要往上调整
            else{
                node* p = cur->_parent;
                // 1.叶子节点：直接删除
                if(!cur->_left && !cur->_right)
                {
                    if(!p) _root = nullptr; // 特判只有一个节点
                    else if(cur == p->_left) 
						p->_left = nullptr;
                    else 
						p->_right = nullptr;
                    del_node(cur);
                    update(p);	// 删除后从父节点往上更新
                }
                // 2.只有一个儿子：用儿子替代
                else if(!cur->_left || !cur->_right)
                {
                    node* child = cur->_left ? cur->_left : cur->_right;
                    if(!p) _root = child;   // 特判只有一个节点
                    else if(p->_left == cur) 
						p->_left = child;
                    else 
						p->_right = child;
                    child->_parent = p;		// 别忘记连接父节点
                    del_node(cur);
                    update(p);	// 删除后从父节点往上更新
                }
                // 3.有两个儿子: 用前驱替代，然后删除前驱
                else{
                    // 找前驱
                    node* pre = cur->_left;
                    node* pre_parent = cur;
                    while(pre->_right) 
                    {
                        pre_parent = pre;
                        pre = pre->_right;
                    }
                    // 交换，然后删除前驱节点
                    std::swap(cur->_val, pre->_val);
                    std::swap(cur->_cnt, pre->_cnt);
                    // 到这里pre必定没有右儿子
                    if(pre_parent->_left == pre) 
						pre_parent->_left = pre->_left;
                    else 
						pre_parent->_right = pre->_left;
                    if(pre->_left) 
						pre->_left->_parent = pre_parent;
                    del_node(pre);
                    update(pre_parent);	// 删除pre后，需从其父节点往上更新
                }
            }
        }
    }

小总结

相比于普通二叉搜索树，AVL树的插入/删除只是多了一个向上更新，若更新发现高度失衡，则需调整，调整就分直线型、折线形两种情况，对于这两种情况有两种旋转方式，其正确性我们只需感性地了解即可。

8、找某个节点前驱

1.该节点存在左子树，则左子树的最右侧节点就是前驱

在这里插入图片描述

2.该节点不存在左子树，则向上找第一个往左拐的节点

在这里插入图片描述

代码如下

    node* get_prev(node* x)
    {
        if(!x) return nullptr;

        if(x->_left)
        {
            x = x->_left;
            while(x->_right)
                x = x->_right;
            return x;
        }
        else
		{
            node* p = x->_parent;
            while(p && x == p->_left)
            {
                x = p;
                p = p->_parent;
            }
            return p;
        }
    }

找某个节点的前驱搞定后，我们可以找到权值为val的前驱（前驱定义为小于val，且最大的数。注意树中可能不存在权值为val的节点）

	node* get_prev(const T& val)
    {
        node* cur = find(val);	
		// find
		// 1.找到了返回权值为val的节点；
		// 2.找不到则返回其应当插入位置的父节点，该父节点必定是val的前驱/后继！！！
		if (!cur)
			return nullptr; // cur为空，说明是个空树
        else if(cur->_val < val)
            return cur;
        else 
            return get_prev(cur);
    }

9、找某个节点后继

1.该节点存在右子树，则右子树的最左侧节点就是后继

在这里插入图片描述

2.该节点不存在右子树，则向上找第一个往右拐的节点

在这里插入图片描述
代码如下

    node* get_next(node* x)
    {
        if(!x) return nullptr;

        if(x->_right)
        {
            x = x->_right;
            while(x->_left)
                x = x->_left;
            return x;
        }
        else{
            node* p = x->_parent;
            while(p && x == p->_right)
            {
                x = p;
                p = p->_parent;
            }
            return p;
        }
    }

找某个节点的后继搞定后，我们可以找到权值为val的后继（后继定义为大于val，且最小的数。注意树中可能不存在权值为val的节点）

    node* get_next(const T& val)
    {
        node* cur = find(val);
		if (!cur)
			return nullptr;
        if(cur->_val > val)
            return cur;
        else 
            return get_next(cur);
    }

10、查询排名为k的节点

这部分类似基于快速排序的快速选择算法
快速选择算法参考leetcode官方题解一

令cur等于根结点，开始搜索
对当前结点cur进行如下操作：
- 如果 cur的左子树的结点数小于等于k，则第k小的元素一定在cur的左子树中，令cur等于其的左子结点，并继续搜索；
- 如果cur的左子树的结点数再加上cur的_cnt小于等于k，则第k小的元素即为cur，结束搜索；
- 如果cur的左子树的结点数left再加上cur的_cnt大于k，则第k小的元素一定在cur的右子树中，需去右子树中查询第k - left - _cnt小的元素

	node* kth(int k)
    {
		if (k > size(_root)) 
			return nullptr;
        node* cur = _root;
        while(cur)
        {
            if(k <= size(cur->_left))
                cur = cur->_left;
            else if(k <= size(cur->_left) + cur->_cnt)
                return cur;
            else{
                k -= size(cur->_left) + cur->_cnt;
                cur = cur->_right;
            }
        }
    }

查询排名为k的节点参考leetcode官方题解二

11、查询权值为val的排名

令cur等于根结点，开始搜索
对当前结点cur进行如下操作：
- 如果val < cur->_val，则val在以cur为根的子树的排名就等于val在以cur左子树为根的子树的排名。
- 如果val == cur->_val，则val在以cur为根的子树的排名就等于size(cur->_left) + 1。
- 如果val > cur->_val，则val在以cur为根的子树的排名就等于val在以cur右子树为根的子树的排名再加上size(cur->_left) + cur->_cnt。

	// 查询val的排名（val的排名定义为比val小的数的个数 + 1）
    int get_rank(const T& val)
    {
        int res = 0;
        node* cur = _root;
        while(cur)
        {
            if(val < cur->_val)
                cur = cur->_left;
            else if(val == cur->_val)
            {
                res += size(cur->_left);
                break;
            } 
            else{
                res += size(cur->_left) + cur->_cnt;
                cur = cur->_right;
            }
        }
        return res + 1;
    }

完整代码

补充了构造、析构、拷贝、赋值等内容，至于迭代器，将会放在后面的用AVL树封装set/map中讲

#include<iostream>
using namespace std;

template<class T>
struct AVLtree_node
{
    T _val; // 权值
    int _h; // 以该节点为根的子树的高度（为了保持平衡）
    int _cnt;   // 值为_val的节点的个数（为了支持插入重复数据）
    int _size;  // 以该节点为根的子树的大小（为了可以查询树中排名第k的节点）

    AVLtree_node* _left;    // 左儿子
    AVLtree_node* _right;   // 右儿子
    AVLtree_node* _parent;  // 父节点
    AVLtree_node(const T& x = T())
        :_val(x)
        ,_h(1)
        ,_cnt(1)
        ,_size(1)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
    {}
};


template<class T>
class AVLtree
{
	typedef AVLtree_node<T> node;
	typedef AVLtree_node<T>* node_ptr;
protected:
	node* _root = nullptr;
public:
	AVLtree(){}

	// 迭代器区间构造
	template<class InputIterator>
	AVLtree(InputIterator first, InputIterator last)
	{
		while (first != last)
		{
			insert(*first);
			++first;
		}
	}
	~AVLtree() { clear(); }
	void clear()
	{
		_clear(_root);
		_root = nullptr;
	}

	AVLtree(const AVLtree& t) { _root = copy(t._root); }

	void swap(AVLtree& t) { std::swap(_root, t._root); }
	AVLtree& operator= (const AVLtree& t)
	{
		if (this != &t)
		{
			AVLtree tmp(t);
			swap(tmp);
		}
		return *this;
	}

	// 打印AVL树
	void print() 
	{ 
		_print(_root); 
		cout << endl;
	}

	// 求树里面的元素个数
	int size() { return size(_root); }
	bool empty() { return !_root; }

	node* find(const T& val)
	{
		node* cur = _root;
		node* p = nullptr;	// 记录cur的父节点
		while (cur)
		{
			p = cur;
			if (val < cur->_val)
				cur = cur->_left;
			else if (val > cur->_val)
				cur = cur->_right;
			else
				return cur;
		}
		return p;
	}

	void insert(const T& val)
	{
		if (!_root)
		{
			_root = get_node(val);
			return;
		}
		node* cur = find(val);
		if (cur->_val == val)
			cur->_cnt++;
		else
		{
			// 到这里说明未找到，cur是val应插入的位置的父节点
			node* p = cur;
			cur = get_node(val);
			cur->_parent = p;
			if (val < p->_val) p->_left = cur;
			else p->_right = cur;
		}

		// 插入节点后还需往上更新
		update(cur);
	}

	void erase(const T& val)
    {
        if(!_root) return;
        node* cur = find(val);
        if(cur->_val == val)
        {
            cur->_cnt--;
            if(cur->_cnt != 0) 
				update(cur); // 注意删除后_h虽然没变，但_cnt变了，导致子树的大小也会改的，此时也需要往上调整
            else{
                node* p = cur->_parent;
                // 1.叶子节点：直接删除
                if(!cur->_left && !cur->_right)
                {
                    if(!p) _root = nullptr; // 特判只有一个节点
                    else if(cur == p->_left) 
						p->_left = nullptr;
                    else 
						p->_right = nullptr;
                    del_node(cur);
                    update(p);	// 删除后从父节点往上更新
                }
                // 2.只有一个儿子：用儿子替代
                else if(!cur->_left || !cur->_right)
                {
                    node* child = cur->_left ? cur->_left : cur->_right;
                    if(!p) _root = child;   // 特判只有一个节点
                    else if(p->_left == cur) 
						p->_left = child;
                    else 
						p->_right = child;
                    child->_parent = p;		// 别忘记连接父节点
                    del_node(cur);
                    update(p);	// 删除后从父节点往上更新
                }
                // 3.有两个儿子: 用前驱替代，然后删除前驱
                else{
                    // 找前驱
                    node* pre = cur->_left;
                    node* pre_parent = cur;
                    while(pre->_right) 
                    {
                        pre_parent = pre;
                        pre = pre->_right;
                    }
                    // 交换，然后删除前驱节点
                    std::swap(cur->_val, pre->_val);
                    std::swap(cur->_cnt, pre->_cnt);
                    // 到这里pre必定没有右儿子
                    if(pre_parent->_left == pre) 
						pre_parent->_left = pre->_left;
                    else 
						pre_parent->_right = pre->_left;
                    if(pre->_left) 
						pre->_left->_parent = pre_parent;
                    del_node(pre);
                    update(pre_parent);	// 删除pre后，需从其父节点往上更新
                }
            }
        }
    }

	node* get_prev(const T& val)
    {
        node* cur = find(val);	
		// find
		// 1.找到了返回权值为val的节点；
		// 2.找不到则返回其应当插入位置的父节点，该父节点必定是val的前驱/后继！！！
		if (!cur)
			return nullptr; // cur为空，说明是个空树
        else if(cur->_val < val)
            return cur;
        else 
            return get_prev(cur);
    }

	node* get_next(const T& val)
    {
        node* cur = find(val);
		if (!cur)
			return nullptr;
        if(cur->_val > val)
            return cur;
        else 
            return get_next(cur);
    }

	node* kth(int k)
    {
		if (k > size(_root)) 
			return nullptr;
        node* cur = _root;
        while(cur)
        {
            if(k <= size(cur->_left))
                cur = cur->_left;
            else if(k <= size(cur->_left) + cur->_cnt)
                return cur;
            else{
                k -= size(cur->_left) + cur->_cnt;
                cur = cur->_right;
            }
        }
    }

	// 查询val的排名（val的排名定义为比val小的数的个数 + 1）
    int get_rank(const T& val)    
    {
        int res = 0;
        node* cur = _root;
        while(cur)
        {
            if(val < cur->_val)
                cur = cur->_left;
            else if(val == cur->_val)
            {
                res += size(cur->_left);
                break;
            } 
            else{
                res += size(cur->_left) + cur->_cnt;
                cur = cur->_right;
            }
        }
        return res + 1;
    }

protected:
	void _clear(node* x)
	{
		if (!x) return;
		_clear(x->_left);
		_clear(x->_right);
		del_node(x);
	}

	node* copy(node* x)
	{
		if (!x) return nullptr;
		node* le = copy(x->_left);
		node* ri = copy(x->_right);
		node* root = get_node(x->_val);
		root->_left = le, root->_right = ri;
		if (le) le->_parent = root;
		if (ri) ri->_parent = root;
		return root;
	}

	void _print(node* x)
	{
		if (!x) return;
		_print(x->_left);
		cout << x->_val << ' ';
		_print(x->_right);
	}

	// 申请空间（为什么不直接写成new node(val)呢？因为后续可能引入类似内存池的东西）
	node* get_node(const T& val)  {  return new node(val);  }
	// 释放空间
	void del_node(node* x) { delete x; }

    node* get_prev(node* x)
    {
        if(!x) return nullptr;

        if(x->_left)
        {
            x = x->_left;
            while(x->_right)
                x = x->_right;
            return x;
        }
        else
		{
            node* p = x->_parent;
            while(p && x == p->_left)
            {
                x = p;
                p = p->_parent;
            }
            return p;
        }
    }


	node* get_next(node* x)
    {
        if(!x) return nullptr;

        if(x->_right)
        {
            x = x->_right;
            while(x->_left)
                x = x->_left;
            return x;
        }
        else{
            node* p = x->_parent;
            while(p && x == p->_right)
            {
                x = p;
                p = p->_parent;
            }
            return p;
        }
    }
    

	// 计算以x为根的子树的高度
	int height(node* x) { return x ? x->_h : 0; }

	// 计算以x为根的子树的大小
	int size(node* x) { return x ? x->_size : 0; }

	// 更新x的_h与_size
	void push_up(node* x)
	{
		if (x)
		{
			x->_h = max(height(x->_left), height(x->_right)) + 1;
			x->_size = size(x->_left) + size(x->_right) + x->_cnt;
		}
	}
    void update(node* p)
    {
        while(p)
        {
            node* g = p->_parent;
            int l = height(p->_left), r =height(p->_right);
            if(abs(l - r) <= 1)
                push_up(p);
            else       // 平衡破坏，需旋转调整
                balance(p);
            p = g;
        }
    }
	void balance(node* p)
	{
		int l = height(p->_left), r = height(p->_right);
		if (l > r)
		{
			int ll = height(p->_left->_left), lr = height(p->_left->_right);
			// LL型
			//     p
			//    /
			//   ●
			//  /
			// ●    
			if (ll >= lr)
				rotateR(p);
			// LR型
			//     p
			//    /
			//   ●
			//    \ 
            //     ●
			else {
				rotateL(p->_left);
				rotateR(p);
			}
		}
		else {
			int rr = height(p->_right->_right), rl = height(p->_right->_left);
			// RR型
			//  p
			//   \
            //    ●
			//     \
            //      ●
			if (rr >= rl)
				rotateL(p);
			// RL型
			//  p
			//   \
            //    ●
			//    /
			//   ●
			else {
				rotateR(p->_right);
				rotateL(p);
			}
		}
	}
	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   ====>   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateR(node* p)	// 右旋
    {
        node* g = p->_parent;
        node* x = p->_left;
        p->_left = x->_right;
        if(x->_right) x->_right->_parent = p;

        x->_right = p;
        p->_parent = x;

        x->_parent = g;
        if(g){
            if(p == g->_left) g->_left = x;
            else g->_right = x;
        }
		// 注意需先更新p，再更新x
        push_up(p);
        push_up(x);
        if(_root == p) // 注意可能需要更新根节点
			_root = x;
    }

	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   <====   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateL(node* x)	// 左旋，与右旋类似
    {
        node* g = x->_parent;
        node* p = x->_right;
        x->_right = p->_left;
        if(p->_left) p->_left->_parent = x;

        p->_left = x;
        x->_parent = p;

        p->_parent = g;
        if(g){
            if(x == g->_left) g->_left = p;
            else g->_right = p;
        }
        push_up(x);
        push_up(p);
        if(_root == x) _root = p;
    }
};

相关题目

【模板】普通平衡树
该题与下面的一样，这里只给出数据加强版的参考代码

【模板】普通平衡树（数据加强版）
参考代码

#include<iostream>
using namespace std;

template<class T>
struct AVLtree_node
{
    T _val; // 权值
    int _h; // 以该节点为根的子树的高度（为了保持平衡）
    int _cnt;   // 值为_val的节点的个数（为了支持插入重复数据）
    int _size;  // 以该节点为根的子树的大小（为了可以查询树中排名第k的节点）

    AVLtree_node* _left;    // 左儿子
    AVLtree_node* _right;   // 右儿子
    AVLtree_node* _parent;  // 父节点
    AVLtree_node(const T& x = T())
        :_val(x)
        ,_h(1)
        ,_cnt(1)
        ,_size(1)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
    {}
};

const int N = 1e5 + 1e6 + 10;
AVLtree_node<int> t[N];	// 预先申请好空间
int idx;	// 记录用到哪个节点了

template<class T>
class AVLtree
{
	typedef AVLtree_node<T> node;
	typedef AVLtree_node<T>* node_ptr;
protected:
	node* _root = nullptr;
public:
	node* find(const T& val)
	{
		node* cur = _root;
		node* p = nullptr;	// 记录cur的父节点
		while (cur)
		{
			p = cur;
			if (val < cur->_val)
				cur = cur->_left;
			else if (val > cur->_val)
				cur = cur->_right;
			else
				return cur;
		}
		return p;
	}

	// 申请空间（为什么不直接写成new node(val)呢？因为后续可能引入类似内存池的东西）
	node* get_node(const T& val) 
	{ 
		//return new node(val); 

		t[idx]._val = val;	// 直接从申请好的空间取
		return &t[idx++];
	}
	// 释放空间
	void del_node(node* x) 
	{ 
		//delete x; 
	}

	void insert(const T& val)
	{
		if (!_root)
		{
			_root = get_node(val);
			return;
		}
		node* cur = find(val);
		if (cur->_val == val)
			cur->_cnt++;
		else
		{
			// 到这里说明未找到，cur是val应插入的位置的父节点
			node* p = cur;
			cur = get_node(val);
			cur->_parent = p;
			if (val < p->_val) p->_left = cur;
			else p->_right = cur;
		}

		// 插入节点后还需往上更新
		update(cur);
	}

	void erase(const T& val)
    {
        if(!_root) return;
        node* cur = find(val);
        if(cur->_val == val)
        {
            cur->_cnt--;
            if(cur->_cnt != 0) 
				update(cur); // 注意删除后_h虽然没变，但_cnt变了，导致子树的大小也会改的，此时也需要往上调整
            else{
                node* p = cur->_parent;
                // 1.叶子节点：直接删除
                if(!cur->_left && !cur->_right)
                {
                    if(!p) _root = nullptr; // 特判只有一个节点
                    else if(cur == p->_left) 
						p->_left = nullptr;
                    else 
						p->_right = nullptr;
                    del_node(cur);
                    update(p);	// 删除后从父节点往上更新
                }
                // 2.只有一个儿子：用儿子替代
                else if(!cur->_left || !cur->_right)
                {
                    node* child = cur->_left ? cur->_left : cur->_right;
                    if(!p) _root = child;   // 特判只有一个节点
                    else if(p->_left == cur) 
						p->_left = child;
                    else 
						p->_right = child;
                    child->_parent = p;		// 别忘记连接父节点
                    del_node(cur);
                    update(p);	// 删除后从父节点往上更新
                }
                // 3.有两个儿子: 用前驱替代，然后删除前驱
                else{
                    // 找前驱
                    node* pre = cur->_left;
                    node* pre_parent = cur;
                    while(pre->_right) 
                    {
                        pre_parent = pre;
                        pre = pre->_right;
                    }
                    // 交换，然后删除前驱节点
                    std::swap(cur->_val, pre->_val);
                    std::swap(cur->_cnt, pre->_cnt);
                    // 到这里pre必定没有右儿子
                    if(pre_parent->_left == pre) 
						pre_parent->_left = pre->_left;
                    else 
						pre_parent->_right = pre->_left;
                    if(pre->_left) 
						pre->_left->_parent = pre_parent;
                    del_node(pre);
                    update(pre_parent);	// 删除pre后，需从其父节点往上更新
                }
            }
        }
    }

    node* get_prev(node* x)
    {
        if(!x) return nullptr;

        if(x->_left)
        {
            x = x->_left;
            while(x->_right)
                x = x->_right;
            return x;
        }
        else
		{
            node* p = x->_parent;
            while(p && x == p->_left)
            {
                x = p;
                p = p->_parent;
            }
            return p;
        }
    }
	node* get_prev(const T& val)
    {
        node* cur = find(val);	
		// find
		// 1.找到了返回权值为val的节点；
		// 2.找不到则返回其应当插入位置的父节点，该父节点必定是val的前驱/后继！！！
		if (!cur)
			return nullptr; // cur为空，说明是个空树
        else if(cur->_val < val)
            return cur;
        else 
            return get_prev(cur);
    }

	node* get_next(node* x)
    {
        if(!x) return nullptr;

        if(x->_right)
        {
            x = x->_right;
            while(x->_left)
                x = x->_left;
            return x;
        }
        else{
            node* p = x->_parent;
            while(p && x == p->_right)
            {
                x = p;
                p = p->_parent;
            }
            return p;
        }
    }
    node* get_next(const T& val)
    {
        node* cur = find(val);
		if (!cur)
			return nullptr;
        if(cur->_val > val)
            return cur;
        else 
            return get_next(cur);
    }

	node* kth(int k)
    {
		if (k > size(_root)) 
			return nullptr;
        node* cur = _root;
        while(cur)
        {
            if(k <= size(cur->_left))
                cur = cur->_left;
            else if(k <= size(cur->_left) + cur->_cnt)
                return cur;
            else{
                k -= size(cur->_left) + cur->_cnt;
                cur = cur->_right;
            }
        }
    }

	// 查询val的排名（val的排名定义为比val小的数的个数 + 1）
    int get_rank(const T& val)    
    {
        int res = 0;
        node* cur = _root;
        while(cur)
        {
            if(val < cur->_val)
                cur = cur->_left;
            else if(val == cur->_val)
            {
                res += size(cur->_left);
                break;
            } 
            else{
                res += size(cur->_left) + cur->_cnt;
                cur = cur->_right;
            }
        }
        return res + 1;
    }

protected:

	// 计算以x为根的子树的高度
	int height(node* x) { return x ? x->_h : 0; }

	// 计算以x为根的子树的大小
	int size(node* x) { return x ? x->_size : 0; }

	// 更新x的_h与_size
	void push_up(node* x)
	{
		if (x)
		{
			x->_h = max(height(x->_left), height(x->_right)) + 1;
			x->_size = size(x->_left) + size(x->_right) + x->_cnt;
		}
	}
    void update(node* p)
    {
        while(p)
        {
            node* g = p->_parent;
            int l = height(p->_left), r =height(p->_right);
            if(abs(l - r) <= 1)
                push_up(p);
            else       // 平衡破坏，需旋转调整
                balance(p);
            p = g;
        }
    }
	void balance(node* p)
	{
		int l = height(p->_left), r = height(p->_right);
		if (l > r)
		{
			int ll = height(p->_left->_left), lr = height(p->_left->_right);
			// LL型
			//     p
			//    /
			//   ●
			//  /
			// ●    
			if (ll >= lr)
				rotateR(p);
			// LR型
			//     p
			//    /
			//   ●
			//    \ 
            //     ●
			else {
				rotateL(p->_left);
				rotateR(p);
			}
		}
		else {
			int rr = height(p->_right->_right), rl = height(p->_right->_left);
			// RR型
			//  p
			//   \
            //    ●
			//     \
            //      ●
			if (rr >= rl)
				rotateL(p);
			// RL型
			//  p
			//   \
            //    ●
			//    /
			//   ●
			else {
				rotateR(p->_right);
				rotateL(p);
			}
		}
	}
	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   ====>   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateR(node* p)	// 右旋
    {
        node* g = p->_parent;
        node* x = p->_left;
        p->_left = x->_right;
        if(x->_right) x->_right->_parent = p;

        x->_right = p;
        p->_parent = x;

        x->_parent = g;
        if(g){
            if(p == g->_left) g->_left = x;
            else g->_right = x;
        }
		// 注意需先更新p，再更新x
        push_up(p);
        push_up(x);
        if(_root == p) // 注意可能需要更新根节点
			_root = x;
    }

	//     g               g
	//     |               |
    //     p               x
    //    / \             / \
    //   x   C   <====   A   p
    //  / \                 / \
    // A   B               B   C
    void rotateL(node* x)	// 左旋，与右旋类似
    {
        node* g = x->_parent;
        node* p = x->_right;
        x->_right = p->_left;
        if(p->_left) p->_left->_parent = x;

        p->_left = x;
        x->_parent = p;

        p->_parent = g;
        if(g){
            if(x == g->_left) g->_left = p;
            else g->_right = p;
        }
        push_up(x);
        push_up(p);
        if(_root == x) _root = p;
    }

};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, op, x, last = 0, res = 0;
	AVLtree<int> tree;
	cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        tree.insert(a);
    }
    for(int i = 0; i < m; i++)
    {
        cin >> op >> x;
        x ^= last;
        if(op == 1) tree.insert(x);
        else if(op == 2) tree.erase(x);
        else{
            if(op == 3) last = tree.get_rank(x);
            else if(op == 4) last = tree.kth(x)->_val;
            else if(op == 5) last = tree.get_prev(x)->_val;
            else last = tree.get_next(x)->_val;
            res ^= last;
        }
    }
    cout << res;
    return 0;
}

结语

AVL树的查询速度非常快，但插入/删除的旋转开销稍大，综合来看其效率确实很高。（但是STL的set/map底层用的一般是红黑树，因为红黑树插入/删除的开销相较于AVL会更小）
AVL树缺点：代码量太大了！！！
比赛时若需要用平衡树，更建议写Splay（参考董晓算法Splay）
或者直接用pb_ds库里面的（如果比赛允许的话）pb_ds用法参考 OI Wiki

感谢观看

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

2026企业微信AI Agent实测：7款技术方案对比

会话审计、敏感词管理、聊天质检、敏感行为识别、舆情、属性、词频及竞品分析覆盖服务风险；线索公海、客户、产品、商机、订单、回款、发票和业绩目标则连接销售全过程。快创助手负责快速建运营任务，策略生成把目标拆成方案，智能客服回答系统使用咨询，数据报表处理自然语言查数，AI洞察联合标签、订单和会话分析客户。我们设计了客户筛选、订单关联、销售交接、会话质检和异常恢复任务，配合技术访谈与行业公开资料复核。准备