平衡二叉树（AVL树）

文章目录

  • 平衡二叉树（AVL树）
    • 1、平衡二叉树概念
    • 2、平衡二叉树的的实现
      • 2.1、平衡二叉树的结点定义
      • 2.2、平衡二叉树的插入
      • 2.3、平衡二叉树的旋转
        • 2.3.1、右单旋（R旋转）
        • 2.3.2、左单旋（L旋转）
        • 2.3.3、先右单旋再左单旋（RL旋转）
        • 2.3.4、先左单旋再右单旋（LR旋转）
      • 2.4、平衡二叉树的插入完整代码
    • 3、平衡二叉树的验证
    • 4、平衡二叉树的删除（了解）
    • 5、平衡二叉树的性能
    • 6、平衡二叉树的整体代码

img

平衡二叉树（AVL树）

1、平衡二叉树概念

  • 平衡二叉树（Balanced Binary Tree），也称为AVL树，是一种特殊的二叉搜索树，它的特点是任意节点的左右子树高度差不超过1。这种高度的平衡性确保了在最坏情况下，树的深度大致为 O(log n)，其中 n 是树中节点的数量。

  • 平衡二叉树通常通过在插入或删除节点时进行旋转操作来维持平衡性。这些旋转操作可以分为左旋和右旋，通过重新调整子树的结构，以保持树的平衡。平衡二叉树的平衡性能够保证树的查找、插入和删除操作的时间复杂度为 O(log n)。

  • 由于平衡二叉树的平衡性要求比普通的二叉搜索树更高，因此在插入和删除节点时可能需要执行更多的旋转操作，这会带来一些额外的开销。但是，对于需要频繁地执行查找操作的情况，平衡二叉树能够提供更稳定的性能保证。

  • 平衡二叉树就是为了解决普通的搜索二叉树的插入可能导致单边树的问题（当搜索二叉树退化为单边树，那么搜索和插入性能会大大降低）。普通的搜索二叉树的树深度最好情况下是O(log n)，最坏情况下是O(n)；而平衡二叉树的最好和最坏树高都是O(log n)。

AVL树：一颗空树或是有以下性质的二叉搜索树

  1. 它的左右子树都是AVL树
  2. 它的每个结点的左右子树的高度差（平衡因子）的绝对值不超过1（-1/0/1）

2、平衡二叉树的的实现

2.1、平衡二叉树的结点定义

这里我们将平衡二叉树的结点的值定义为键值对（Key，Value），当然也可以只定义为单值Key。

template<class K, class V>
struct AVLTreeNode {
   typedef AVLTreeNode<K, V> Node;

   Node *_left;
   Node *_right;
   Node *_parent; // 记录当前结点的双亲

   pair<K, V> _kv;
   int _bf; // 平衡因子

   AVLTreeNode(const pair<K, V> &kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
};

2.2、平衡二叉树的插入

由于之前我们已经写过二叉搜索树的插入，并且平衡二叉树是一种特殊的二叉搜索树，因此之前的插入步骤我们可以拿来修改一下。

AVL树的插入可以分为两步：

  1. 按二叉搜索树进行插入

  • 之前的二叉搜索树的插入代码：

    bool Insert(const K &key) {
    Node *cur = _root;
    Node *parent = nullptr;
    if (cur == nullptr) {
        Node *newNode = new Node(key);
        _root = newNode;
        return true;
    }
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
  			cur = new Node(key);
        if (parent->_key < key)
            parent->_right = cur;
        else if (parent->_key > key)
            parent->_left = cur;
        return true;
}

    略微先简单修改一下（将之前的K模型变为KV模型），确定一下初步思路：

    bool Insert(const pair<K, V> &kv) {
    Node *cur = _root;
    Node *parent = nullptr;
    if (cur == nullptr) {
        Node *newNode = new Node(key);
        _root = newNode;
        return true;
    }
    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 == nullptr
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
      parent->_right = cur;
    else if (parent->_kv.first > kv.first)
      parent->_left = cur;
         
    cur->_parent = parent;// 这里是新增的代码，用来记录当前结点的双亲，以便后续进行向上迭代
         
  	// 判断当前插入新结点后会不会导致AVL树变得不平衡
  	// 此处是代码
    return true;
}
  1. 检查插入后会不会导致AVL树不平衡（存在平衡因子绝对值大于1的结点），如果有则调整，没有则继续第一步
  • 我们处理当前结点的平衡因子的值：右树的高度减去左树高度
  • 所以当插入的结点是在parent的左边，则parent的结点的平衡因子–
  • 当插入的结点是在parent的右边，则parent的结点的平衡因子++
  • 新插入的结点的平衡因子是0（无左右子树），这个我们在其构造函数就已经初始化了。

因此我们又加入以下代码

bool Insert(const pair<K, V> &kv) {
    Node *cur = _root;
    Node *parent = nullptr;
    if (cur == nullptr) {
        Node *newNode = new Node(key);
        _root = newNode;
        return true;
    }
    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 == nullptr
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
      parent->_right = cur;
    else if (parent->_kv.first > kv.first)
      parent->_left = cur;

    cur->_parent = parent;// 这里是新增的代码，用来记录当前结点的双亲，以便后续进行向上迭代

  	// 判断当前插入新结点后会不会导致AVL树变得不平衡
  	// parent == nullptr说明已经调整到根了

    while (parent) {
      if (cur == parent->_left)
        parent->_bf--;
      else
        parent->_bf++;

      // 检查parent平衡因子
      // 以下是代码
    }

    return true;
}

检查parent平衡因子：

  1. 插入结点后当前parent平衡因子为0，说明插入之前parent的平衡因子是1或者-1，现在变得非常健康，不要调整。

  2. 插入结点后当前parent平衡因子为1/-1，说明插入之前parent的平衡因子是0，现在变得亚健康，需要往上看爷爷结点是不是平衡因子出现问题了。

    在这里插入图片描述

  3. 插入结点后当前parent平衡因子为2/-2，这时候需要旋转调整，将以parent为根的这棵树调整为AVL树。

因此又插入以下代码：

 bool Insert(const pair<K, V> &kv) {
     Node *cur = _root;
     Node *parent = nullptr;
     if (cur == nullptr) {
         Node *newNode = new Node(key);
         _root = newNode;
         return true;
     }
     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 == nullptr
     cur = new Node(kv);
     if (parent->_kv.first < kv.first)
       parent->_right = cur;
     else if (parent->_kv.first > kv.first)
       parent->_left = cur;

     cur->_parent = parent;// 这里是新增的代码，用来记录当前结点的双亲，以便后续进行向上迭代

   	// 判断当前插入新结点后会不会导致AVL树变得不平衡
   	// parent == nullptr说明已经调整到根了

     while (parent) {
       if (cur == parent->_left)
         parent->_bf--;
       else
         parent->_bf++;

       // 检查parent平衡因子
       
       // 说明插入之前parent的平衡因子是1或者-1，现在变得非常健康，不要调整
           if (parent->_bf == 0) {
               break;
           } else if (parent->_bf == 1 || parent->_bf == -1) {
               // 说明插入之前parent的平衡因子是0,现在变得亚健康，需要往上看爷爷结点是不是平衡因子出现问题了
               cur = cur->_parent;
               parent = parent->_parent;
           } else if (parent->_bf == 2 || parent->_bf == -2) {
               // 旋转调整
             	// 以下是代码 -- 由于比较复杂，我们把代码放到下面新的章节
           }
     }
     return true;
 }

接下来就差旋转的代码了。我们往下看。

2.3、平衡二叉树的旋转

前面说到，当插入一个新结点后当前parent平衡因子为2/-2，这时候需要旋转调整，将以parent为根的这棵树调整为AVL树。

这时候还要分四种情况：

  1. 新结点插入到左子树的左侧。这时候我们需要右单旋。
  2. 新结点插入到右子树的右侧。这时候我们需要左单旋。
  3. 新结点插入到右子树的左侧。这时候我们需要先右单旋再左单旋。
  4. 新结点插入到左子树的右侧。这时候我们需要先单左旋再右单旋。
2.3.1、右单旋（R旋转）

新结点插入到左子树的左侧。这时候我们需要右单旋。看下面抽象图

旋转过程中需要考虑以下几点：

  1. 30节点的右孩子可能存在，也可能不存在
  2. 60可能是根节点，也可能是子树
    • 如果是根节点，旋转完成后，要更新根节点
    • 如果是子树，可能是parent的父节点的左子树，也可能是右子树
  3. 旋转结束后，平衡因子需要调整的就两个结点，一个是起始parent结点，一个是起始parent结点的左结点（subL），其他结点的左右高度差没有变化。这两个结点调整后平衡因子都变为0（看上面抽象图）。
void RotateR(Node *parent) {
      Node *subL = parent->_left;
     Node *subLR = subL->_right;

      parent->_left = subLR;
      subL->_right = parent;
      Node *ppnode = parent->_parent;

      if (subLR)
          subLR->_parent = parent;
      parent->_parent = subL;



      // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
      } else {
          if (parent == ppnode->_left) {
              // subR链接上之前的爷爷结点
              ppnode->_left = subL;
          } else {
              // subR链接上之前的爷爷结点
              ppnode->_right = subL;
          }
          subL->_parent = ppnode;
      }
      parent->_bf = 0;
      subL->_bf = 0;
}
2.3.2、左单旋（L旋转）

新结点插入到右子树的右侧。这时候我们需要左单旋。看下面抽象图

旋转过程中需要考虑以下几点：

  1. 60节点的左孩子可能存在，也可能不存在
  2. 30可能是根节点，也可能是子树
    • 如果是根节点，旋转完成后，要更新根节点
    • 如果是子树，可能是parent的父节点的左子树，也可能是右子树
  3. 旋转结束后，平衡因子需要调整的就两个结点，一个是起始parent结点，一个是起始parent结点的右结点（subR），其他结点的左右高度差没有变化。这两个结点调整后平衡因子都变为0（看上面抽象图）。
void RotateL(Node *parent) {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        parent->_right = subRL;
        subR->_left = parent;
        Node *ppnode = parent->_parent;

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



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subR;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
        parent->_bf = 0;
        subR->_bf = 0;
}
2.3.3、先右单旋再左单旋（RL旋转）

新结点插入到右子树的左侧。这时候我们需要先右单旋再左单旋。看下面抽象图

这里我们看到，parent的右子树的左侧插入新结点后导致parent不平衡，我们的策略是：先对90进行左单旋，再对30进行右单旋。

这里我们需要注意的是：我们可以调用上面已经写好的左单旋和右单旋的函数，但是，左单旋和右单旋的函数只对它们的parent结点及其左结点或者右结点的平衡因子作出了调整，并且都调整为了0。我们观察上述抽象图，我们调整后，会有三个结点的平衡因子需要作出调整（结点30、60、90）！

考虑以下三种情况：

  1. 新结点插入的是60的左子树（上述抽象图）：插入后三个结点的平衡因子为30(bf==-2)，90(bf==-1)，60(bf==-1)，调整后的三个平衡因子为30(bf==0)，90(bf==1)，60(bf==0)。

  2. 新结点插入的是60的右子树（参考上述抽象图，自行画抽象图）：插入后三个结点的平衡因子为30(bf==-2)，90(bf==-1)，60(bf==1)，调整后的三个平衡因子为30(bf==-1)，90(bf==0)，60(bf==0)。

  3. 新结点插入的是一棵原本仅有2个结点的AVL树：插入后的三个结点的平衡因子为30(bf==2)，90(bf==-1)，60(bf==0)，调整后的三个平衡因子为30(bf==0)，90(bf==0)，60(bf==0)。

综合来说，我们看的是60结点（subRL）的平衡因子的值：若插入后调整前60结点（subRL）的平衡因子为0，则该三个结点的平衡因子都变为0；若插入后调整前60结点（subRL）的平衡因子为-1（新结点插入的是60的左子树），则调整后的三个平衡因子为30(bf==0)，90(bf==1)，60(bf==0)；若插入后调整前60结点（subRL）的平衡因子为1（新结点插入的是60的右子树），则调整后的三个平衡因子为30(bf==-1)，90(bf==0)，60(bf==0)。

因此我们得先记录好调整前的subRL结点的平衡因子。

RL旋转代码为：

void RotateRL(Node *parent) {
       // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

       // 会改变平衡因子的结点
       Node *subR = parent->_right;
       Node *subRL = subR->_left;

       //  用来记录没旋转前subRL的结点的bf
       int rlbf = subRL->_bf;

       RotateR(parent->_right);
       RotateL(parent);

       // 讨论旋转后的bf（平衡因子改变的结点）
       if (rlbf == -1) {
           subRL->_bf = 0;
           subR->_bf = 1;
           parent->_bf = 0;
       } else if (rlbf == 1) {
           subRL->_bf = 0;
           subR->_bf = 0;
           parent->_bf = -1;
       } else if (rlbf == 0) { // rlbf == 0
           subRL->_bf = 0;
           subR->_bf = 0;
           parent->_bf = 0;
       } else {
           assert(false);
       }
   }
2.3.4、先左单旋再右单旋（LR旋转）

新结点插入到左子树的右侧。这时候我们需要先单左旋再右单旋。看下面抽象图

这里我们看到，parent的左子树的右侧插入新结点后导致parent不平衡，我们的策略是：先对30进行左单旋，再对90进行右单旋。

这里我们需要注意的是：我们可以调用上面已经写好的左单旋和右单旋的函数，但是，左单旋和右单旋的函数只对它们的parent结点及其左结点或者右结点的平衡因子作出了调整，并且都调整为了0。我们观察上述抽象图，我们调整后，会有三个结点的平衡因子需要作出调整（结点30、60、90）！

考虑以下三种情况：

  1. 新结点插入的是60的左子树（上述抽象图）：插入后三个结点的平衡因子为90(bf==-2)，30(bf==1)，60(bf==-1)，调整后的三个平衡因子为90(bf==1)，30(bf==0)，60(bf==0)。

  2. 新结点插入的是60的右子树（参考上述抽象图，自行画抽象图）：插入后三个结点的平衡因子为90(bf==-2)，30(bf==1)，60(bf==1)，调整后的三个平衡因子为90(bf==0)，30(bf==-1)，60(bf==0)。

  3. 新结点插入的是一棵原本仅有2个结点的AVL树：插入后的三个结点的平衡因子为90(bf==-2)，30(bf==1)，60(bf==0)，调整后的三个平衡因子为90(bf==0)，30(bf==0)，60(bf==0)。

综合来说，我们看的是60结点（subLR）的平衡因子的值：若插入后调整前60结点（subLR）的平衡因子为0，则该三个结点的平衡因子都变为0；若插入后调整前60结点（subLR）的平衡因子为-1（新结点插入的是60的左子树），则调整后的三个平衡因子为90(bf==1)，30(bf==0)，60(bf==0)；若插入后调整前60结点（subLR）的平衡因子为1（新结点插入的是60的右子树），则调整后的三个平衡因子为90(bf==0)，30(bf==-1)，60(bf==0)。

因此我们得先记录好调整前的subLR结点的平衡因子。

LR旋转代码为：

void RotateLR(Node *parent) {
        // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

        // 会改变平衡因子的结点
        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        //  用来记录没旋转前subLR的结点的bf
        int lrbf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        // 讨论旋转后的bf（平衡因子改变的结点）
        if (lrbf == -1) {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        } else if (lrbf == 1) {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        } else if (lrbf == 0) { // lrbf == 0
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        } else {
            assert(false);
        }
}

2.4、平衡二叉树的插入完整代码

需要注意的是：当当前parent进行旋转调整了，说明整棵树已经平衡了（因为每次旋转调整都会把平衡因子有问题的结点都调整好），不再需要调整了。

 bool Insert(const pair<K, V> &kv) {
     Node *cur = _root;
     Node *parent = nullptr;
     if (cur == nullptr) {
         Node *newNode = new Node(key);
         _root = newNode;
         return true;
     }
     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 == nullptr
     cur = new Node(kv);
     if (parent->_kv.first < kv.first)
       parent->_right = cur;
     else if (parent->_kv.first > kv.first)
       parent->_left = cur;

     cur->_parent = parent;// 这里是新增的代码，用来记录当前结点的双亲，以便后续进行向上迭代

   	// 判断当前插入新结点后会不会导致AVL树变得不平衡
   	// parent == nullptr说明已经调整到根了

     while (parent) {
       if (cur == parent->_left)
         parent->_bf--;
       else
         parent->_bf++;

       // 检查parent平衡因子

       // 说明插入之前parent的平衡因子是1或者-1，现在变得非常健康，不要调整
           if (parent->_bf == 0) {
               break;
           } else if (parent->_bf == 1 || parent->_bf == -1) {
               // 说明插入之前parent的平衡因子是0,现在变得亚健康，需要往上看爷爷结点是不是平衡因子出现问题了
               cur = cur->_parent;
               parent = parent->_parent;
           } else if (parent->_bf == 2 || parent->_bf == -2) {
               // 旋转调整
             
             	 // 说明插入之前parent的平衡因子是1或者-1，现在变得不健康了，需要调整
                if (parent->_bf == 2 && parent->_right->_bf == 1) { // parent->_bf == 2 && cur->_bf == 1
                    // 此时需要左单旋
                    RotateL(parent);
                } else if (parent->_bf == -2 && parent->_left->_bf == -1) {
                    // 此时需要右单旋
                    RotateR(parent);
                } else if (parent->_bf == 2 && parent->_right->_bf == -1) {
                    // 此时需要右旋再左旋
                    RotateRL(parent);
                } else {
                    // 此时需要左旋再右旋
                    RotateLR(parent);
                }
                break;// 调整结束，不用再往上调整
           }
     }
     return true;
 }

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

        parent->_right = subRL;
        subR->_left = parent;
        Node *ppnode = parent->_parent;

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



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subR;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
        parent->_bf = 0;
        subR->_bf = 0;
    }

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

        parent->_left = subLR;
        subL->_right = parent;
        Node *ppnode = parent->_parent;

        if (subLR)
            subLR->_parent = parent;
        parent->_parent = subL;



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subL;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
        parent->_bf = 0;
        subL->_bf = 0;
    }

    void RotateRL(Node *parent) {
        // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

        // 会改变平衡因子的结点
        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        //  用来记录没旋转前subRL的结点的bf
        int rlbf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        // 讨论旋转后的bf（平衡因子改变的结点）
        if (rlbf == -1) {
            subRL->_bf = 0;
            subR->_bf = 1;
            parent->_bf = 0;
        } else if (rlbf == 1) {
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = -1;
        } else if (rlbf == 0) { // rlbf == 0
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = 0;
        } else {
            assert(false);
        }
    }

    void RotateLR(Node *parent) {
        // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

        // 会改变平衡因子的结点
        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        //  用来记录没旋转前subLR的结点的bf
        int lrbf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        // 讨论旋转后的bf（平衡因子改变的结点）
        if (lrbf == -1) {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        } else if (lrbf == 1) {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        } else if (lrbf == 0) { // lrbf == 0
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        } else {
            assert(false);
        }

    }

3、平衡二叉树的验证

  1. 验证其为搜索二叉树
    • 中序遍历该AVL树，如果是有序说明是搜索二叉树。
  2. 验证平衡因子
    • 每个结点的高度差绝对值不超过1。
    • 结点的平衡因子是否等于结点的高度差。
bool _IsBalance(Node *root) {
    if (root == nullptr)
      return true;
    int lheight = _Height(root->_left);
    int rheight = _Height(root->_right);
    if (root->_bf != (rheight - lheight) || root->_bf > 1 || root->_bf < -1)
      return false;
    cout << "key:" << root->_kv.first << " " << "bf:" << root->_bf << " " << "rh-lh:" << rheight - lheight
      << endl;
    return _IsBalance(root->_left) && _IsBalance(root->_right);
}

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

4、平衡二叉树的删除（了解）

这里仅贴代码，不过多讲解。

// AVL的删除
       bool Remove(const K &key) {
           return Remove(_root, key);
    }
   
       bool Remove(Node *&root, const K &key) {
           if (!root)
               return false;
   
           if (key < root->_kv.first) {
               bool res = Remove(root->_left, key);
               // 重新计算平衡因子并进行平衡调整
               if (res)
                   updateBalanceFactor(root);
               return res;
        } else if (key > root->_kv.first) {
               bool res = Remove(root->_right, key);
               // 重新计算平衡因子并进行平衡调整
               if (res)
                   updateBalanceFactor(root);
               return res;
           } else {
               if (!root->_left || !root->_right) {
                   Node *temp = root;
                   root = (root->_left) ? root->_left : root->_right;
                   if (root)
                       root->_parent = temp->_parent;
                   delete temp;
               } else {
                   Node *successor = GetSuccessor(root->_right);
                   root->_kv = successor->_kv;
                   Remove(root->_right, successor->_kv.first);
                   // 重新计算平衡因子并进行平衡调整
                   updateBalanceFactor(root);
               }
               return true;
           }
       }
   
       Node *GetSuccessor(Node *node) {
           while (node->_left)
               node = node->_left;
           return node;
       }
   
       void updateBalanceFactor(Node *node) {
           int leftHeight = (node->_left) ? _Height(node->_left) : -1;
           int rightHeight = (node->_right) ? _Height(node->_right) : -1;
           node->_bf = rightHeight - leftHeight;
       }

5、平衡二叉树的性能

平衡二叉树（AVL树）具有良好的性能特征，尤其是在平均情况下。以下是关于平衡二叉树性能的一些重要方面：

  1. 插入、查找、删除操作的时间复杂度： 在平衡二叉树中，这些操作的时间复杂度通常为O(log n)，其中n是树中元素的数量。这是因为树的高度始终保持在O(log n)的水平，这使得这些操作的平均性能非常高效。

  2. 平衡维护的开销： 平衡二叉树的主要开销来自于维护树的平衡。每次插入或删除操作后，都可能需要通过一系列的旋转操作来重新平衡树，这可能增加一定的开销。然而，这种开销通常是可以接受的，因为树的高度始终受到限制，所以平衡维护的成本不会随着树的大小呈指数增长。

  3. 内存使用： 平衡二叉树需要额外的空间来存储平衡因子或其他用于维护平衡的信息。相比于非平衡的二叉搜索树，这可能会增加一些额外的内存消耗。但是，由于树的高度受到控制，所以平衡二叉树通常不会占用过多的内存。

  4. 局部性： 平衡二叉树在插入和删除操作时会进行局部性调整，而不是对整个树进行重构。这意味着在进行一系列插入或删除操作时，只有树的一部分需要被修改，这有助于提高缓存局部性和整体性能。

总的来说，平衡二叉树是一种在插入、查找和删除操作方面性能良好的数据结构。它的时间复杂度保持在对数级别，而且由于其平衡特性，具有较为稳定的性能表现。然而，在某些特定情况下（如频繁的插入和删除操作，这时候AVL树可能需要较多次的旋转），可能会出现比其他数据结构（如哈希表，后面会讲）更高的开销，因此需要根据具体情况进行选择。

6、平衡二叉树的整体代码

  • AVLTree.h文件
#include <utility>
#include <iostream>

using namespace std;

template<class K, class V>
struct AVLTreeNode {
    typedef AVLTreeNode<K, V> Node;

    Node *_left;
    Node *_right;
    Node *_parent;

    pair<K, V> _kv;
    int _bf; // 平衡因子

    AVLTreeNode(const pair<K, V> &kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
};


template<class K, class V>
class AVLTree {
public:
    typedef AVLTreeNode<K, V> Node;

// AVL的删除
       bool Remove(const K &key) {
           return Remove(_root, key);
    }
   
       bool Remove(Node *&root, const K &key) {
           if (!root)
               return false;
   
           if (key < root->_kv.first) {
               bool res = Remove(root->_left, key);
               // 重新计算平衡因子并进行平衡调整
               if (res)
                   updateBalanceFactor(root);
               return res;
        } else if (key > root->_kv.first) {
               bool res = Remove(root->_right, key);
               // 重新计算平衡因子并进行平衡调整
               if (res)
                   updateBalanceFactor(root);
               return res;
           } else {
               if (!root->_left || !root->_right) {
                   Node *temp = root;
                   root = (root->_left) ? root->_left : root->_right;
                   if (root)
                       root->_parent = temp->_parent;
                   delete temp;
               } else {
                   Node *successor = GetSuccessor(root->_right);
                   root->_kv = successor->_kv;
                   Remove(root->_right, successor->_kv.first);
                   // 重新计算平衡因子并进行平衡调整
                   updateBalanceFactor(root);
               }
               return true;
           }
       }
   
       Node *GetSuccessor(Node *node) {
           while (node->_left)
               node = node->_left;
           return node;
       }
   
       void updateBalanceFactor(Node *node) {
           int leftHeight = (node->_left) ? _Height(node->_left) : -1;
           int rightHeight = (node->_right) ? _Height(node->_right) : -1;
           node->_bf = rightHeight - leftHeight;
       }

    // AVL的插入
    bool Insert(const pair<K, V> &kv) {

        if (_root == nullptr) {
            _root = new Node(kv);
            return true;
        }

        Node *cur = _root;
        Node *parent = nullptr;

        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 == nullptr
        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
            parent->_right = cur;
        else if (parent->_kv.first > kv.first)
            parent->_left = cur;

        cur->_parent = parent;

        // 看当前插入的结点会不会导致树不平衡
        // parent == nullptr说明已经调整到根了
        // 平衡因子使用的是右减左的方案
        while (parent) {
            if (cur == parent->_left)
                parent->_bf--;
            else
                parent->_bf++;

            // 说明插入之前parent的平衡因子是1或者-1，现在变得非常健康，不要调整
            if (parent->_bf == 0) {
                break;
            } else if (parent->_bf == 1 || parent->_bf == -1) {
                // 说明插入之前parent的平衡因子是0,现在变得亚健康，需要往上看爷爷结点是不是平衡因子出现问题了
                cur = cur->_parent;
                parent = parent->_parent;
            } else if (parent->_bf == 2 || parent->_bf == -2) {
                // 旋转调整

                // 说明插入之前parent的平衡因子是1或者-1，现在变得不健康了，需要调整
                if (parent->_bf == 2 && parent->_right->_bf == 1) { // parent->_bf == 2 && cur->_bf == 1
                    // 此时需要左单旋
                    RotateL(parent);
                } else if (parent->_bf == -2 && parent->_left->_bf == -1) {
                    // 此时需要右单旋
                    RotateR(parent);
                } else if (parent->_bf == 2 && parent->_right->_bf == -1) {
                    // 此时需要右旋再左旋
                    RotateRL(parent);
                } else {
                    // 此时需要左旋再右旋
                    RotateLR(parent);
                }
                break;// 调整结束，不用再往上调整
            }
        }
        return true;
    }

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

        parent->_right = subRL;
        subR->_left = parent;
        Node *ppnode = parent->_parent;

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



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subR;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
        parent->_bf = 0;
        subR->_bf = 0;
    }

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

        parent->_left = subLR;
        subL->_right = parent;
        Node *ppnode = parent->_parent;

        if (subLR)
            subLR->_parent = parent;
        parent->_parent = subL;



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subL;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
        parent->_bf = 0;
        subL->_bf = 0;
    }

    void RotateRL(Node *parent) {
        // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

        // 会改变平衡因子的结点
        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        //  用来记录没旋转前subRL的结点的bf
        int rlbf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        // 讨论旋转后的bf（平衡因子改变的结点）
        if (rlbf == -1) {
            subRL->_bf = 0;
            subR->_bf = 1;
            parent->_bf = 0;
        } else if (rlbf == 1) {
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = -1;
        } else if (rlbf == 0) { // rlbf == 0
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = 0;
        } else {
            assert(false);
        }
    }

    void RotateLR(Node *parent) {
        // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

        // 会改变平衡因子的结点
        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        //  用来记录没旋转前subLR的结点的bf
        int lrbf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        // 讨论旋转后的bf（平衡因子改变的结点）
        if (lrbf == -1) {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        } else if (lrbf == 1) {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        } else if (lrbf == 0) { // lrbf == 0
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        } else {
            assert(false);
        }

    }


    void InOrder() {
        _InOrder(_root);
    }

    int Height() {
        return _Height(_root);
    }

    bool IsBalance() {
        return _IsBalance(_root);
    }


private:

    bool _IsBalance(Node *root) {
        if (root == nullptr)
            return true;
        int lheight = _Height(root->_left);
        int rheight = _Height(root->_right);
        if (root->_bf != (rheight - lheight) || root->_bf > 1 || root->_bf < -1)
            return false;
        cout << "key:" << root->_kv.first << " " << "bf:" << root->_bf << " " << "rh-lh:" << rheight - lheight
             << endl;
        return _IsBalance(root->_left) && _IsBalance(root->_right);
    }

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

    void _InOrder(Node *root) {
        if (root == nullptr)
            return;
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << "[" << root->_bf << "]" << endl;
        _InOrder(root->_right);

    }


    Node *_root = nullptr;
};

void test_AVLTree1() {
    int a[] = {3, 5, 7, 1, 2, 9, 4, 6, 10, 1, 9, 99, -1, -2, -10, -100, 11, 6};
    AVLTree<int, string> avl;
    for (auto e: a) {
        avl.Insert(make_pair(e, ""));
    }
    avl.InOrder();
    cout << "height：" << avl.Height() << endl;
}

void test_AVLTree2() {
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    AVLTree<int, string> avl;
    for (auto e: a) {
        avl.Insert(make_pair(e, ""));
    }
    avl.InOrder();
    cout << avl.IsBalance() << endl;
}

void test_AVLTree3() {
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    AVLTree<int, string> avl;
    for (auto e: a) {
        avl.Insert(make_pair(e, ""));
    }
    avl.InOrder();
    cout << avl.IsBalance() << endl;
    avl.Remove(11);
    avl.InOrder();
    cout << avl.IsBalance() << endl;
}

OKOK，AVL树就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。

Xpccccc的github主页

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/504491.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

详解JAVA程序调优

详解JAVA程序调优

目录 1.概述 2.命令 2.1.查看JAVA进程 2.2.查看虚拟机状态 2.3.查看线程的情况 3.工具 3.1.jconsole 3.2.jvisualVM 4.实战场景 1.概述 在实际工作中我们难免会遇见程序执行慢、线程死锁等一系列的问题&#xff0c;这时候就需要我们定位具体问题然后来解决问题了。所…
阅读更多...
正弦实时数据库(SinRTDB)的使用(7)-历史统计查询

正弦实时数据库(SinRTDB)的使用(7)-历史统计查询

前文已经将正弦实时数据库的使用进行了介绍&#xff0c;需要了解的可以先看下面的博客&#xff1a; 正弦实时数据库(SinRTDB)的安装 正弦实时数据库(SinRTDB)的使用(1)-使用数据发生器写入数据 正弦实时数据库(SinRTDB)的使用(2)-接入OPC DA的数据 正弦实时数据库(SinRTDB)…
阅读更多...
【Frida】【Android】02_JAVA层HOOK

【Frida】【Android】02_JAVA层HOOK

&#x1f6eb; 系列文章导航 【Frida】【Android】01_手把手教你环境搭建 https://blog.csdn.net/kinghzking/article/details/136986950【Frida】【Android】02_JAVA层HOOK https://blog.csdn.net/kinghzking/article/details/137008446【Frida】【Android】03_RPC https://bl…
阅读更多...
从输入url到页面展示的过程

从输入url到页面展示的过程

唠唠叨&#xff1a;我不想误人子弟&#xff0c;我这篇算是搬运工&#xff0c;加上自己的理解做点总结&#xff0c;所以还请大家科学上网去看这篇&#xff1a;https://aws.amazon.com/cn/blogs/mobile/what-happens-when-you-type-a-url-into-your-browser/ 是这六个步骤&#…
阅读更多...
前端学习＜二＞CSS基础——13-CSS3属性：Flex布局图文详解

前端学习＜二＞CSS基础——13-CSS3属性：Flex布局图文详解

前言 CSS3中的 flex 属性&#xff0c;在布局方面做了非常大的改进&#xff0c;使得我们对多个元素之间的布局排列变得十分灵活&#xff0c;适应性非常强。其强大的伸缩性和自适应性&#xff0c;在网页开中可以发挥极大的作用。 flex 初体验 我们先来看看下面这个最简单的布局…
阅读更多...
笔记: JavaSE day16笔记 - string字符串

笔记: JavaSE day16笔记 - string字符串

第十六天课堂笔记 学习任务 Comparable接口★★★★ 接口 : 功能的封装 > 一组操作规范 一个抽象方法 -> 某一个功能的封装多个抽象方法 -> 一组操作规范 接口与抽象类的区别 1本质不同 接口是功能的封装 , 具有什么功能 > 对象能干什么抽象类是事物本质的抽象 &…
阅读更多...
学习刷题-14

学习刷题-14

3.29 贪心算法 跳跃游戏 II 给定一个非负整数数组&#xff0c;你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 贪心的思路&#xff0c;局部最优&#xff1a;当前可移动距离尽可能多…
阅读更多...
Redis 常见数据结构及命令

Redis 常见数据结构及命令

目录 一.Redis常见的数据结构 二.Redis数据结构对应的命令 1.String类型 2.Hash类型 3.List类型 4.Set类型 5.Sorted Set类型 一.Redis常见的数据结构 Redis支持多种数据结构&#xff0c;包括字符串&#xff08;string&#xff09;、哈希&#xff08;hash&#xff09;、…
阅读更多...
B端：甲方吐槽界面丑，少反驳，气势能得100分，体验永远0分

B端：甲方吐槽界面丑，少反驳，气势能得100分，体验永远0分

2023-10-24 10:20贝格前端工场 甲方吐槽B端系统界面丑陋时&#xff0c;作为设计师或开发者&#xff0c;我们不应该立即反驳或争辩。相反&#xff0c;我们应该以积极的态度倾听甲方的意见&#xff0c;并采取以下措施&#xff1a; 理解甲方需求&#xff1a; 首先要理解甲方对界…
阅读更多...
二维码门楼牌管理应用平台建设：一扫即知，智慧生活新篇章

二维码门楼牌管理应用平台建设：一扫即知，智慧生活新篇章

文章目录 前言一、二维码门楼牌管理的创新之处二、二维码门楼牌管理应用平台的实际应用三、二维码门楼牌管理应用平台的未来展望 前言 随着信息技术的飞速发展&#xff0c;二维码门楼牌管理应用平台应运而生&#xff0c;为城市管理和居民生活带来了极大的便利。只需轻轻一扫&a…
阅读更多...
CentOS7 磁盘相关的命令及磁盘重新调整分配

CentOS7 磁盘相关的命令及磁盘重新调整分配

umount 在CentOS 7中&#xff0c;umount是一个常用的命令&#xff0c;用于卸载文件系统。以下是一些常用的umount命令&#xff1a; 卸载指定的文件系统&#xff1a; umount /dev/sdXN 其中&#xff0c;/dev/sdXN是你想要卸载的分区。例如&#xff0c;/dev/sda1。 卸载并…
阅读更多...
传参的指针，你的值到底变了没？！（有关函数形参修改的另类案例）

传参的指针，你的值到底变了没？！（有关函数形参修改的另类案例）

我们都知道&#xff0c;想要在函数中修改某个变量的值&#xff0c;传变量本身是没有用的。原因在于不同的函数在不同的空间上&#xff0c;函数的生命周期随着函数的调用而结束&#xff0c;因此在函数内部进行的值操作是不会对函数外的变量产生影响的。所以在函数里面想要修改变…
阅读更多...
今日早报 每日精选15条新闻简报 每天一分钟 知晓天下事 3月31日，星期日

今日早报 每日精选15条新闻简报 每天一分钟 知晓天下事 3月31日，星期日

每天一分钟&#xff0c;知晓天下事&#xff01; 2024年3月31日 星期日 农历二月廿二 1、 医保局&#xff1a;北京、广西、内蒙古、甘肃已将辅助生殖纳入医保报销。 2、 百日咳卷土重来&#xff0c;今年已有13人死亡&#xff0c;医生提醒&#xff1a;久咳不愈要警惕。 3、 上海…
阅读更多...
亚马逊云科技—云从业者认证考试限时 50% 折扣优惠 限量提供, 先到先得！

亚马逊云科技—云从业者认证考试限时 50% 折扣优惠 限量提供, 先到先得！

亚马逊云科技云从业者认证&#xff08;AWS Certified Cloud Practitioner&#xff09;作为全球热门的云基础认证, 对于寻求基础云知识的开发者、专业人士、学生, 以及没有技术背景的职场人士来说, 都是进阶亚马逊云认证之旅的良好起点并助您进一步提升职场竞争力&#xff01; 与…
阅读更多...
Spring IoCDI(3)

Spring IoCDI(3)

DI详解 接下来学习一下依赖注入DI的细节. 依赖注入是一个过程, 是指IoC容器在创建Bean时, 去提供运行时所依赖的资源, 而资源指的就是对象. 在之前的案例中, 使用了Autowired这个注解, 完成了依赖注入这个操作. 简单来说, 就是把对象取出来放到某个类的属性中. 在一些文章中…
阅读更多...
上市公司-劳动投资效率数据集-Abresid 含原始数据及处理代码（2020-2022年）

上市公司-劳动投资效率数据集-Abresid 含原始数据及处理代码（2020-2022年）

01、数据简介 劳动投资效率是指企业在进行劳动力投资时所获得的效益程度。简单来说&#xff0c;它衡量了企业对于人力资源的投入与产出之间的比率&#xff0c;反映了企业在人力资源管理方面的效果和效率。 Abresid是劳动投资效率的测度指标&#xff0c;它来源于某个回归模型的…
阅读更多...
Vmware下减小Ubuntu系统占用系统盘大小

Vmware下减小Ubuntu系统占用系统盘大小

1、虚拟机设置下占用空间 如图&#xff0c;给虚拟机分配了120GB&#xff0c;已经占用116.9GB&#xff0c;开机会提示空间不足。 2、实际使用空间 ubuntu系统下使用“df -h”命令查看实际使用空间大小50GB左右 造成这个原因是&#xff0c;虚拟机的bug&#xff1a;在虚拟机的ub…
阅读更多...
【PHP编程使用UI框架】——GET和POST的请求方法

【PHP编程使用UI框架】——GET和POST的请求方法

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…
阅读更多...
详解 Java多线程带来的的风险-线程安全

详解 Java多线程带来的的风险-线程安全

目录 一、什么是线程安全&#xff1f; 二、线程不安全的原因 1、线程调度是随机的 2、修改共享数据&#xff1a;多个线程修改同⼀个变量 3、原⼦性 ​编辑 &#xff08;1&#xff09;什么是原⼦性 &#xff08;2&#xff09;⼀条 java 语句不⼀定是原⼦的&#xff0c;也不⼀定…
阅读更多...
【转移表】

【转移表】

文章目录 一、函数指针数组1.什么事函数指针数组2.函数指针数组如何定义 二、转移表结束语 一、函数指针数组 1.什么事函数指针数组 在我们学习函数指针数组前&#xff0c;大家可以一起回顾一下我们以前学习的指针和数组。 数组指针 数组指针是指指向数组的指针。 int arr…
阅读更多...
最新文章

Copyright @ 2022~2023