AVL Insert from Slides

AVL.cpp

node *root=NULL;
void AVL_Insert(data X)
{
    node *Y;          // The new node we insert
    node *A, *B, *F;  // see below...
    node *C, *CL, *CR // ... for description
    int  d;           // displacement; Used to adjust BFs
    
    if (root==NULL)   // Empty tree? Make root node!
    {
        Y = new node;  // make and fill a node
        Y->data = X;
        Y->LCH  = Y->RCH = NULL;  // leaf --> no children
        Y->BF   = 0;   // it is, by definition, balanced
        root = Y;      // root was NULL, so Y is new root
        return;        // This was the trivial case
    }
    
    // Locate insertion point for X.
    // P scans through the tree until it falls off bottom
    // Q is P’s parent (Q lags behind P)
    //    New Node Y will be the Left or Right child of Q
    // A is the last parent above Y w/BF=±1 (pre-insert)
    // F is A’s parent (F lags behind A)
    //
    F = Q = NULL; // F and Q lag, so they start NULL
    A = P = root; // A and P start at the root
    
    while (P != NULL) // search tree for insertion point
    {
        if (X == P->data) return;  // ALREADY HERE!
        if (P->BF !=0)   // remember the last place we saw
        {
            // a non-zero BF (and its parent)
            A=P;
            F=Q;
        }
        
        Q = P;                               // advance Q
        P = (X < P->data) ? P->LCH : P->RCH; // and P
    }
    
    // At this point, P is NULL, but Q points at the last
    // node where X belongs (either as Q’s LCH or RCH,
    // and Q points at an existing leaf)
    
    Y = new node;   // Make a new node
    Y->data = X;    // Put our data (X) in it
    Y->LCH  = NULL; // New nodes are always inserted
    Y->RCH  = NULL; // as leaves (i.e., no children)
    Y->BF   = 0;    // Leaves are always balanced
    
    // Will Y be Q's new left or right child?
    if (X < Q->data) Q->LCH = Y;
    else             Q->RCH = Y;
    
    // so far, except for keeping track of F and A, we
    // have done the same “dumb” BST insert we’ve seen
    // before.  Now, time to detect (and fix) imbalance
    
    // Adjust BFs from A to Q.
    // A was the LAST ancestor with a BF of ± 1, (or is
    // still the root, because we never FOUND a BF
    // of ± 1), so ALL nodes BETWEEN A and Q must have a
    // BF of 0, and will, therefore, BECOME ± 1.
    //
    // If X is inserted in the LEFT subtree of A, then
    // d = +1 (d = -1 means we inserted X in the RIGHT
    // subtree of A.
    
    if (X > A->data)
    {
        P=A->RCH;
        B=P;
        d=-1;
    }
    else
    {
        P=A->LCH;
        B=P;
        d=+1;
    }
    
    while (P != Y)  // P is now one node below A
    {               // Don’t do anything to new node (Y)
        if (X>P->data)
        {
            P->BF=-1;
            P=P->RCH;
        }
        else
        {
            P->BF=+1;
            P=P->LCH;
        }
    }
    
    // Now we check the BF at A and see if we just
    // BALANCED the tree, IMBALANCED the tree, or if
    // it is still BALANCED ENOUGH.
    if (A->BF==0) // Tree WAS completely balanced.  The
    {             // insert pushed it to slight imbalance
        A->BF=d;    // set the BF to +/- 1.  This is close
        return;     // enough to live with, so exit now
    }
    
    if (A->BF== -d) // If the tree had a slight imbalance
    {               // the OTHER way, did the insertion
        A->BF = 0;   // throw the tree INTO balance?
        return;      // If so, set the BF to zero & return
    }
    
    // If we took neither of the two returns just above,
    // then the tree WAS acceptably imbalanced, and is
    // now UNACCEPTABLY IMBALANCED. Which rotation type?
    if (d==+1) // left imbalance.  LL or LR?
    {
        if (B->BF==+1) // LL rotation
        {
            // Change the child pointers at A and B to
            // reflect the rotation. Adjust the BFs at A & B
            // <<< LEFT FOR YOU TO WRITE (3-4 LOC) >>>
            // See Schematic (1)
        }
        else  // LR Rotation: three cases
        {
            // Adjust the child pointers of nodes A, B, & C
            // to reflect the new post-rotation structure
            // <<< LEFT FOR YOU TO WRITE, BUT HERE’S >>>
            // <<< A HEAD START (4 LOC here)         >>>
            C  = B->RCH; // C is B's right child
            CL = C->LCH; // CL and CR are C's left
            CR = C->RCH; //    and right children
            // See Schematic (2) and (3)
            switch (C->BF)
            {
                // Set the new BF’s at A and B, based on the
                // BF at C. Note: There are 3 sub-cases
                // <<< LEFT FOR YOU TO WRITE (3 LOC/CASE) >>>
            }
            
            C->BF=0; B=C;
        } // end of else (LR Rotation)
    } // end of “if (d = +1)”
    else // d=-1.  This is a right imbalance
    {
        // (RR or RL).  THAT code goes here.
        // <<< LEFT FOR YOU TO WRITE, BUT IT’S >>>
        // <<< SYMMETRIC TO THE LEFT IMBALANCE >>>
    }
    // Finish up:
    //
    // The subtree with root B has been rebalanced, and
    // is the new subtree of F.  The original subtree
    // of F had root A.
    
    // did we rebalance the root?
    if (F == NULL)
    {
        root=B;
        return;
    }
    
    // otherwise, we rebalanced whatever was the
    // child (left or right) of F.
    if (A == F->LCH)
    {
        F->LCH=B;
        return;
    }
    if (A == F->RCH)
    {
        F->RCH=B;
        return;
    }
    cout << “We should never be heren”;
    
} // End of AVL_Insert