浅析AVL树算法

AVL树简介

   AVL树是一种高度平衡的二叉树，在定义树的每个结点的同时，给树的每一个结点增加成员 平衡因子bf  ，定义平衡因子为右子树的高度减去左子树的高度。AVL树要求所有节点左右子树的高度差不超过2，即bf的绝对值小于2。

   当我们插入新的结点之后，平衡树的平衡状态将会被破坏，因此我们需要采用相应的调整算法使得树重新回归平衡。

预备知识

    前文说当插入新的结点时，树的结构可能会发生破坏，因此我们设定了一套调整算法。调整可分为两类：一类是结构调整，即改变树中结点的连接关系，另一类是平衡因子的调整，使平衡因子重新满足AVL树的要求。调整过程包含四个基本的操作，左旋转，右旋转，右左双旋，左右双旋。   

平衡树的旋转，目的只有一个，降低树的高度，高度降低之后，就大大简化了在树中查找结点时间复杂度。

左旋：   

10、20为树的三个结点。当在20的右子树插入一个结点之后，如图。当Parent结点的平衡因子为2，cur结点的平衡因子为1时进行左旋。

将 parent 的 right 指针，指向cur 的left结点；同时cur的left 指针，指向parent 结点。cur 结点继承了原来parent结点在该树（子树）中的根节点的位置，如果原来的parent结点还有父结点，cur需要和上一层的结点保持连接关系。（这里我们允许cur的左子树为NULL）

可以看到，旋转之后，原来的parent结点和cur结点的平衡因子都变为0 。

//左旋转代码实现：
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;	
		
		parent->_right = subRL;
		if (subRL != NULL)
			subRL->_parent = parent;


        Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (ppNode == NULL)
		{
			_root = subR;
			subR->_parent = NULL;
		}
		else
		{
			if (parent == ppNode->_left)
				ppNode->_left = subR;
			if (parent == ppNode->_right)
				ppNode->_right = subR;

			subR->_parent = ppNode;
		}

		parent->_bf = 0;
		subR->_bf = 0;
	}

右旋：

    右旋和左旋的原理类似，和左旋成镜像关系。当parent结点的平衡因子变为 -2，cur结点的平衡因子变为-1 时，进行右旋。

   将 parent 结点的左指针，指向cur结点的右子树，cur结点的右指针，指向parent结点。同时，cur结点将要继承在该子树中parent结点的根节点的位置。即如果parent结点有它自己的父节点，cur将要和parent结点的父节点保持指向关系。（这里同样允许cur的右子树为NULL）

   旋转之后，也可以发现，parent 和 cur结点的平衡因子都变为0。

//右旋转代码实现

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR != NULL)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
    parent->_parent = subL;
if (ppNode == NULL)
{
_root = subL;
subL->_parent = NULL;
}
else
{
if (parent == ppNode->_left)
ppNode->_left = subL;
else
ppNode->_right = subL;
           subL->_parent = ppNode;
}
parent->_bf = 0;
subL->_bf = 0;
}

右左双旋：

理解了左单旋和右单旋的情况，双旋实现起来就简单了些。

上图给出了右左双旋的情况，可以看到，当parent 的平衡因子为2，cur 的平衡因子为-1时，满足右左双旋的情况。

右左双旋的实现，可分为三步。

1>以parent->_right 结点为根进行右旋转

2>以parent结点为根进行左旋转

3>进行调整。

前两步应该理解起来问题不大，但右左旋转之后，为什么还要多一步调整呢？原因就在于我的新增结点是在key=20结点（cur结点的左孩子）的左子树还是右子树插入的，还有可能20就是我的新增结点，即h=0。三种情况造成的直接后果就是cur的左孩子结点的平衡因子不同。这将是我们区分三种情况的依据。

这里有个问题值得注意，为了提高代码的复用性，我们在双旋的实现中调用了单旋的函数，但在单旋最后，我们都会将parent 和cur 结点的bf 置0。因此，在单旋之前我们需要保存cur->_left结点的平衡因子。（如上图）

//右左旋转
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
size_t bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
subRL->_bf = 0;
}
else
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
}

左右双旋：

左右双旋和右左双旋其实也差不多，当满足parent的平衡因子为-2，且cur 的平衡因子为1时，进行左右双旋。

和右左双旋的概念类似，我们依旧要先调用单旋函数，之后再进行调整。也需要注意插入节点的位置不同带来的影响，提前对cur的右节点的平衡因子进行保存。这里同样给出图示和代码，不再过多赘述。

//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
size_t bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
}

插入算法

    首先我们给出结点的定义和相应的构造函数，其中，_key为关键码，_value为值。

template <typename K, typename V>
struct AVLTreeNode
{
int _bf;
K _key;
V _value;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
AVLTreeNode(const K& key, const V& value)
:_bf(0)
, _key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
{}
};

    接下来我们分析的是插入结点的几种情况：

1、树为空树(_root == NULL）

       给根节点开辟空间并赋值，直接结束

if (_root == NULL)
{
_root = new Node(k, v);
return true;
}

2、树不为空树

要在树中插入一个结点，大致可分为几步。

1>   找到该结点的插入位置

2>   插入结点之后，调整该结点与parent结点的指向关系。

3>   向上调整插入结点祖先结点的平衡因子。

   由于AVL树是二叉搜索树，通过循环，比较待插入结点的key值和当前结点的大小，找到待插入结点的位置。同时给该节点开辟空间，确定和parent节点的指向关系。

//找到待插入结点位置
Node* cur = _root;
Node* parent = NULL;
while (cur != NULL)
{
parent = cur;
if (k > cur->_key)
{
cur = cur->_right;
}
else if (k < cur->_key)
{
cur = cur->_left;
}
else
{
return false;
}
}
//插入节点，建立指向关系
cur = new Node(k, v);
if (k < parent->_key)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}

    插入结点之后，对该AVL树结点的平衡因子进行调整。由于插入一个结点，其祖先结点的循环因子都可能发生改变，所以采用循环的方式，向上调整循环因子。

    由上图可知，当插入节点之后，该结点的向上的所有祖先结点的平衡因子并不是都在变化，当向上调整直到某一结点的平衡因子变为 0 之后，将不再向上调整，因为此时再向上的结点的左右子树高度差没有发生变化。

       接下来是向上调整平衡因子。

       由于存在要向上调整，这里定义两个指针，parent 指针和 cur 指针。当开始循环之后，首先进行调整 parent 指针的平衡因子。调整之后，判断平衡因子。

平衡因子为 0 ，则直接跳出循环。

平衡因子为 1 或 -1 时，继续向上调整，进行下次循环。

平衡因子为 2 或 -2 时，就要用到我们一开始提到的算法--->平衡树的旋转

while (parent)
{
//调整parent的bf
if (k < parent->_key)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
//如果parent的bf为0，表面插入结点之后，堆parent以上节点的bf无影响
if (parent->_bf == 0)
{
return true;
}
else if (abs(parent->_bf) == 1)  //为1、-1时继续向上调整
{
cur = parent;
parent = cur->_parent;
}
else//2、-2   为2、-2时进行旋转调整
{
if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateL(parent);
break;
}
else if (cur->_bf == -1)
{
RotateRL(parent);
break;
}
}
else//parent->_bf == -2
{
if (cur->_bf == -1)
{
RotateR(parent);
break;
}
else if (cur->_bf == 1)
{
RotateLR(parent);
break;
}
}
}
}

    到这里，插入算法就已经结束，接下来给出两个函数，用以对我们刚刚构建好的AVL树进行判断，看是否满足我们的条件。

bool IsBalance()
{
int sz = 0;
return _IsBalance_better(_root, sz);
}
bool _IsBalance(Node* root,int& height)
{
if (root == NULL)
return true;
int leftheight = 0;
if (_IsBalance(root->_left, leftheight) == false)
return false;
int rightheight = 0;
if (_IsBalance(root->_right, rightheight) == false)
return false;
height = leftheight > rightheight ? leftheight : rightheight;
return abs(leftheight - rightheight) < 2 && (root->_bf == rightheight - leftheight);
}

    关于完整的AVL树的代码，会在下面给出，这里想多说一点的是，AVL树是一棵高度平衡的二叉树，当我们构建好这样一棵二叉树之后，进行查找、插入、删除相应结点的时候，效率肯定是最高的，时间复杂度为O(logN),但实际应用中，比起和他类似的红黑树，AVL的实现难度和由于AVL树的高要求(abs(bf) <2)导致的插入结点要多次调整，AVL树的使用相对较少。