/*
* 插入节点
* 同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);