1. AVL树的概念

  • AVL树是最先发明的自平衡二叉搜索树。AVL树是一棵空树或是一棵具有以下性质的二叉搜索树：
    它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。
    AVL树是一棵高度平衡搜索二叉树，通过控制高度差去控制平衡。
  • 平衡因子：每个结点都有一个平衡因子，任何结点的平衡因子都等于其右子树的高度减去左子树的高度
    任何结点的平衡因子一定等于-1/0/1
  • AVL树整体结点数量和分布与完全二叉树类似，高度可以控制在logN，增删查改的效率也可以控制在O(logN)

2.AVL树的实现

2.1 AVL树的结构

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _bf; // 平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0) // 新增结点的平衡因子一定是0
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// ...
private:
	Node* _root = nullptr;
};

2.2 AVL树的插入

2.2.1 AVL树插入一个值的大概过程

  1. 插入一个值按二叉搜索树的规则进行插入。
  2. 插入结点后，只会影响其祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根节点路径上
    的结点的平衡因子，最坏情况下要更新到根。
  3. 更新平衡因子过程中没有出现问题则插入结束。
  4. 更新平衡因子过程中如果出现不平衡（平衡因子==2/-2），需要对不平衡子树进行旋转。旋转调平衡的同时也降低了子树的高
    度，不会再影响上一层，则插入结束。

2.2.2 平衡因子更新

更新规则：

  • 平衡因子 = 右子树高度 - 左子树高度
  • 只有子树高度变化才会影响当前结点平衡因子
  • 插入结点会增加高度，所以新增节点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，平衡因子–
  • parent的子树高度是否变化决定了是否继续往上更新

更新停止条件：

  • 更新后parent的平衡因子等于0，说明parent子树高度不变，不会影响parent父节点的平衡因子，更新结束
  • 更新后parent的平衡因子等于1或-1，parent所在子树符合平衡要求，但高度增加了1，会影响parent父节点的平衡因子，
    所以要继续向上更新
  • 更新后parent的平衡因子等于2或-2，说明AVL树的平衡被破坏，需要进行旋转。旋转后parent所在子树高度降低，所以旋
    转后也不需要继续向上更新，插入结束

2.2.3 插入结点及更新平衡因子代码实现

// 插入
bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		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->_left)
			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 && 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);
			break;
		}
		else
		{
			assert(false);
		}
	}
	return true;
}

2.3 旋转

2.3.1 旋转的原则

  1. 保持搜索树的规则
  2. 让旋转的树从不平衡到平衡，其次降低树的高度
    旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋

2.3.2 右单旋

  • 本图展示的是一棵以 10 为根的树，a/b/c 抽象为三棵高度为 h 的子树(h >= 0)，a/b/c 均满足 AVL 树的要求。10 可能是整棵树的根，也可能是整棵树中局部的子树的根（图中具体数值可以是任何值，只要大小关系满足 AVL 树的要求即可）。
  • 在 a 子树中插入一个新结点，导致 a 子树的高度从 h 变为 h + 1，不断向上更新平衡因子，导致 10 的平衡因子从 -1 变成 -2,10为根的树左右高度差超过1，违法平衡规则。10 为根的树左边高，需要往右边旋转，控制两棵树的平衡。
  • 旋转核心步骤：b 变为 5 的左子树，10 变成 5 的右子树，5 变成这棵树新的根，符合搜索树的规则，控制了平衡；同时这棵树的高度恢复到了插入之前的 h + 2，符合旋转原则。旋转后不会影响上一层，插入结束。
    右单旋

2.3.3 右单旋代码实现

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// 连接subLR与parent
	parent->_left = subLR;
	// subLR不为空时才能更改其parent
	if (subLR)
		subLR->_parent = parent;

	// 记录parent的原_parent
	Node* parentParent = parent->_parent;

	// 连接subL与parent
	subL->_right = parent;
	parent->_parent = subL;

	// parent有可能是整棵树的根，也可能是局部的子树
	// 如果是整棵树的根，要修改其_root
	if (parentParent == nullptr)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	// 如果是局部的子树要与上一层连接
	else
	{
		// 若parent为其原父节点的左孩子结点
		// 则修改原父节点的左孩子为subL
		if (parent == parentParent->_left)
		{
			parentParent->_left = subL;
		}
		// 若parent为其原父节点的右孩子结点
		// 则修改原父节点的右孩子为subL
		else
		{
			parentParent->_right = subL;
		}
		// 将subL的父节点指针指向parent的原_parent
		subL->_parent = parentParent;
	}

	// 此时parent和subL平衡，更新平衡因子为0
	subL->_bf = parent->_bf = 0;
}

2.3.4 左单旋

  • 本图展示的是一棵以 10 为根的树，a/b/c 抽象为三棵高度为 h 的子树(h >= 0)，a/b/c 均满足 AVL 树的要求。10 可能是整棵树的根，也可能是整棵树中局部的子树的根（图中具体数值可以是任何值，只要大小关系满足 AVL 树的要求即可）。
  • 在 a 子树中插入一个新结点，导致 a 子树的高度从 h 变为 h + 1，不断向上更新平衡因子，导致 10 的平衡因子从 1 变成 2,10为根的树左右高度差超过1，违法平衡规则。10 为根的树右边高，需要往左边旋转，控制两棵树的平衡。
  • 旋转核心步骤：b 变为 10 的右子树，10 变成 15 的左子树，15 变成这棵树新的根，符合搜索树的规则，控制了平衡；同时这棵树的高度恢复到了插入之前的 h + 2，符合旋转原则。旋转后不会影响上一层，插入结束。
    左单旋

2.3.5 左单旋代码实现

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

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

	Node* parentParent = parent->_parent;

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

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

2.3.6 左右双旋

新插入结点在失衡结点的左孩子的右子树上时
需要进行左右双旋。
根据旋转后平衡因子的变化可以分为三种情况

  1. h >= 1 时，新增结点在 e 子树，e 子树高度从 h - 1 变为 h，并不断更新 8->5 -> 10 的平衡因子，引发旋转，其中 8 的平衡因子为 -1，旋转后 8 和 5 平衡因子为 0，10 平衡因子为 1
  2. h >= 1 时，新增结点在 f 子树，f 子树高度从 h - 1 变为 h，并不断更新 8->5 -> 10 的平衡因子，引发旋转，其中 8 的平衡因子为 1，旋转后 8 和 10 平衡因子为 0，5 平衡因子为 -1
  3. h == 0 时， a/b/c 都是空树， b 本身就是新增结点，不断更新 5->10 平衡因子，引发旋转，其中 8 的平衡因子为 0，旋转后 8 和 5 和 10 的平衡因子均为 0

左右双旋

2.3.7 左右双旋代码实现

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(subL);
	RotateR(parent);

	if (bf == 0)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.3.8 右左双旋

新插入结点在失衡结点的右孩子的左子树上时
需要进行右左双旋。
根据旋转后平衡因子的变化可以分为三种情况

  1. h >= 1 时，新增结点在 e 子树，e 子树高度从 h - 1 变为 h，并不断更新 12->15 -> 10 的平衡因子，引发旋转，其中 12 的平衡因子为 -1，旋转后 10 和 12 平衡因子为 0，15 平衡因子为 1
  2. h >= 1 时，新增结点在 f 子树，f 子树高度从 h - 1 变为 h，并不断更新 12->15 -> 10 的平衡因子，引发旋转，其中 12 的平衡因子为 1，旋转后 15 和 12 平衡因子为 0，10 平衡因子为 -1
  3. h == 0 时， a/b/c 都是空树， b 本身就是新增结点，不断更新 15->10 平衡因子，引发旋转，其中 12 的平衡因子为 0，旋转后 10 和 12 和 15 的平衡因子均为 0
    右左双旋

2.3.9 右左双旋代码实现

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(subR);
	RotateL(parent);

	if (bf == 0)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = -1;
	}
	else
	{
		assert(false);
	}
}

2.4 AVL树查找

AVL 树查找逻辑与二叉搜索树逻辑相同，搜索效率为O(logN)

Node* Find(const K& key)
{
	Node* cur = _root;

	while (cur) {
		if (key > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else if (key < cur->_kv.first)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}

	return nullptr;
}

2.5 AVL 树平衡检测

通过检查左右子树高度差可以验证AVL树是否合格，同时可以检查平衡因子是否出现问题

bool IsBalanceTree()
{
	return _IsBalanceTree(_root);
}

bool _IsBalanceTree(Node* root)
{
	if (root == nullptr)
	{
		// 空树也是AVL树
		return true;
	}

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;

	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "高度差异常" << endl;
	}
	
	if (diff != root->_bf)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
	}

	// 左右子树都是AVL树则该树一定是AVL树
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
# c++ # 开发语言 # 数据结构
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

AI 一周大事盘点（2026 年 7 月 12 日～2026 年 7 月 19 日）

avatar 亚马逊云科技技术品牌专区

深度解析：用 TDengine 重构物联网平台设备接入的时序数据存储的技术选型

从物联网场景看，由于预处理任务和原始信息写入不同步，用户经常发现同一时段的聚合结果和原始数据对不上，引发业务部门的质疑。从物联网场景看，保存原始秒级数据的同时，还需要按分钟、小时、天预聚合，预处理链路冗长。从物联网场景看，聚合数据与原始数据存放在同一平台中，保证了一致性，也减少了 ETL 任务的开发和维护支出。从物联网场景看，由此可见，设备导入 的数字化转型不仅是技术替换，更是记录治理和业务流程的

avatar 亚马逊云科技技术品牌专区
cover

WEEX Labs 周度观察：AI 基础设施的“权力重构”与实体经济的“深潜运动”

avatar 亚马逊云科技技术品牌专区