淺析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樹的使用相對較少。