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;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-09/106609.htm