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

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