C++ AVL旋转操作

---

---

前言

  本章主要介绍AVL树的旋转操作，包括单旋（左旋与右旋）和双旋（左右旋，右左旋）。

---

一、单旋

（1）左旋

  左旋以下图举例，5的右子树的高度为h+2,左子树高度为h,5的平衡因子为2（右子树高度-左子树的高度），因此需要左旋。左旋操作如下所示：
  ①2成为5的父亲，5成为2的左子树
  ②2的左子树放在5的右子树
  ③5的父亲指向2
注意以下事项：
  ①判断5是根还是某个子树的根节点
  ②若5是某个子树的根节点，则要判断5的父亲是右边指向5还是左边指向5
  ③注意平衡因子的更新

  下面是AVL树左旋的代码：

		void RotateRL(Node* parent) {Node* subR = parent->right;Node* subRL = subR->left;int bf = subRL->_bf;//在旋转之前获取，旋转之后获取逻辑不对RotateR(parent->right);RotateL(parent);if (bf == 0) {parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1) {parent->_bf = -1;subR->_bf = subRL->_bf;}else if (bf == -1) {subR->_bf = 1;parent->_bf = subRL->_bf = 0;}else {assert(false);}}

（2）右旋

  右旋以下图举例，5的右子树的高度为h,左子树高度为h+2,5的平衡因子为-2（右子树高度-左子树的高度），因此需要右旋。左旋操作如下所示：
  ①2成为5的父亲，5成为2的右子树
  ②2的右子树放在5的左子树
  ③5的父亲指向2
注意以下事项：
  ①判断5是根还是某个子树的根节点
  ②若5是某个子树的根节点，则要判断5的父亲是右边指向5还是左边指向5

  下面是AVL树右旋的代码：

		void RotateR(Node* parent) {Node* subL = parent->left;Node* subLR = subL->right;Node* parentparent = parent->parent;parent->left=subLR;if(subLR!=nullptr) subLR->parent = parent;subL->right = parent;parent->parent = subL;subL->parent = parentparent;if (parentparent == nullptr) _root = subL;else {if (parentparent->left == parent) parentparent->left = subL;else parentparent->right = subL;}parent->_bf = subL->_bf = 0;}

二、双旋

（1）左右旋

1.左右旋情况一

下图为左右旋的一种情况，具体操作如下：
  ①将节点2进行左旋
  ②再将节点5进行右旋

2.左右旋情况二

  下图为左右旋的另一种情况，这里的操作可简单描述为：将3的左边给2的右边，将3的右边给5的左边，3成为子树根节点，左边指向2，右边指向5，具体操作如下：
  ①将节点2进行左旋
  ②再将节点5进行右旋
注意事项：
  在a侧插入和b侧插入新元素时候，各节点的平衡因子变化会有所不用
  下面为左右旋的代码。

		void RotateLR(Node* parent) {Node* subL = parent->left;Node* subLR = subL->right;int bf = subLR->_bf;//在旋转之前获取，旋转之后获取逻辑不对RotateL(parent->left);RotateR(parent);if (bf == 0) {parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == 1) {subL->_bf = -1;parent->_bf = subLR->_bf = 0;}else if (bf == -1) {parent->_bf = 1;subL->_bf = subLR->_bf=0;}else {assert(false);}}

（2）右左旋

1.右左旋情况一

下图为左右旋的一种情况，具体操作如下：
  ①将节点10进行左旋
  ②再将节点5进行右旋

2.右左旋情况二

下图为左右旋的另一种情况，这里的操作可简单描述为：将4的左边给3的右边，将4的右边给7的左边，4成为子树根节点，左边指向3，右边指向7，具体操作如下：
  ①将节点7进行右旋
  ②再将节点3进行左旋
注意事项：
  在a侧插入和b侧插入新元素时候，各节点的平衡因子变化会有所不用

  下面为右左旋的代码。

		void RotateRL(Node* parent) {Node* subR = parent->right;Node* subRL = subR->left;int bf = subRL->_bf;//在旋转之前获取，旋转之后获取逻辑不对RotateR(parent->right);RotateL(parent);if (bf == 0) {parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1) {parent->_bf = -1;subR->_bf = subRL->_bf;}else if (bf == -1) {subR->_bf = 1;parent->_bf = subRL->_bf = 0;}else {assert(false);}}

总结

  本文主要讲用图例和代码呈现的方式详细列举了AVL树旋转的各种情况，希望对各位读者有所帮助。