一、前言
《二叉查找树全面详细介绍》中讲解了二叉树操作：搜索（查找）、遍历、插入、删除。《二叉树遍历详解（递归遍历、非递归栈遍历，Morris遍历）》详细讲解了二叉树遍历的几种方法。《二叉树平衡（有序数组创建）》和《二叉树平衡（DSW算法）》介绍了两种构建平衡二叉树的方法（完全平衡二叉树）。
前两篇讨论的算法可以从全局重新平衡树；每个节点都可能参与树的重新平衡：或者从节点中移动数据，或者重新设置指针的值。但是，当插入或删除元素时，将只影响树的一部分，此时树的重新平衡可以只在局部执行。Adel'son-Vel'ski和Landis提出了一种经典方法,用这种方法修改的树就以他们的名字来命名： AVL树。
AVL树(最初叫做可容许树)要求每个节点左右子树的高度差最大为1。
二、AVL树实现
平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
2.1 平衡因子
某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。如果某一结点的平衡因子绝对值大于1则说明此树不是平衡二叉树，需要进行调整。为了方便计算每一结点的平衡因子我们可以为每个节点赋予height这一属性，表示此节点的高度。
2.2 AVL节点定义
template<class T>
class AvlNode
{
public:
T m_el;
AvlNode<T>* m_left;
AvlNode<T>* m_right;
int m_height;
AvlNode(const T& e, AvlNode<T>* l = nullptr, AvlNode<T>* r = nullptr, int h = 0)
{
m_el = e;
m_left = l;
m_right = r;
m_height = h;
}
};
2.3 插入平衡调整
在插入一个元素之后，当树的平衡被破坏就需要对树结构进行调整。树结构调整我们可以对树进行左旋转或者右旋转。当插入一个节点之后破坏了树的平衡有四种情况：
1）待插入元素3，将元素插入到节点右节点的右边（右右插入），如下图，我们只需要对其进行一次左旋转即可。回顾一下《二叉树平衡（DSW算法）》实现平衡的过程，先将一颗树转换成只有右节点的树，然后对其多次左旋转就可以达到平衡二叉树的要求。
2）待插入元素1，将元素插入到节点左节点的左边（左左插入），如下图，我们只需要对其进行一次右旋转即可。延伸思考一下，《二叉树平衡（DSW算法）》是不是可以有两种实现方法，一：先转换为只有右节点的树，然后对其左旋转；二：先转换为只有左节点的树，然后对其右旋转。
3）待插入元素2，将元素插入到节点右节点的左边（右左插入），如下图，需要先进行一次右旋转，再进行一次左旋转。
4）待插入元素2，将元素插入到节点左节点的右边（左右插入），如下图，需要先进行一次左旋转，再进行一次右旋转。
三、总结
在构建平衡二叉树的过程中，当插入一个节点之后，新插入的节点破坏树l平衡此时需要对树进行旋转。旋转调整树的结构是从插入节点往上进行判断（用到的是递归）树的高度，如果高度相差为2，说明该节点以下的树（包含该节点）不是平衡二叉树需要进行调整，需要用上面四种调整中的一种，通过树插入的方向进行确定。
四、编码实现
//==========================================================================
/**
* @file : AvlTree.h
* @blogs :
* @author : niebingyu
* @title : AVL树
* @purpose : 构建AVL树
*/
//==========================================================================
#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template<class T>
class AvlNode
{
public:
T m_el;
AvlNode<T>* m_left;
AvlNode<T>* m_right;
int m_height;
AvlNode(const T& e, AvlNode<T>* l = nullptr, AvlNode<T>* r = nullptr, int h = 0)
{
m_el = e;
m_left = l;
m_right = r;
m_height = h;
}
};
template<typename T>
class AvlTree: public BSTNode<T>
{
public:
AvlTree() { m_root = NULL; }
~AvlTree() { clear(); };
void clear()
{
clear(m_root);
m_root = nullptr;
}
// 插入值为el的结点
void insert(const T& el) { insert(el, m_root); };
// 前序遍历
void preorder() { preorder(m_root); };
// 中序遍历
void inorder() { inorder(m_root); };
protected:
void clear(AvlNode<T>* t);
// 前序遍历
void preorder(AvlNode<T>*);
// 中序遍历
void inorder(AvlNode<T>*);
// 获得当前结点t的高度
int height(AvlNode<T>*) const;
// 在t处。插入值为x的结点
void insert(const T&, AvlNode<T>*&);
// 将当前结点进行右单旋转，用于左左插入
void rotateRight(AvlNode<T>*&);
// 将当前结点进行左单旋转，用于右右插入
void rotateLeft(AvlNode<T>*&);
// 将当前结点的左节点进行左旋转，再对当前节点进行右旋转，用于左右插入
void rotateLeftRight(AvlNode<T>*&);
// 将当前结点的右节点进行右旋转，再对当前节点进行左旋转，用于右左插入
void rotateRightLeft(AvlNode<T>*&);
// 访问节点
virtual void visit(AvlNode<T>* p) { cout << p->m_el << ' '; }
private:
AvlNode<T>* m_root;
};
//在结点t的后面插入值为x的结点
template<typename T>
void AvlTree<T>::insert(const T& el, AvlNode<T>*& t)
{
if (t == NULL) //当前结点为空
t = new AvlNode<T>(el, NULL, NULL);
else if (el < t->m_el)
{
insert(el, t->m_left);
if (height(t->m_left) - height(t->m_right) == 2)
{
if (el < t->m_left->m_el) //右旋转，左左插入
rotateRight(t);
else
rotateLeftRight(t); //先左旋转再右旋转，左右插入
}
}
else if (el > t->m_el)
{
insert(el, t->m_right);
if (height(t->m_right) - height(t->m_left) == 2)
{
if (el > t->m_right->m_el) //左旋转，右右插入
rotateLeft(t);
else
rotateRightLeft(t); //先右旋转再左旋转，右左插入
}
}
//假设x的值和当前结点的值同样，则忽略。也能够向之前二叉查找树一样给每一个结点再加一个num成员变量。
t->m_height = max(height(t->m_left), height(t->m_right)) + 1;//更新结点t的高度
}
// 将当前结点进行右单旋转，用于左左插入
template<typename T>
void AvlTree<T>::rotateRight(AvlNode<T>*& k2)
{
AvlNode<T>* k1 = k2->m_left;
k2->m_left = k1->m_right;
k1->m_right = k2;
k2->m_height = max(height(k2->m_left), height(k2->m_right)) + 1;
k1->m_height = max(height(k1->m_left), k2->m_height) + 1;
k2 = k1;
}
// 将当前结点进行左单旋转，用于右右插入
template<typename T>
void AvlTree<T>::rotateLeft(AvlNode<T>*& k1)
{
AvlNode<T>* k2 = k1->m_right;
k1->m_right = k2->m_left;
k2->m_left = k1;
k1->m_height = max(height(k1->m_left), height(k1->m_right)) + 1;
k2->m_height = max(height(k2->m_right), k1->m_height) + 1;
k1 = k2;
}
// 将当前结点的左节点进行左旋转，再对当前节点进行右旋转，用于左右插入
template<typename T>
void AvlTree<T>::rotateLeftRight(AvlNode<T>*& k3)
{
rotateLeft(k3->m_left);
rotateRight(k3);
}
// 将当前结点的右节点进行右旋转，再对当前节点进行左旋转，用于右左插入
template<typename T>
void AvlTree<T>::rotateRightLeft(AvlNode<T>*& k1)
{
rotateRight(k1->m_right);
rotateLeft(k1);
}
// 获得当前结点t的高度
template<typename T>
int AvlTree<T>::height(AvlNode<T>* t) const
{
return (t == NULL) ? -1 : t->m_height;
}
// 前序遍历
template<typename T>
void AvlTree<T>::preorder(AvlNode<T>* t)
{
if (t != NULL)
{
visit(t);
preorder(t->m_right);
preorder(t->m_left);
}
}
// 中序遍历
template<typename T>
void AvlTree<T>::inorder(AvlNode<T>* t)
{
if (t != NULL)
{
inorder(t->m_left);
visit(t);
inorder(t->m_right);
}
}
// 释放t指针指向的结点
template<typename T>
void AvlTree<T>::clear(AvlNode<T>* t)
{
if (t != NULL)
{
clear(t->m_left);
clear(t->m_right);
delete t;
}
}
测试用例：
//==========================================================================
/**
* @file : AvlTreeTest.h
* @blogs :
* @author : niebingyu
* @title : 测试AVL平衡二叉树
* @purpose : 测试AVL平衡二叉树
*
*/
//==========================================================================
#pragma once
#include "AvlTree.h"
using namespace std;
#define NAMESPACE_AVLTREETEST namespace NAME_AVLTREETEST {
#define NAMESPACE_AVLTREETESTEND }
NAMESPACE_AVLTREETEST
void test(const char* testName, vector<int> data)
{
cout << "测试用例：" << testName << ", 构造AVL树" << endl;
cout << "插入数据：";
for (int i = 0; i < (int)data.size(); ++i)
cout << data[i] << " ";
cout << endl;
AvlTree<int> tree;
for (int i = 0; i < (int)data.size(); ++i)
tree.insert(data[i]);
cout << "前序遍历：";
tree.preorder();
cout << "\n中序遍历：";
tree.inorder();
cout << endl;
cout << endl;
}
// 测试用例
void Test1()
{
vector<int> data = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
test("Test1", data);
}
void Test2()
{
vector<int> data = { 10,20,15 };
test("Test1", data);
}
NAMESPACE_AVLTREETESTEND
void AvlTreeTest_Test()
{
NAME_AVLTREETEST::Test1();
NAME_AVLTREETEST::Test2();
}
执行结果：
