网站导航
> 技术文档 > C++之AVL树的介绍以及AVL树自我实现

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

网友: 技术文档 2025-07-30 12:28:51

AVL

  • 一.AVL树的概念
  • 二.AVL树的实现
    • 2.1AVL树的结构
    • 2.2AVL树的插⼊
      • AVL树插⼊⼀个值的⼤概过程
      • 平衡因⼦更新
    • 2.3旋转
      • 左左不平衡----- 右旋
        • 代码解析
        • 示例说明
      • 右右不平衡 ----- 左旋
        • 左旋操作的背景
        • 左旋操作的逻辑
      • 代码解析
        • 示例说明
      • 左右双旋
        • 左右双旋的触发条件
        • 代码实现分析
        • 操作步骤详解
        • 旋转前后的树结构变化
      • 右左双旋
        • 右左双旋的触发条件
        • 代码实现分析
        • 操作步骤详解
        • 旋转前后的树结构变化
    • 2.4AVL树的查找
    • 2.5AVL树的检测（作为了解）

在这里插入图片描述

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

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

一.AVL树的概念

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

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

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

二.AVL树的实现

2.1AVL树的结构

  1. 节点定义
    我们首先定义一个AVLTreeNode类，用于表示AVL树的节点。
  2. 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树插⼊⼀个值的⼤概过程

  1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。

  2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可以停⽌了，具体情况我们下⾯再详细分析。

  3. 更新平衡因⼦过程中没有出现问题，则插⼊结束

  4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树的⾼度，不会再影响上⼀层，所以插⼊结束。

平衡因⼦更新

  1. 更新原则：

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

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

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

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

  1. 更新停⽌条件：

• 更新后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旋转

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

  1. 纯粹的左边高
  2. 左边高后右边高
  3. 右边高后左边高
  4. 纯粹的右边高
    旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
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;

旋转的原则

  1. 保持搜索树的规则

  2. 让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度

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

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

  1. 保存相关节点：

    • subL：parent的左子节点。
    • subLR：subL的右子节点。

  2. 调整指针：

    • 将parent的左子节点指向subL的右子节点（subLR）。
    • 如果subLR存在，将其父节点指向parent。
    • 将subL的右子节点指向parent。
    • 将parent的父节点指向subL。

  3. 更新父节点的父节点：

    • 如果parent是整棵树的根节点（parentParent == nullptr），则将subL设置为新的根节点。
    • 如果parent是某个节点的子节点，则根据parent在父节点中的位置（左子节点或右子节点），更新父节点的相应指针。

  4. 更新平衡因子：

    • 在右旋后，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;}
示例说明

  1. 左左不平衡情况：

    • 初始插入节点10，树结构为： 
      10
    • 插入节点5： 
       10 /5
    • 插入节点2： 
       10 / 5 /2

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

  2. 右旋操作：

    • 右旋操作将节点5提升为根节点，调整树结构为： 
       5 / \\ 2 10

      此时，树恢复平衡。

  3. 输出结果：

    • 中序遍历结果为：2 5 10，表示树结构已经调整为平衡状态。
      图解：
      C++之AVL树的介绍以及AVL树自我实现

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

左旋操作的背景

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

  1. 调整子节点关系：

    • 将subR的左子节点subRL移动到parent的右子节点位置。
    • 更新subRL的父节点为parent。

  2. 调整父节点关系：

    • 将subR的左子节点设置为parent。
    • 更新parent的父节点为subR。

  3. 更新父节点的子节点关系：

    • 如果parent是原树的根节点，更新根节点为subR。
    • 如果parent不是根节点，更新parent的父节点的子节点关系，确保树的结构正确。

  4. 重置平衡因子：

    • 将parent和subR的平衡因子设置为0。
示例说明

  1. 右右不平衡情况：

    • 初始插入节点10，树结构为： 
      10
    • 插入节点20： 
      10 \\ 20
    • 插入节点30： 
      10 \\ 20 \\ 30

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

  2. 左旋操作：

    • 左旋操作将节点20提升为根节点，调整树结构为： 
       20 / \\10 30

      此时，树恢复平衡。
      图解：C++之AVL树的介绍以及AVL树自我实现

左右双旋

左右双旋（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); // 非法平衡因子，触发断言 }}
操作步骤详解

  1. 节点标识：

    • parent：失衡的根节点（平衡因子为2）
    • subL：parent的左子节点（平衡因子为-1）
    • subLR：subL的右子节点（插入节点或其祖先）

  2. 双旋流程：

    • 第一步：对subL执行左旋（RotateL(parent->_left)），将subLR提升为parent的左子节点。
    • 第二步：对parent执行右旋（RotateR(parent)），将subLR提升为新的根节点。

  3. 平衡因子调整：

    • 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)

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

右左双旋

右左双旋（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);  // 非法平衡因子，触发断言 }}
操作步骤详解

  1. 节点标识：

    • parent：失衡的根节点（平衡因子为-2）
    • subR：parent的右子节点（平衡因子为1）
    • subRL：subR的左子节点（插入节点或其祖先）

  2. 双旋流程：

    • 第一步：对subR执行右旋（RotateR(parent->_right)），将subRL提升为parent的右子节点。
    • 第二步：对parent执行左旋（RotateL(parent)），将subRL提升为新的根节点。

  3. 平衡因子调整：

    • 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)

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

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

在这里插入图片描述

网络标签：

相关问题