base_bnt.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 482 行 · 第 1/2 页

        ptr->ltree = raised_node;               //  change ltree to raised node
      else if (route == RIGHT)                  // or for right route
        ptr->rtree = raised_node;               //  change rtree to raised node
      raised_node = NULL;
    }
    if (more_todo == FALSE)                     // Exit loop when all balanced
      break;
    
    if (route == LEFT) {                        // Node inserted as an LTREE
      switch (ptr->avl_balance) {               // Depending on node's balance
      case 1:
        ptr->avl_balance = 0;                   // Set node as balanced
        more_todo = FALSE;
        break;
      case 0:
        ptr->avl_balance = -1;                  // Set node as 1 heavy on left
        break;
      case -1:                                  // Will need to rotate
        more_todo = FALSE;
        p1 = ptr->ltree;                        
        if (p1->avl_balance == -1) {            // Single Right Rotation
          ptr->ltree = p1->rtree;
          p1->rtree = ptr;
          p1->avl_balance = 0;
          ptr->avl_balance = 0;
          raised_node = p1;                     // This node bubbled up
        }                                       // End Single right rotation
        else {                                  // Double Right Rotation
          p2 = p1->rtree;
          p1->rtree = p2->ltree;
          p2->ltree = p1;
          ptr->ltree = p2->rtree;
          p2->rtree = ptr;
          if (p2->avl_balance == -1)            // update balance for ptr
            ptr->avl_balance = 1;
          else
            ptr->avl_balance = 0;
          if (p2->avl_balance == 1)             // update balance for p1
            p1->avl_balance = -1;
          else
            p1->avl_balance = 0;
          p2->avl_balance = 0;                  // update balance for p2
          raised_node = p2;                     // This node now moved up
          break;
        }                                       // End Left Right Rotation
      }                                         // End switch
    }                                           // End LTREE path
    
    else {                                      // Node inserted as an RTREE
      switch (ptr->avl_balance) {
      case -1:
        ptr->avl_balance = 0;                   // Node is now balanced
        more_todo = FALSE;                      // Tree is now balanced
        break;
      case 0:
        ptr->avl_balance = 1;                   // Node is 1 heavy on right
        break;
      case 1:                                   // Will need to rotate
        more_todo = FALSE;
        p1 = ptr->rtree;
        if (p1->avl_balance == 1) {             // Single Left Rotation
          ptr->rtree = p1->ltree;
          p1->ltree = ptr;
          p1->avl_balance = 0;
          ptr->avl_balance = 0;
          raised_node = p1;
        }                                       // End Single Left Rotation
        else {                                  // Right/Left Rotation
          p2 = p1->ltree;
          p1->ltree = p2->rtree;
          p2->rtree = p1;
          ptr->rtree = p2->ltree;
          p2->ltree = ptr;
          if (p2->avl_balance == 1)             // Update balance for ptr
            ptr->avl_balance = -1;
          else
            ptr->avl_balance = 0;
          if (p2->avl_balance == -1)            // Update balance for p1
            p1->avl_balance = 1;
          else
            p1->avl_balance = 0;
          p2->avl_balance = 0;                  // update balance for p2
          raised_node = p2;                     // This node now moved up
          break;
        }                                       // End Right/Left Rotation
      }                                         // End switch
    }                                           // End RTREE path
  }

  if (raised_node != NULL) {                    // When a node gets raised
    this->root = raised_node;                   //  raised_node to be root
  }
}

// Balances the nodes in the path of a removed node for an AVL Binary Tree
// The parent nodes and index to their subtrees are maintained in a Stack of 
// Stack_entrys
 
void CoolBase_Binary_Tree::avl_remove_balance (BT_Stack &stack) {
  CoolBase_Binary_Node *p, *p1, *p2, *raised_node=NULL; // Temporary pointers to nodes
  Boolean more_todo=TRUE;                       // When more_todo is FALSE, done.
  Left_Right route=NONE;
  while (stack.length() > 0) {                  // Loop thru nodes on stack
    Stack_Entry stack_entry = stack.pop();      // Get next stack_entry
    p = stack_entry.get_first();                // Get Node 
    route = (Left_Right)stack_entry.get_second();// Get the subtree

    // UPDATE PARENT TO POINT AT RAISED NODE FROM PREVIOUS ITERATION
    if (raised_node != NULL) {                  // If there is a raised node
      if (route == LEFT)                        //    See what side was changed
          p->ltree = raised_node;               //    Update ltree
      else
        p->rtree = raised_node;                 //    or update rtree
      raised_node = NULL;                       //    raised_node taken care of.
    }

    if (more_todo == FALSE)                     // Tree is balanced
      break;

    // BALANCE LEFT SUBTREE OF NODE P.  Note that this is VERY similar 
    // to the code below to balance the right side.  Changes here are likely
    // necessary below also.

    if (route == LEFT) {
      switch (p->avl_balance) {
      case -1:                                  // Set balance to 0. 
        p->avl_balance = 0;                     //   balance parent node
        break;
      case 0:                                   // Set balance to 1.  Tree is 
        p->avl_balance = 1;                     //   all balanced.
        more_todo = FALSE;
        break;
      case 1:                                   // Need to rotate
        p1 = p->rtree;
        if (p1->avl_balance >= 0) {             
          p->rtree = p1->ltree;                 // Single left rotate
          p1->ltree = p;
          raised_node = p1;
          if (p1->avl_balance == 0) {           // Update p and p1 balance
            p->avl_balance = 1;
            p1->avl_balance = -1;
            more_todo = FALSE;
          }
          else {
            p->avl_balance = 0;
            p1->avl_balance = 0;
          }
        }
        else {                                  // Double right left rotate
          p2 = p1->ltree;
          p1->ltree = p2->rtree;
          p2->rtree = p1;
          p->rtree = p2->ltree;
          p2->ltree = p;
          int b2 = p2->avl_balance;
          if (b2 == 1)                          // Set new balance for node p
            p->avl_balance = -1;
          else
            p->avl_balance = 0;
          if (b2 == -1)                         // Set new balance for node p1
            p1->avl_balance = 1;
          else 
            p1->avl_balance = 0;

          p2->avl_balance = 0;                  // Set new balance for node p2
          raised_node = p2;             
        }
      }
    }
    // BALANCE RIGHT SUBTREE OF NODE P.  Note that this is VERY similar
    // to the code above to balance the left side.  Changes here are likely
    // necessary above also.
    else {
      switch (p->avl_balance) {
      case 1:                                   // Set balance to 0. 
        p->avl_balance = 0;                     //   balance parent node
        break;
      case 0:                                   // Set balance to 1.  Tree is 
        p->avl_balance = -1;                    //   all balanced.
        more_todo = FALSE;
        break;
      case -1:                                  // Need to rotate
        p1 = p->ltree;
        if (p1->avl_balance <= 0) {             // Single right rotate
          p->ltree = p1->rtree;
          p1->rtree = p;
          raised_node = p1;
          if (p1->avl_balance == 0) {           // Update p and p1 balance
            p->avl_balance = -1;
            p1->avl_balance = 1;
            more_todo = FALSE;                  
          }
          else {
            p->avl_balance = 0;
            p1->avl_balance = 0;
          }
        }
        else {                                  // Double left right rotate
          p2 = p1->rtree;
          p1->rtree = p2->ltree;
          p2->ltree = p1;
          p->ltree = p2->rtree;
          p2->rtree = p;
          int b2 = p2->avl_balance;
          if (b2 == -1)                         // Set new balance for node p
            p->avl_balance = 1;
          else
            p->avl_balance = 0;
          if (b2 == 1)                          // Set new balance for node p1
            p1->avl_balance = -1;
          else
            p1->avl_balance = 0;

          p2->avl_balance = 0;                  // Set new balance for node p2
          raised_node = p2;
        }
      }
    }
  }

  // If raised_node is non_null, after all the balancing is done, it means
  // we have a new root. 
  if (raised_node != NULL) {
    this->root = raised_node;
  }
}
                          

// curpos_error -- Raise exception for invalid current position
// Input:         Character string of function and type
// Output:        None

void CoolBase_Binary_Tree::curpos_error (const char* Type, const char* fcn) {
  //RAISE Error, SYM(CoolBase_Binary_Tree), SYM(Invalid_Cpos),
  printf ("CoolBase_Binary_Tree<%s>::%s: Invalid current position.\n", Type, fcn);
  abort ();
}