14.5.3 Step 4: Rebalance

The two cases for PAVL deletion are distinguished based on x's balance factor, as always:

542. <Step 4: Rebalance after PAVL deletion 542> =
struct pavl_node *x = y->pavl_link[1];
if (x->pavl_balance == -1)
  { 
    <Left-side rebalancing case 1 in PAVL deletion 543> 
  }
else 
  { 
    <Left-side rebalancing case 2 in PAVL deletion 544> 
  }

This code is included in 541.

Case 1: x has - balance factor

The same rebalancing is needed here as for a - balance factor in PAVL insertion, and the same code is used.

543. <Left-side rebalancing case 1 in PAVL deletion 543> =
struct pavl_node *w;

<Rebalance for - balance factor in PAVL insertion in right subtree 535>
q->pavl_link[dir] = w;

This code is included in 542.

Case 2: x has + or 0 balance factor

If x has a + or 0 balance factor, we rotate left at y and update parent pointers as for any left rotation (see PBST Rotations). We also update balance factors. If x started with balance factor 0, then we're done. Otherwise, x becomes the new y for the next loop iteration, and rebalancing continues. See avldel2, for details on this rebalancing case.

544. <Left-side rebalancing case 2 in PAVL deletion 544> =
y->pavl_link[1] = x->pavl_link[0];
x->pavl_link[0] = y;
x->pavl_parent = y->pavl_parent;
y->pavl_parent = x;
if (y->pavl_link[1] != NULL)
  y->pavl_link[1]->pavl_parent = y;
q->pavl_link[dir] = x;
if (x->pavl_balance == 0) 
  {
    x->pavl_balance = -1;
    y->pavl_balance = +1;
    break;
  } 
else 
  {
    x->pavl_balance = y->pavl_balance = 0;
    y = x;
  }

This code is included in 542.