【C++】2.5 AVL树的实现（附代码）

用户11952558

发布于 2026-01-09 14:13:49

830

1. AVL树特点

AVL树是一种自平衡二叉搜索树，其核心特点如下：

左右子树高度差不超过1
平衡因子：右子树高度 - 左子树高度
通过旋转操作维持平衡

2. 模拟实现

2.1 成员结构

template<class K, class V>
struct treenode
{
    std::pair<K, V> _kv;
    treenode* _left;
    treenode* _right;
    treenode* _father;  // 指向父节点的指针
    int _bf;            // 平衡因子
    
    treenode(const std::pair<K, V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _father(nullptr)
        , _bf(0)
    { }
};

设计要点：

和搜索二叉树一样，有左右节点和一个pair键值对
由于需要从下到上处理高度差问题，因此需要指向父节点的指针
_bf负责存储平衡因子

2.2 插入操作

插入操作 = 搜索二叉树插入 + 平衡高度调整

节点更新后平衡因子的三种情况：

平衡因子 = 0（-1→0 或 1→0）：已经平衡，停止更新
平衡因子为 ±1（0→±1）：会影响父节点，继续向上更新
平衡因子为 ±2（-1→-2 或 1→2）：不符合AVL树，需要旋转，旋转完后停止更新

插入主逻辑：

bool insert(const std::pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new node(kv);
        return 1;
    }
    
    node* par = nullptr;
    node* cur = _root;
    
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            par = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            par = cur;
            cur = cur->_left;
        }
        else
        {
            return 0;  // 键值已存在
        }
    }
    
    cur = new node(kv);
    if (par->_kv.first < kv.first)
    {
        par->_right = cur;
    }
    else
    {
        par->_left = cur;
    }
    
    // 回溯更新平衡因子
    while (par)
    {
        if (cur == par->_left) par->_bf--;
        else par->_bf++;
        
        if (par->_bf == 0) break;
        else if (par->_bf == 1 || par->_bf == -1)
        {
            cur = par;
            par = par->_father;
        }
        else if (par->_bf == 2 || par->_bf == -2)
        {
            // 需要旋转
            if (par->_bf == -2 && cur->_bf == -1)
            {
                rotateR(par);  // 右单旋
            }
            else if (par->_bf == -2 && cur->_bf == 1)
            {
                rotateLR(par);  // 左右双旋
            }
            else if (par->_bf == 2 && cur->_bf == 1)
            {
                rotateL(par);  // 左单旋
            }
            else if (par->_bf == 2 && cur->_bf == -1)
            {
                rotateRL(par);  // 右左双旋
            }
            else
            {
                assert(0);
            }
            break;
        }
        else
        {
            assert(0);
        }
    }
    return 1;
}

3. 旋转操作

由于造成不平衡可能是左子树或右子树，因此先分为左旋和右旋。

3.1 右旋

右旋用于解决左子树过高的问题。造成左子树不平衡的可能是左左子树或左右子树，因此分为：

右单旋
左右双旋

（1）右单旋

想象有重力：提起左节点，让它变为根节点。

操作步骤：

原来的根节点有三个分支
将原来左节点的右枝砍断，接到原来的根节点上

右单旋的优点：

保持搜索树规则
使树变平衡
降低树高度

结束后平衡因子变化：根节点变为0，右节点变为0

代码实现：

void rotateR(node* par)
{
    node* subL = par->_left;
    node* subLR = subL->_right;
    
    par->_left = subLR;
    if (subLR)
        subLR->_father = par;
    
    node* pPar = par->_father;
    subL->_right = par;
    par->_father = subL;
    
    if (par == _root)
    {
        _root = subL;
        subL->_father = nullptr;
    }
    else
    {
        if (pPar->_left == par)
        {
            pPar->_left = subL;
        }
        else
        {
            pPar->_right = subL;
        }
        subL->_father = pPar;
    }
    
    subL->_bf = 0;
    par->_bf = 0;
}

注意事项：

par节点可能为根节点，此时需要更新根节点
par节点可能为ppar节点的左或右节点，需要先判断再连接

（2）左右双旋

此时造成左节点不平衡的原因是左节点的右节点过高。

变平衡的方式：先对子节点左旋，再对根节点右旋。

但由于平衡因子变化会因为左节点高还是右节点高而不同，因此要分情况讨论：

情况1：左节点高

先左旋左节点，再右旋根节点

情况2：右节点高

同样先左旋左节点，再右旋根节点

不同的部分即为蓝笔标出的部分，为什么平衡因子变化有区别就一目了然了。

平衡因子变化：

根节点为0
左节点、右节点为(-1, 0)或(0, 1)

由于节点8的左右子树会分别到节点5的右以及节点10的左，并且区别也就是节点8的两个子树，因此仅有两个节点会受影响。

（3）左右双旋特殊情况

左右双旋当只有三个节点时，平衡因子会变为(0, 0, 0)，需要注意。

代码实现：

void rotateLR(node* par)
{
    node* subL = par->_left;
    node* subLR = subL->_right;
    int bf = subLR->_bf;
    
    rotateL(par->_left);
    rotateR(par);
    
    if (bf == 1)
    {
        par->_bf = 0;
        subL->_bf = -1;
        subLR->_bf = 0;
    }
    else if (bf == -1)
    {
        par->_bf = 1;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == 0)
    {
        subLR->_bf = 0;
        subL->_bf = 0;
        par->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

为什么单旋调完了平衡因子，双旋复用时还要再调一次？ 因为双旋的第一次单旋本质上不是将二叉树调平衡，而是将二叉树调成有利于我们的不平衡结构。因此单旋无脑调成0的设定在双旋中是不适用的，三个关键节点的平衡因子还是需要手动调整。

3.2 左旋

左旋与右旋同理，只是方向相反。

右左双旋代码：

void rotateRL(node* par)
{
    node* subR = par->_right;
    node* subRL = subR->_left;
    int bf = subRL->_bf;
    
    rotateR(subR);
    rotateL(par);
    
    if (bf == 0)
    {
        subR->_bf = 0;
        subRL->_bf = 0;
        par->_bf = 0;
    }
    else if (bf == 1)
    {
        subR->_bf = 0;
        subRL->_bf = 0;
        par->_bf = -1;
    }
    else if (bf == -1)
    {
        subR->_bf = 0;
        subRL->_bf = 1;
        par->_bf = 0;
    }
    else
    {
        assert(0);
    }
}

4. 遍历操作

4.1 中序遍历

void _inorder()
{
    inorder(_root);
}

void inorder(node* root)
{
    if (root == nullptr) return;
    inorder(root->_left);
    std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;
    inorder(root->_right);
}

4.2 计算节点数量

size_t size()
{
    if (_root == nullptr) return 0;
    return _size(_root->_left) + _size(_root->_right) + 1;
}

size_t _size(node* root)
{
    if (root == nullptr) return 0;
    return _size(root->_left) + _size(root->_right) + 1;
}

5. 查找操作

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

利用搜索二叉树特点，用while循环寻找，返回节点指针。

6. 计算树高度

size_t height()
{
    return _height(_root);
}

size_t _height(node* root)
{
    if (root == nullptr) return 0;
    int l = _height(root->_left);
    int r = _height(root->_right);
    return l > r ? l + 1 : r + 1;
}

代码

#include<iostream>
#include<assert.h>

namespace bit
{
	template<class K, class V>
	struct treenode
	{
		std::pair<K, V> _kv;
		treenode* _left;
		treenode* _right;
		treenode* _father;
		int _bf;
		treenode(const std::pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _father(nullptr)
			, _bf(0)
		{
		}
	};
	template<class K, class V>
	class tree
	{
		typedef treenode<K, V> node;
	public:
		bool insert(const std::pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new node(kv);
				return 1;
			}
			node* par = nullptr;
			node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first < kv.first)
				{
					par = cur;
					cur = cur->_right;
				}
				else if (cur->_kv.first > kv.first)
				{
					par = cur;
					cur = cur->_left;
				}
				else
				{
					return 0;
				}
			}
			cur = new node(kv);
			if (par->_kv.first < kv.first)
			{
				par->_right = cur;
			}
			else
			{
				par->_left = cur;
			}
			cur->_father = par;
			while (par)
			{
				if (cur == par->_left)
					par->_bf--;
				else par->_bf++;
				if (par->_bf == 0)break;
				else if (par->_bf == 1 || par->_bf == -1)
				{
					cur = par;
 					par = par->_father;
				}
				else if (par->_bf == 2 || par->_bf == -2)
				{
					if (par->_bf == -2 && cur->_bf == -1)
					{
						rotateR(par);
					}
					else if (par->_bf == -2 && cur->_bf == 1)
					{
						rotateLR(par);
					}
					else if (par->_bf == 2 && cur->_bf == 1)
					{
						rotateL(par);
					}
					else if (par->_bf == 2 && cur->_bf == -1)
					{
						rotateRL(par);
					}
					else
					{
						assert(0);
					}
					break;
				}
				else
				{
					assert(0);
				}
			}
			return 1;
		}
		void rotateLR(node* par)
		{
			node* subL = par->_left;
			node* subLR = subL->_right;
			int bf = subLR->_bf;
			rotateL(par->_left);
			rotateR(par);
			if (bf == 1)
			{
				par->_bf = 0;
				subL->_bf = -1;
				subLR->_bf = 0;
			}
			else if (bf == -1)
			{
				par->_bf = 1;
				subL->_bf = 0;
				subLR->_bf = 0;

			}
			else if (bf == 0)
			{
				subLR->_bf = 0;
				subL->_bf = 0;
				par->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}
		void rotateRL(node* par)
		{
			node* subR = par->_right;
			node* subRL = subR->_left;
			int bf = subRL->_bf;
			rotateR(subR);
			rotateL(par);
			if (bf == 0)
			{
				subR->_bf = 0;
				subRL->_bf = 0;
				par->_bf = 0;
			}
			else if (bf == 1 )
			{
				subR->_bf = 0;
				subRL->_bf = 0;
				par->_bf = -1;
			}
			else if (bf == -1)
			{
				subR->_bf = 1;
				subRL->_bf = 0;
				par->_bf = 0;
			}
			else
			{
				assert(0);
			}
		}
		void rotateR(node* par)
		{
			node* subL = par->_left;
			node* subLR = subL->_right;

			par->_left = subLR;
			if (subLR)
				subLR->_father = par;

			node* pPar = par->_father;

			subL->_right = par;
			par->_father = subL;

			if (par == _root)
			{
				_root = subL;
				subL->_father = nullptr;
			}
			else
			{
				if (pPar->_left == par)
				{
					pPar->_left = subL;
				}
				else
				{
					pPar->_right = subL;
				}

				subL->_father = pPar;
			}

			subL->_bf = 0;
			par->_bf = 0;
		}

		void rotateL(node* par)
		{
			node* subR = par->_right;
			node* subRL = subR->_left;
			par->_right = subRL;
			if (subRL)
				subRL->_father = par;

			node* pPar = par->_father;
			subR->_left = par;
			par->_father = subR;
			if (par == _root)
			{
				_root = subR;
				subR->_father = nullptr;
			}
			else
			{
				if (par == pPar->_left)
				{
					pPar->_left = subR; 
				}
				else
				{
					pPar->_right = subR;
				}
				subR->_father = pPar;
			}

			par->_bf = subR->_bf = 0;
		}
		void inorder()
		{
			_inorder(_root);
		}
		size_t size()
		{
			if (_root == nullptr)return 0;
			return _size(_root->_left) + _size(_root->_right) + 1;
		}
		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;
				}
			}

			return nullptr;
		}
		size_t height()
		{
			return _height(_root);
		}
	private:
		node* _root = nullptr;
		void _inorder(node* root)
		{
			if (root == nullptr)return;
			_inorder(root->_left);
			std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;
			_inorder(root->_right);
		}
		size_t _size(node* root)
		{
			if (root == nullptr)return 0;
			return _size(root->_left) + _size(root->_right) + 1;
		}
		size_t _height(node* root)
		{
			if (root == nullptr)return 0;
			int l = _height(root->_left);
			int r = _height(root->_right);
			return l > r ? l + 1 : r + 1;
		}
	};
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除

c++