2.AVL树节点定义

3.AVL树的插入（重点）

3.1AVL树

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步:

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

平衡因子 = 右子树高度 - 左子树高度

• 插入的新结点newNode在当前结点cur的左子树，平衡因子--
• 插入的新结点newNode在当前结点cur的右子树，平衡因子++
• 是否要往上更新祖先的平衡因子，要看cur的parent结点所在高度是否发生变化
  1. 插入新节点之前，parent的平衡因子为0，插入新节点后，parent的平衡因子变为1/-1，说明parent所在子树的高度改变了，需要往上更新
  2. 插入新节点之前，parent的平衡因子为1/-1，插入新节点后，parent的平衡因子变为0，说明parent所在子树的高度没有改变，不需要往上更新
  3. 插入新节点之前，parent的平衡因子为1/-1，插入新节点后，parent的平衡因子变为2/-2，需要进行旋转处理

3.2AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构使之平衡化。达到旋转的条件是该结点平衡因子变为2/-2就要进行旋转。根据节点插入位置的不同，AVL树的旋转分为四种:

        1.新节点插入在较高左子树的左侧，解决操作：右单旋

当h越来越大，a,b,c这三颗子树的情况越多，组合起来越大，这里只是进行简单分析了一下

上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层， 即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

1.  30节点的右孩子可能存在，也可能不存在
2.  60可能是根节点，也可能是子树如果是根节点，旋转完成后，要更新根节点。如果是子树，可能是某个节点的左子树，也可能是右子树

把subL往上提，parent作为subL的右孩子，parent的左孩子变为subL的右孩子，修改完后调节平衡因子（subLR可能为空）

// 右单旋
void _RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR != nullptr){subLR->_parent = parent;}Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr) // parent为根结点{_root = subL;subL->_parent = nullptr;}else // parent为其中的一颗子树{// 判断该子树是parentParent的左还是右if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}// 调节平衡因子parent->_bf = 0;subL->_bf = 0;
}

        2.新节点插入较高右子树的右侧，解决操作：左单旋

// 左单旋
void _RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL != nullptr){subRL->_parent = parent;}Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr) // parent为根结点{_root = subR;subR->_parent = nullptr;}else // parent为其中的一颗子树{// 判断该子树是parentParent的左还是右if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}// 调节平衡因子parent->_bf = 0;subR->_bf = 0;
}

        3. 新节点插入较高左子树的右侧，解决操作：先左单旋再右单旋

void _RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;// subL位置左单旋_RotateL(parent->_left);// parent位置再右单旋_RotateR(parent);// 调整平衡因子if (bf == 0) // subLR为插入的结点（图中abcd子树都为空，原树只有parent和curL这两个节点）{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}

        4. 新节点插入较高右子树的左侧，解决方案：先右单旋再左单旋

void _RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;_RotateR(parent->_right);_RotateL(parent);// 调整平衡因子if (bf == 0) // subRL为插入的结点{parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}

总结：

假如以Parent为根的子树不平衡，即Parent的平衡因子为2或者-2，分以下情况考虑：

1.Parent的平衡因子为2，说明Parent的右子树高，设Parent的右子树为SubR，当SubR的平衡因子为1时，执行左单旋，当SubR的平衡因子为-1时，执行右左双旋

2. Parent的平衡因子为-2，说明Parent的左子树高，设Parent的左子树为SubL，当SubL的平衡因子为-1是，执行右单旋，当pSubL的平衡因子为1时，执行左右双旋

旋转完成后，原子树的高度和旋转完的子树高度一样，所以不需要再向上更新。

3.3AVL树插入代码

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 (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}// 判断平衡因子if (parent->_bf == 0) // 插入在矮的那边{break;}else if (parent->_bf == 1 || parent->_bf == -1) {// 往上更新cur = parent;parent = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 旋转if (parent->_bf == 2 && cur->_bf == 1) // 左单旋{_RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋{_RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋{_RotateRL(parent);}else // 左右双旋{_RotateLR(parent);}// 旋转完了不需要往上更新平衡因子break;}else{// 前面出错了assert(false);}}return true;
}

4.AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树，如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树每个节点子树高度差的绝对值不超过1

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;// 如果计算出的平衡因子与root的平衡因子不相等，或者// root平衡因子的绝对值超过1，则一定不是AVL树if (diff != root->_bf || (diff > 1 || diff < -1))return false;// root的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root -> _right);
}

测试用例

int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16 ,14 };

void testAVLTree()
{bit::AVLTree<int, int> avl;//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16 ,14 };for (auto e : a){avl.insert({ e,e });}avl.InOrder();std::cout << avl.IsBalanceTree() << endl;
}

5.AVL树的删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

后面我会写一篇AVL树的删除，再把链接放进来。删除的复杂度要比插入复杂，考虑条件也多。

6.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

7.整体代码（挑选重点看就行）

AVL/AVL.h · wrf/C++test_cpp - 码云 - 开源中国