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