/*
* 左平衡处理
*/
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;
}