淺析AVL樹算法

AVL樹簡(jiǎn)介

   AVL樹是一種高度平衡的二叉樹，在定義樹的每個(gè)結(jié)點(diǎn)的同時(shí)，給樹的每一個(gè)結(jié)點(diǎn)增加成員 平衡因子bf  ，定義平衡因子為右子樹的高度減去左子樹的高度。AVL樹要求所有節(jié)點(diǎn)左右子樹的高度差不超過(guò)2，即bf的絕對(duì)值小于2。

   當(dāng)我們插入新的結(jié)點(diǎn)之后，平衡樹的平衡狀態(tài)將會(huì)被破壞，因此我們需要采用相應(yīng)的調(diào)整算法使得樹重新回歸平衡。

預(yù)備知識(shí)

    前文說(shuō)當(dāng)插入新的結(jié)點(diǎn)時(shí)，樹的結(jié)構(gòu)可能會(huì)發(fā)生破壞，因此我們?cè)O(shè)定了一套調(diào)整算法。調(diào)整可分為兩類：一類是結(jié)構(gòu)調(diào)整，即改變樹中結(jié)點(diǎn)的連接關(guān)系，另一類是平衡因子的調(diào)整，使平衡因子重新滿足AVL樹的要求。調(diào)整過(guò)程包含四個(gè)基本的操作，左旋轉(zhuǎn)，右旋轉(zhuǎn)，右左雙旋，左右雙旋。   

平衡樹的旋轉(zhuǎn)，目的只有一個(gè)，降低樹的高度，高度降低之后，就大大簡(jiǎn)化了在樹中查找結(jié)點(diǎn)時(shí)間復(fù)雜度。

左旋：   

10、20為樹的三個(gè)結(jié)點(diǎn)。當(dāng)在20的右子樹插入一個(gè)結(jié)點(diǎn)之后，如圖。當(dāng)Parent結(jié)點(diǎn)的平衡因子為2，cur結(jié)點(diǎn)的平衡因子為1時(shí)進(jìn)行左旋。

將 parent 的 right 指針，指向cur 的left結(jié)點(diǎn)；同時(shí)cur的left 指針，指向parent 結(jié)點(diǎn)。cur 結(jié)點(diǎn)繼承了原來(lái)parent結(jié)點(diǎn)在該樹（子樹）中的根節(jié)點(diǎn)的位置，如果原來(lái)的parent結(jié)點(diǎn)還有父結(jié)點(diǎn)，cur需要和上一層的結(jié)點(diǎn)保持連接關(guān)系。（這里我們?cè)试Scur的左子樹為NULL）

可以看到，旋轉(zhuǎn)之后，原來(lái)的parent結(jié)點(diǎn)和cur結(jié)點(diǎn)的平衡因子都變?yōu)? 。

//左旋轉(zhuǎn)代碼實(shí)現(xiàn)：
	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;
	}

右旋：

    右旋和左旋的原理類似，和左旋成鏡像關(guān)系。當(dāng)parent結(jié)點(diǎn)的平衡因子變?yōu)?-2，cur結(jié)點(diǎn)的平衡因子變?yōu)?1 時(shí)，進(jìn)行右旋。

   將 parent 結(jié)點(diǎn)的左指針，指向cur結(jié)點(diǎn)的右子樹，cur結(jié)點(diǎn)的右指針，指向parent結(jié)點(diǎn)。同時(shí)，cur結(jié)點(diǎn)將要繼承在該子樹中parent結(jié)點(diǎn)的根節(jié)點(diǎn)的位置。即如果parent結(jié)點(diǎn)有它自己的父節(jié)點(diǎn)，cur將要和parent結(jié)點(diǎn)的父節(jié)點(diǎn)保持指向關(guān)系。（這里同樣允許cur的右子樹為NULL）

   旋轉(zhuǎn)之后，也可以發(fā)現(xiàn)，parent 和 cur結(jié)點(diǎn)的平衡因子都變?yōu)?。

//右旋轉(zhuǎn)代碼實(shí)現(xiàn)

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;
}

右左雙旋：

理解了左單旋和右單旋的情況，雙旋實(shí)現(xiàn)起來(lái)就簡(jiǎn)單了些。

上圖給出了右左雙旋的情況，可以看到，當(dāng)parent 的平衡因子為2，cur 的平衡因子為-1時(shí)，滿足右左雙旋的情況。

右左雙旋的實(shí)現(xiàn)，可分為三步。

1>以parent->_right 結(jié)點(diǎn)為根進(jìn)行右旋轉(zhuǎn)

2>以parent結(jié)點(diǎn)為根進(jìn)行左旋轉(zhuǎn)

3>進(jìn)行調(diào)整。

前兩步應(yīng)該理解起來(lái)問(wèn)題不大，但右左旋轉(zhuǎn)之后，為什么還要多一步調(diào)整呢？原因就在于我的新增結(jié)點(diǎn)是在key=20結(jié)點(diǎn)（cur結(jié)點(diǎn)的左孩子）的左子樹還是右子樹插入的，還有可能20就是我的新增結(jié)點(diǎn)，即h=0。三種情況造成的直接后果就是cur的左孩子結(jié)點(diǎn)的平衡因子不同。這將是我們區(qū)分三種情況的依據(jù)。

這里有個(gè)問(wèn)題值得注意，為了提高代碼的復(fù)用性，我們?cè)陔p旋的實(shí)現(xiàn)中調(diào)用了單旋的函數(shù)，但在單旋最后，我們都會(huì)將parent 和cur 結(jié)點(diǎn)的bf 置0。因此，在單旋之前我們需要保存cur->_left結(jié)點(diǎn)的平衡因子。（如上圖）

//右左旋轉(zhuǎn)
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;
}
}

左右雙旋：

左右雙旋和右左雙旋其實(shí)也差不多，當(dāng)滿足parent的平衡因子為-2，且cur 的平衡因子為1時(shí)，進(jìn)行左右雙旋。

和右左雙旋的概念類似，我們依舊要先調(diào)用單旋函數(shù)，之后再進(jìn)行調(diào)整。也需要注意插入節(jié)點(diǎn)的位置不同帶來(lái)的影響，提前對(duì)cur的右節(jié)點(diǎn)的平衡因子進(jìn)行保存。這里同樣給出圖示和代碼，不再過(guò)多贅述。

//左右雙旋
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;
}
}

插入算法

    首先我們給出結(jié)點(diǎn)的定義和相應(yīng)的構(gòu)造函數(shù)，其中，_key為關(guān)鍵碼，_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)
{}
};

    接下來(lái)我們分析的是插入結(jié)點(diǎn)的幾種情況：

1、樹為空樹(_root == NULL）

       給根節(jié)點(diǎn)開辟空間并賦值，直接結(jié)束

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

2、樹不為空樹

要在樹中插入一個(gè)結(jié)點(diǎn)，大致可分為幾步。

1>   找到該結(jié)點(diǎn)的插入位置

2>   插入結(jié)點(diǎn)之后，調(diào)整該結(jié)點(diǎn)與parent結(jié)點(diǎn)的指向關(guān)系。

3>   向上調(diào)整插入結(jié)點(diǎn)祖先結(jié)點(diǎn)的平衡因子。

   由于AVL樹是二叉搜索樹，通過(guò)循環(huán)，比較待插入結(jié)點(diǎn)的key值和當(dāng)前結(jié)點(diǎn)的大小，找到待插入結(jié)點(diǎn)的位置。同時(shí)給該節(jié)點(diǎn)開辟空間，確定和parent節(jié)點(diǎn)的指向關(guān)系。

//找到待插入結(jié)點(diǎn)位置
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;
}
}
//插入節(jié)點(diǎn)，建立指向關(guān)系
cur = new Node(k, v);
if (k < parent->_key)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}

    插入結(jié)點(diǎn)之后，對(duì)該AVL樹結(jié)點(diǎn)的平衡因子進(jìn)行調(diào)整。由于插入一個(gè)結(jié)點(diǎn)，其祖先結(jié)點(diǎn)的循環(huán)因子都可能發(fā)生改變，所以采用循環(huán)的方式，向上調(diào)整循環(huán)因子。

    由上圖可知，當(dāng)插入節(jié)點(diǎn)之后，該結(jié)點(diǎn)的向上的所有祖先結(jié)點(diǎn)的平衡因子并不是都在變化，當(dāng)向上調(diào)整直到某一結(jié)點(diǎn)的平衡因子變?yōu)?0 之后，將不再向上調(diào)整，因?yàn)榇藭r(shí)再向上的結(jié)點(diǎn)的左右子樹高度差沒(méi)有發(fā)生變化。

       接下來(lái)是向上調(diào)整平衡因子。

       由于存在要向上調(diào)整，這里定義兩個(gè)指針，parent 指針和 cur 指針。當(dāng)開始循環(huán)之后，首先進(jìn)行調(diào)整 parent 指針的平衡因子。調(diào)整之后，判斷平衡因子。

平衡因子為 0 ，則直接跳出循環(huán)。

平衡因子為 1 或 -1 時(shí)，繼續(xù)向上調(diào)整，進(jìn)行下次循環(huán)。

平衡因子為 2 或 -2 時(shí)，就要用到我們一開始提到的算法--->平衡樹的旋轉(zhuǎn)

while (parent)
{
//調(diào)整parent的bf
if (k < parent->_key)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
//如果parent的bf為0，表面插入結(jié)點(diǎn)之后，堆parent以上節(jié)點(diǎn)的bf無(wú)影響
if (parent->_bf == 0)
{
return true;
}
else if (abs(parent->_bf) == 1)  //為1、-1時(shí)繼續(xù)向上調(diào)整
{
cur = parent;
parent = cur->_parent;
}
else//2、-2   為2、-2時(shí)進(jìn)行旋轉(zhuǎn)調(diào)整
{
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;
}
}
}
}

    到這里，插入算法就已經(jīng)結(jié)束，接下來(lái)給出兩個(gè)函數(shù)，用以對(duì)我們剛剛構(gòu)建好的AVL樹進(jìn)行判斷，看是否滿足我們的條件。

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);
}

    關(guān)于完整的AVL樹的代碼，會(huì)在下面給出，這里想多說(shuō)一點(diǎn)的是，AVL樹是一棵高度平衡的二叉樹，當(dāng)我們構(gòu)建好這樣一棵二叉樹之后，進(jìn)行查找、插入、刪除相應(yīng)結(jié)點(diǎn)的時(shí)候，效率肯定是最高的，時(shí)間復(fù)雜度為O(logN),但實(shí)際應(yīng)用中，比起和他類似的紅黑樹，AVL的實(shí)現(xiàn)難度和由于AVL樹的高要求(abs(bf) <2)導(dǎo)致的插入結(jié)點(diǎn)要多次調(diào)整，AVL樹的使用相對(duì)較少。