AVL樹（平衡二叉查找樹）

1、AVL樹的定義

平衡二叉查找樹，又稱作AVL樹（以提出此樹的兩人人名命名的），AVL樹是一種高度平衡的二叉查找樹，它或者是一顆空樹，或者是具有下列性質的二叉查找樹：

（1）它的左子樹和右子樹都是平衡二叉查找樹

（2）它的左子樹和右子樹的深度差的絕對值不超過1

將二叉樹上的節點的左子樹的深度減去右子樹的深度的值定義為節點的平衡因子，因此平衡因子的值只可能是：-1、0 和 1。

2、AVL樹的插入和刪除

AVL樹也是二叉查找樹，因此滿足二叉查找樹的性質。AVL樹最大的特點就是高度的平衡性，因為其節點的左右子樹高度差不超過1，這樣就能絕對的保證AVL樹的高度為O(lgn)，同紅黑樹一樣，在插入和刪除節點後，AVL樹的平衡性可能會被破壞，為了保持AVL樹的性質，必須在插入和刪除節點後進行額外的修復操作。

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

/*
* AVL樹（平衡二叉查找樹）
*/

#include <iostream>
using namespace std;

//定義AVL樹結點
typedef struct AVLNode
{
int key;
int balanceFactor;
AVLNode *left, *right, *parent;
} AVLNode, AVLTree;

/*
* 左旋
* 對以tree為根節點的樹以node為支點左旋
*/
void leftRotate(AVLTree* &tree, AVLNode* node)
{
if (! tree || ! node || ! node->right)
return;

AVLNode* rightChild = node->right;
node->right = rightChild->left;
if (rightChild->left)
{
rightChild->left->parent = node;
}

rightChild->parent = node->parent;
if (! node->parent)
{
tree = rightChild;
} else if (node == node->parent->left) {
node->parent->left = rightChild;
} else {
node->parent->right = rightChild;
}
rightChild->left = node;
node->parent = rightChild;
}

/*
* 右旋
*/
void rightRotate(AVLTree* &tree, AVLNode* node)
{
if (! tree || ! node || ! node->left)
return;

AVLNode* leftChild = node->left;
node->left = leftChild->right;
if (leftChild->right)
{
leftChild->right->parent = node;
}

leftChild->parent = node->parent;
if (! node->parent)
{
tree = leftChild;
} else if (node == node->parent->left) {
node->parent->left = leftChild;
} else {
node->parent->right = leftChild;
}

leftChild->right = node;
node->parent = leftChild;
}

/*
* 左平衡處理
*/
void leftBalanceForInsert(AVLTree* &tree, AVLNode* node)
{
if (! tree || ! node || ! node->left)
return;

AVLNode* leftChild = node->left;
switch (leftChild->balanceFactor)
{
case 1:
//新插入節點是在node的左孩子的左子樹上，需要做單右旋處理
node->balanceFactor = leftChild->balanceFactor = 0;
rightRotate(tree, node);
break;
case 0:
//這種情況只有一種，那就是leftChild就是新插入的結點
//否則如果leftChild是中間結點，在回溯的過程中，leftChild的平衡因子
//必然會被修改成1或者-1
// 因為是新插入的結點，所以不用做處理
break;
case -1:
//新插入的節點是在node的左孩子的右子樹上面，需要先左旋，再右旋
//首先根據node的左孩子的右子樹根的平衡因子確定旋轉後的節點平衡因子
switch (leftChild->right->balanceFactor)
{
case -1:
node->balanceFactor = 0;
leftChild->balanceFactor = 1;
break;
case 0:
node->balanceFactor = leftChild->balanceFactor = 0;
break;
case 1:
node->balanceFactor = -1;
leftChild->balanceFactor = 0;
break;
}
leftChild->right->balanceFactor = 0;
leftRotate(tree, node->left);
rightRotate(tree, node);
break;
}
}

/*
* 右平衡處理
*/
void rightBalanceForInsert(AVLTree* &tree, AVLNode* node)
{
if (! tree || ! node || ! node->right)
return;

AVLNode* rightChild = node->right;
switch (rightChild->balanceFactor)
{
case 1:
//新插入的節點是在node的右孩子的左子樹上面，需要先右旋，再左旋
//首先根據node的右孩子的左子樹根的平衡因子確定旋轉後的節點平衡因子
switch (rightChild->left->balanceFactor)
{
case 1:
node->balanceFactor = 0;
rightChild->balanceFactor = -1;
break;
case 0:
node->balanceFactor = rightChild->balanceFactor = 0;
break;
case -1:
node->balanceFactor = 1;
rightChild->balanceFactor = 0;
break;
}
rightChild->left->balanceFactor = 0;
rightRotate(tree, node->right);
leftRotate(tree, node);
break;
case 0:
//這種情況只有一種，那就是leftChild就是新插入的結點
//否則如果leftChild是中間結點，在回溯的過程中，leftChild的平衡因子
//必然會被修改成1或者-1
// 因為是新插入的結點，所以不用做處理
break;
case -1:
//新插入節點是在node的右孩子的右子樹上，直接左旋即可
node->balanceFactor = rightChild->balanceFactor = 0;
leftRotate(tree, node);
break;
}
}

/*
* 左平衡處理
*/
void leftBalanceForDelete(AVLTree* &tree, AVLNode* node)
{
if (! tree || ! node || ! node->left)
return;

AVLNode* leftChild = node->left;
switch (leftChild->balanceFactor)
{
case 1:
node->balanceFactor = leftChild->balanceFactor = 0;
rightRotate(tree, node);
break;
case 0:
node->balanceFactor = 1;
leftChild->balanceFactor = -1;
rightRotate(tree, node);
break;
case -1:
switch (leftChild->right->balanceFactor)
{
case -1:
node->balanceFactor = 0;
leftChild->balanceFactor = 1;
break;
case 0:
node->balanceFactor = leftChild->balanceFactor = 0;
break;
case 1:
node->balanceFactor = -1;
leftChild->balanceFactor = 0;
break;
}
leftChild->right->balanceFactor = 0;
leftRotate(tree, node->left);
rightRotate(tree, node);
break;
}
}

/*
* 右平衡處理
*/
void rightBalanceForDelete(AVLTree* &tree, AVLNode* node)
{
if (! tree || ! node || ! node->right)
return;

AVLNode* rightChild = node->right;
switch (rightChild->balanceFactor)
{
case 1:
switch (rightChild->left->balanceFactor)
{
case 1:
node->balanceFactor = 0;
rightChild->balanceFactor = -1;
break;
case 0:
node->balanceFactor = rightChild->balanceFactor = 0;
break;
case -1:
node->balanceFactor = 1;
rightChild->balanceFactor = 0;
break;
}
rightChild->left->balanceFactor = 0;
rightRotate(tree, node->right);
leftRotate(tree, node);
break;
case 0:
node->balanceFactor = -1;
rightChild->balanceFactor = 1;
leftRotate(tree, node);
break;
case -1:
node->balanceFactor = rightChild->balanceFactor = 0;
leftRotate(tree, node);
break;
}
}

void avlInsertFixup(AVLTree* &tree, AVLNode* node)
{
bool isTaller = true;
while (isTaller && node->parent)
{
if (node == node->parent->left)
{
switch (node->parent->balanceFactor)
{
case 1:
leftBalanceForInsert(tree, node->parent);
isTaller = false;
break;
case 0:
node->parent->balanceFactor = 1;
isTaller = true;
break;
case -1:
node->parent->balanceFactor = 0;
isTaller = false;
break;
}
} else {
switch (node->parent->balanceFactor)
{
case 1:
node->parent->balanceFactor = 0;
isTaller = false;
break;
case 0:
node->parent->balanceFactor = -1;
isTaller = true;
break;
case -1:
rightBalanceForInsert(tree, node->parent);
isTaller = false;
break;
}
}
node = node->parent;
}
}

/*
* 插入節點
* 同BST的插入相類似，只是插入後需要做調整以保證AVL樹的性質
*/
void avlInsert(AVLTree* &tree, AVLNode* node)
{
if (! node)
return;

AVLNode* pos = NULL;
AVLNode* temp = tree;
while (temp)
{
pos = temp;
if (node->key < temp->key)
{
temp = temp->left;
} else {
temp = temp->right;
}
}

node->parent = pos;
if (! pos)
{
tree = node;
} else if (node->key < pos->key) {
pos->left = node;
} else {
pos->right = node;
}

avlInsertFixup(tree, node);
}

AVLNode* avlTreeMinimum(AVLNode* node)
{
if (! node)
return NULL;

while (node->left)
{
node = node->left;
}

return node;
}

AVLNode* avlTreeSuccessor(AVLNode* node)
{
if (! node)
return NULL;

if (node->right)
{
return avlTreeMinimum(node->right);
}

AVLNode* parentNode = node->parent;
while (parentNode && node == parentNode->right)
{
node = parentNode;
parentNode = node->parent;
}

return parentNode;
}

void avlDeleteFixup(AVLTree* &tree, AVLNode* node)
{
bool isLower = true;
while (isLower && node->parent)
{
if (node == node->parent->left)
{
switch (node->parent->balanceFactor)
{
case 1:
node->parent->balanceFactor = 0;
isLower = true;
break;
case 0:
node->parent->balanceFactor = -1;
isLower = false;
break;
case -1:
rightBalanceForDelete(tree, node->parent);
isLower = true;
break;
}
} else {
switch (node->parent->balanceFactor)
{
case 1:
leftBalanceForDelete(tree, node->parent);
isLower = true;
break;
case 0:
node->parent->balanceFactor = 1;
isLower = false;
break;
case -1:
node->parent->balanceFactor = 0;
isLower = true;
break;
}
}
node = node->parent;
}
}

/*
* 刪除節點，與插入節點相反對應
*/
AVLNode* avlDelete(AVLTree* &tree, AVLNode* node)
{
if (! tree || ! node)
{
return NULL;
}

AVLNode* delNode = NULL;
if (! node->left || ! node->right)
{
delNode = node;
} else {
delNode = avlTreeSuccessor(node);
}

AVLNode* fillNode = NULL;
if (delNode->left)
{
fillNode = delNode->left;
} else {
fillNode = delNode->right;
}

if (fillNode)
{
fillNode->parent = delNode->parent;
}

if (! delNode->parent)
{
tree = fillNode;
} else if (delNode == delNode->parent->left) {
delNode->parent->left = fillNode;
} else {
delNode->parent->right = fillNode;
}

if (delNode != node)
{
node->key = delNode->key;
}

avlDeleteFixup(tree, delNode);

return delNode;
}