平衡二叉树（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;
  }
  

2. 检查插入后会不会导致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主页