AVL树（平衡二叉查找树）(3)

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