C++之AVL树的介绍以及AVL树自我实现

用户11991900

发布于 2026-01-15 12:05:17

AVL树是一种自平衡的二叉查找树，它的名字来源于它的发明者G.M. Adelson-Velsky和E.M. Landis。

AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树，通过控制⾼度差去控制平衡。

一.AVL树的概念

AVL树实现这⾥我们引⼊⼀个平衡因子(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样。AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在，那么增删查改的效率也可以控制在logN，相⽐⼆叉搜索树有了本质的提升。

理解 AVL 树的关键在于把握三个核心概念：

平衡因子（Balance Factor）：节点左子树高度减去右子树高度的值，AVL 树中所有节点的平衡因子只能是 - 1、0 或 1
高度计算：节点的高度定义为从该节点到最远叶子节点的路径长度，空节点高度为 - 1
失衡检测：当某个节点的平衡因子绝对值大于 1 时，树的平衡被破坏，需要通过旋转操作恢复平衡

二.AVL树的实现

2.1AVL树的结构

节点定义我们首先定义一个AVLTreeNode类，用于表示AVL树的节点。
AVL树类接下来，我们定义一个AVLTree类，包含插入操作和旋转操作。

template<class K, class V>

struct AVLTreeNode

{
 // 需要parent指针，后续更新平衡因⼦可以看到 
 pair<K, V> _kv;
 AVLTreeNode<K, V>* _left;
 AVLTreeNode<K, V>* _right;
 AVLTreeNode<K, V>* _parent;
 int _bf; // balance factor

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

2.2AVL树的插⼊

AVL树插⼊⼀个值的⼤概过程

插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。
新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可以停⽌了，具体情况我们下⾯再详细分析。
更新平衡因⼦过程中没有出现问题，则插⼊结束
更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树的⾼度，不会再影响上⼀层，所以插⼊结束。

平衡因⼦更新

更新原则：

• 平衡因⼦=右⼦树⾼度-左⼦树⾼度

• 只有⼦树⾼度变化才会影响当前结点平衡因⼦。

• 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦–

• parent所在⼦树的⾼度是否变化决定了是否会继续往上更新

更新停⽌条件：

• 更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0，说明更新前parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束。

• 更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响parent的⽗亲结点的平衡⼦，所以要继续向上更新。

• 更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求。需要旋转处理，旋转的⽬标有两个：1、把parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。

• 不断更新，更新到根，跟的平衡因⼦是1或-1也停⽌了。

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)
 {
 	// 不平衡了，旋转处理 
	 break;
 }
 	else
 	{
 		assert(false);
 	}
 }
 return true;
}

2.3旋转

要进行旋转的情况无非有以下四种，

纯粹的左边高
左边高后右边高
右边高后左边高
纯粹的右边高旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

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;

旋转的原则

保持搜索树的规则
让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度

左左不平衡----- 右旋

右旋操作的核心思想是将当前节点（parent）的左子节点（subL）提升为新的父节点，并调整相关指针。以下是右旋的具体步骤：

保存相关节点：
- subL：parent的左子节点。
- subLR：subL的右子节点。
调整指针：
- 将parent的左子节点指向subL的右子节点（subLR）。
- 如果subLR存在，将其父节点指向parent。
- 将subL的右子节点指向parent。
- 将parent的父节点指向subL。
更新父节点的父节点：
- 如果parent是整棵树的根节点（parentParent == nullptr），则将subL设置为新的根节点。
- 如果parent是某个节点的子节点，则根据parent在父节点中的位置（左子节点或右子节点），更新父节点的相应指针。
更新平衡因子：
- 在右旋后，parent和subL的平衡因子都被设置为0。这是因为右旋操作通常用于调整局部不平衡，而这种调整通常会使两个节点的平衡因子归零。

代码解析

以下是代码的详细解析：

void RotateR(Node* parent)
{
    Node* subL = parent->_left;  // 保存parent的左子节点
    Node* subLR = subL->_right;  // 保存subL的右子节点

    // 调整parent的左子节点指向subLR
    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;  // 如果subLR存在，更新其父节点

    // 调整subL的右子节点指向parent
    Node* parentParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;

    // 更新parent的父节点
    if (parentParent == nullptr)
    {
        // 如果parent是整棵树的根节点
        _root = subL;  // 将subL设置为新的根节点
        subL->_parent = nullptr;  // 根节点的父节点为nullptr
    }
    else
    {
        // 如果parent是某个节点的子节点
        if (parent == parentParent->_left)
        {
            // 如果parent是父节点的左子节点
            parentParent->_left = subL;
        }
        else
        {
            // 如果parent是父节点的右子节点
            parentParent->_right = subL;
        }
        subL->_parent = parentParent;  // 更新subL的父节点
    }

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

示例说明

左左不平衡情况：

初始插入节点10，树结构为：

插入节点5：

   10
  /
5

插入节点2：

此时，根节点10的左子树高度为2，右子树高度为0，平衡因子为2，导致左左不平衡。

右旋操作：

右旋操作将节点5提升为根节点，调整树结构为：

   5
  / \
 2   10

此时，树恢复平衡。

输出结果：

中序遍历结果为：2 5 10，表示树结构已经调整为平衡状态。图解：

右右不平衡 ----- 左旋

左旋操作的背景

在AVL树中，如果插入或删除节点后，某个节点的平衡因子（左子树高度 - 右子树高度）的绝对值大于1，就需要通过旋转操作来恢复平衡。左旋操作主要用于解决右右不平衡的情况，即某个节点的右子树的右子树高度过高。

左旋操作的逻辑

假设我们有一个节点parent，其右子树的右子树高度过高，导致右右不平衡。左旋操作的目的是将parent的右子节点subR提升为新的根节点，同时调整parent和subR的子节点关系，以恢复平衡。

代码解析

以下是代码的详细解析：

void RotateL(Node* parent)
{
    Node* subR = parent->_right;  // subR是parent的右子节点
    Node* subRL = subR->_left;    // subRL是subR的左子节点

    // 1. 将subR的左子节点（subRL）移动到parent的右子节点位置
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;  // 更新subRL的父节点为parent

    // 2. 将subR的左子节点设置为parent
    subR->_left = parent;
    parent->_parent = subR;  // 更新parent的父节点为subR

    // 3. 更新subR的父节点
    Node* parentParent = parent->_parent;
    if (parentParent == nullptr)
    {
        // 如果parent是原树的根节点，更新根节点为subR
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        // 如果parent不是根节点，更新parent的父节点的子节点关系
        if (parent == parentParent->_left)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }
        subR->_parent = parentParent;
    }

    // 4. 重置平衡因子
    parent->_bf = subR->_bf = 0;
}

调整子节点关系：
- 将subR的左子节点subRL移动到parent的右子节点位置。
- 更新subRL的父节点为parent。
调整父节点关系：
- 将subR的左子节点设置为parent。
- 更新parent的父节点为subR。
更新父节点的子节点关系：
- 如果parent是原树的根节点，更新根节点为subR。
- 如果parent不是根节点，更新parent的父节点的子节点关系，确保树的结构正确。
重置平衡因子：
- 将parent和subR的平衡因子设置为0。

示例说明

右右不平衡情况：

初始插入节点10，树结构为：

插入节点20：

10
 \
  20

插入节点30：

此时，根节点10的右子树高度为2，左子树高度为0，平衡因子为-2，导致右右不平衡。

左旋操作：

左旋操作将节点20提升为根节点，调整树结构为：

  20
 /  \
10   30

此时，树恢复平衡。图解：

左右双旋

左右双旋（LR旋转）是AVL树中处理"左-右"失衡的关键操作，通过结合左旋和右旋来恢复树的平衡。

左右双旋的触发条件

当节点的平衡因子为 2（左子树比右子树高2），且其左子节点的平衡因子为 -1（左子树的右子树导致失衡）时，需要执行左右双旋。

代码实现分析

void RotateLR(Node* parent)
{
    // 1. 保存关键节点指针
    Node* subL = parent->_left;       // 左子节点
    Node* subLR = subL->_right;       // 左子节点的右子节点（失衡关键节点）
    int bf = subLR->_bf;              // 记录subLR的平衡因子，用于后续调整
    
    // 2. 执行双旋操作
    RotateL(parent->_left);           // 先对左子节点执行左旋
    RotateR(parent);                  // 再对父节点执行右旋
    
    // 3. 根据subLR的原始平衡因子调整各节点的平衡因子
    if (bf == 0) {                    // 插入节点是subLR自身
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == -1) {              // 插入节点在subLR的右子树
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    }
    else if (bf == 1) {               // 插入节点在subLR的左子树
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else {
        assert(false);                // 非法平衡因子，触发断言
    }
}

操作步骤详解

节点标识：
- parent：失衡的根节点（平衡因子为2）
- subL：parent的左子节点（平衡因子为-1）
- subLR：subL的右子节点（插入节点或其祖先）
双旋流程：
- 第一步：对subL执行左旋（RotateL(parent->_left)），将subLR提升为parent的左子节点。
- 第二步：对parent执行右旋（RotateR(parent)），将subLR提升为新的根节点。
平衡因子调整：
- bf记录了subLR的原始平衡因子，用于判断插入位置：
  - bf == 0：插入节点是subLR自身，旋转后所有节点平衡因子为0。
  - bf == -1：插入节点在subLR的右子树，旋转后parent的左子树高度增加1。
  - bf == 1：插入节点在subLR的左子树，旋转后subL的右子树高度增加1。

旋转前后的树结构变化

        parent(2)                 parent(2)                 subLR(0)
       /            左旋(subL)     /         右旋(parent)    /    \
    subL(-1)      --------->    subLR(0)     --------->   subL(0) parent(0)
       \                       /
      subLR(0)               subL(0)

图解：

右左双旋

右左双旋（RL旋转）是AVL树中处理"右-左"失衡的关键操作，通过结合右旋和左旋来恢复树的平衡。

右左双旋的触发条件

当节点的平衡因子为 -2（右子树比左子树高2），且其右子节点的平衡因子为 1（右子树的左子树导致失衡）时，需要执行右左双旋。

代码实现分析

void RotateRL(Node* parent)
{
    // 1. 保存关键节点指针
    Node* subR = parent->_right;       // 右子节点
    Node* subRL = subR->_left;         // 右子节点的左子节点（失衡关键节点）
    int bf = subRL->_bf;               // 记录subRL的平衡因子，用于后续调整
    
    // 2. 执行双旋操作
    RotateR(parent->_right);           // 先对右子节点执行右旋
    RotateL(parent);                   // 再对父节点执行左旋
    
    // 3. 根据subRL的原始平衡因子调整各节点的平衡因子
    if (bf == 0) {                     // 插入节点是subRL自身
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == 1) {                // 插入节点在subRL的左子树
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = -1;
    }
    else if (bf == -1) {               // 插入节点在subRL的右子树
        subR->_bf = 1;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else {
        assert(false);                 // 非法平衡因子，触发断言
    }
}

操作步骤详解

节点标识：
- parent：失衡的根节点（平衡因子为-2）
- subR：parent的右子节点（平衡因子为1）
- subRL：subR的左子节点（插入节点或其祖先）
双旋流程：
- 第一步：对subR执行右旋（RotateR(parent->_right)），将subRL提升为parent的右子节点。
- 第二步：对parent执行左旋（RotateL(parent)），将subRL提升为新的根节点。
平衡因子调整：
- bf记录了subRL的原始平衡因子，用于判断插入位置：
  - bf == 0：插入节点是subRL自身，旋转后所有节点平衡因子为0。
  - bf == 1：插入节点在subRL的左子树，旋转后parent的右子树高度减少1。
  - bf == -1：插入节点在subRL的右子树，旋转后subR的左子树高度增加1。

旋转前后的树结构变化

        parent(-2)                parent(-2)                 subRL(0)
          \           右旋(subR)      \         左旋(parent)    /    \
          subR(1)     --------->      subRL(0)    --------->   parent(0) subR(0)
          /                         \
       subRL(0)                     subR(0)

图解：

2.4AVL树的查找

那⼆叉搜索树逻辑实现即可，搜索效率为O(logN)

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

2.5AVL树的检测（作为了解）

我们实现的AVL树是否合格，我们通过检查左右⼦树⾼度差的的程序进⾏反向验证，同时检查⼀下结点的平衡因⼦更新是否出现了问题。

int _Height(Node* root)
{
 if (root == nullptr)
 return 0;
 int leftHeight = _Height(root->_left);
 int rightHeight = _Height(root->_right);
 return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

bool _IsBalanceTree(Node* root)
{
 // 空树也是AVL树 
 if (nullptr == root)
 return true;
 // 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 
 int leftHeight = _Height(root->_left);
 int rightHeight = _Height(root->_right);
 int diff = rightHeight - leftHeight;
 // 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 
 // pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树 
 if (abs(diff) >= 2)
 {
 cout << root->_kv.first << "⾼度差异常" << endl;
 return false;
 }
 if (root->_bf != diff)
 {
 cout << root->_kv.first << "平衡因⼦异常" << endl;
 return false;
 }
 // pRoot的左和右如果都是AVL树，则该树⼀定是AVL树 
 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

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

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

c++