平衡二叉树（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 == nullptrcur = 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 == nullptrcur = 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--;elseparent->_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 == nullptrcur = 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--;elseparent->_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的结点的bfint 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 == 0subRL->_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的结点的bfint 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 == 0subLR->_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 == nullptrcur = 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--;elseparent->_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的结点的bfint 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 == 0subRL->_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的结点的bfint 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 == 0subLR->_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 == nullptrcur = 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--;elseparent->_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的结点的bfint 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 == 0subRL->_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的结点的bfint 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 == 0subLR->_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主页

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

leetcode 周赛 391场

leetcode 周赛 391场

2. 换水问题 给你两个整数 numBottles 和 numExchange 。 numBottles 代表你最初拥有的满水瓶数量。在一次操作中&#xff0c;你可以执行以下操作之一&#xff1a; 喝掉任意数量的满水瓶&#xff0c;使它们变成空水瓶。用 numExchange 个空水瓶交换一个满水瓶。然后&#xf…
阅读更多...
Django安装及第一个项目

Django安装及第一个项目

1、安装python C:\Users\leell>py --version Python 3.10.6 可以看出我的环境python的版本3.10.6&#xff0c;比较新 2、 Python 虚拟环境创建 2.1 官网教程 目前&#xff0c;有两种常用工具可用于创建 Python 虚拟环境&#xff1a; venv 在 Python 3.3 及更高版本中默…
阅读更多...
Vue系列——数据对象

Vue系列——数据对象

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>el:挂载点</title> </head> <body&g…
阅读更多...
C++11入门手册第二节，学完直接上手Qt(共两节)

C++11入门手册第二节，学完直接上手Qt(共两节)

C++多线程 #include <thread>：C++多线程库 #include <mutex>：C++互斥量库 #include <future>：C++异步库 多线程介绍 线程的创建 void entry_1() { }以普通函数作为线程入口函数：void entry_2(int val) { }​std::thread my_thread_1(entry_1);std::thr…
阅读更多...
【c++】类和对象（六）深入了解隐式类型转换

【c++】类和对象（六）深入了解隐式类型转换

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好&#xff0c;本篇文章我们来到初始化列表&#xff0c;隐式类型转换以及explicit的内容 目录 1.初始化列表1.1构造函数体赋值1.2初始化列表1.2.1隐式类型转换与复制初始化 1.3e…
阅读更多...
C语言-写一个宏，可以将一个整数的二进制位的奇数位和偶数位交换。

C语言-写一个宏，可以将一个整数的二进制位的奇数位和偶数位交换。

0xaaaaaaaa...等是什么&#xff1f;-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/137179252 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #define SWAP(num) (((num & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << …
阅读更多...
WIFI驱动移植实验：配置 Linux 内核

WIFI驱动移植实验：配置 Linux 内核

一. 简介 前面文章删除了Linux内核源码&#xff08;NXP官方的kernel内核源码&#xff09;自带的 WIFI驱动。 WIFI驱动移植实验&#xff1a;删除Linux内核自带的 RTL8192CU 驱动-CSDN博客 将正点原子提供的 rtl8188EUS驱动源码添加到 kernel内核源码中。文章如下&#xff1a…
阅读更多...
JavaScript基础语法–变量

JavaScript基础语法–变量

文章目录 认识JavaScript变量程序中变量的数据&#xff08;记录&#xff09;–变量变量的命名格式在Java script中变量定义包含两部分1. 变量声明&#xff08;高级JS引擎接下来定义一个变量&#xff09;2. 其他的写法 变量命名的规范&#xff08;遵守&#xff09;变量的练习a. …
阅读更多...
C语言每日一题

C语言每日一题

1.题目 二.分析 本题有两点需要注意的&#xff1a; do-while循环 &#xff1a;在判断while条件前先执行一次do循环static变量 &#xff1a;程序再次调用时static变量的值不会重新初始化&#xff0c;而是在上一次退出时的基础上继续执行。for( i 1; i < 3; i )将调用两次…
阅读更多...
江协STM32:点亮第一个LED灯和流水灯

江协STM32:点亮第一个LED灯和流水灯

很多单片机都是高电平弱驱动&#xff0c;低电平强驱动&#xff0c;所以这里是低电平有效 点亮一个LED灯 操作STM32的GPIO需要三个操作&#xff1a; 第一个使用RCC开启GPIO的时钟 第二步使用GPIO_Init函数初始化GPIO 第三步使用输出或输入函数控制GPIO 1.使用RCC开启GPIO的时…
阅读更多...
C++ | leetcode C++题解之第1题两数之和

C++ | leetcode C++题解之第1题两数之和

题目&#xff1a; C 题解&#xff1a; class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashtable;for (int i 0; i < nums.size(); i) {auto it hashtable.find(target - nums[i]);if (it …
阅读更多...
【微服务】Nacos（配置中心）

【微服务】Nacos（配置中心）

文章目录 1.AP和CP1.基本介绍2.说明 2.Nacos配置中心实例1.架构图2.在Nacos Server加入配置1.配置列表&#xff0c;加号2.加入配置3.点击发布&#xff0c;然后返回4.还可以编辑 3. 创建 Nacos 配置客户端模块获取配置中心信息1.创建子模块 e-commerce-nacos-config-client50002…
阅读更多...
flutter生成二维码并截图保存到图库

flutter生成二维码并截图保存到图库

引入库&#xff1a;flutter_screenutil、image_gallery_saver、qr_flutter弹窗布局 import dart:async; import dart:typed_data; import package/generated/l10n.dart; import package:jade/configs/PathConfig.dart; import package:jade/utils/ImageWaterMarkUtil.dart; im…
阅读更多...
Linux中常用命令(文件、目录和文件压缩)及功能示例

Linux中常用命令(文件、目录和文件压缩)及功能示例

一、Linux关于文件与目录的常用命令及其功能示例 命令: ls 全名: List (列表) 常用选项: -l: 详细列表格式&#xff0c;显示详细信息。-a: 显示所有文件&#xff0c;包括隐藏文件。 功能: 列出目录内容。 示例: ls -la /home 此命令以详细格式列出/home目录中的所有文件&#x…
阅读更多...
杂货铺 | 使用 Github Pages 和 Hexo 搭建自己的独立博客

杂货铺 | 使用 Github Pages 和 Hexo 搭建自己的独立博客

文章目录 &#x1f4da;Step1&#xff1a;安装Node.js和Git&#x1f4da;Step2&#xff1a;安装并初始化配置Hexo&#x1f4da;Step3&#xff1a;本地查看效果&#x1f4da;Step4&#xff1a;将博客部署到Github Pages上&#x1f407;创建项目代码库&#x1f407;配置SSH密钥&a…
阅读更多...
【Postman如何进行接口测试简单详细操作实例】

【Postman如何进行接口测试简单详细操作实例】

1、下载Postman postman下载地址&#xff1a;Download Postman | Get Started for Free 2、安装Postman (1)双击下载好的postman-setup.exe文件&#xff0c;进行安装postman工具 (2)安装完成后&#xff0c;在桌面找到并打开postman软件&#xff0c;输入邮箱和密码进行登录&a…
阅读更多...
基于SSM大学生健康管理系统的设计与实现

基于SSM大学生健康管理系统的设计与实现

基于SSM大学生健康管理系统的设计与实现 获取源码——》哔站搜&#xff1a;计算机专业毕设大全 获取源码——》哔站搜&#xff1a;计算机专业毕设大全 源码获取——》可以私信
阅读更多...
IntelliJ IDEA 2023 for Mac 好用的Java开发工具

IntelliJ IDEA 2023 for Mac 好用的Java开发工具

IntelliJ IDEA 2023是一款由JetBrains开发的强大的集成开发环境&#xff08;IDE&#xff09;软件&#xff0c;适用于多个编程语言。它旨在提高开发人员的生产力和代码质量&#xff0c;具有以下多种特色功能&#xff1a; 软件下载&#xff1a;IntelliJ IDEA 2023 v2023.3.6中文激…
阅读更多...
SQLite版本3中的文件锁定和并发(七）

SQLite版本3中的文件锁定和并发(七）

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;自己编译SQLite或将SQLite移植到新的操作系统&#xff08;六&#xff09; 下一篇&#xff1a;SQLite—系列文章目录 正文&#xff1a; 1.0 SQLite 版本 3 中的文件锁定和并发 SQLite 版本 3.0.0 引入了新的锁…
阅读更多...
RIP环境下的MGRE 综合实验

RIP环境下的MGRE 综合实验

实验题目及要求&#xff1a; 1.R5为ISP&#xff0c;只能进行IP地址配置&#xff0c;其所有地址均配为公有IP地址 2.R1和R5间使用PPP的PAP认证&#xff0c;R5为主认证方; R2于R5之间使用PPP的chap认证&#xff0c;R5为主认证方&#xff1b; R3于R5之间使用HDLC封装。 3.R1/…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023