#define MAX 4   /* maximum number of keys in node:  MAX = m - 1       */
#define MIN 2   /* minimum number of keys in node:  MIN =  m/2  -1   */

typedef struct treenode Treenode;

struct treenode {
    int count;      /* Except for the root, the lower limit is MIN    */
    Treeentry entry[MAX+1];
    Treenode *branch[MAX+1];
};
 /* SearchTree: traverse B-tree looking for target.

 
Pre:  The B-tree pointed to by root has been created.
Post: If the key target is present in the B-tree, then the return value
      points to the node containing target in position targetpos.
      Otherwise, the return value is NULL and targetpos is undefined.
Uses: SearchTree recursively, SearchNode.
 */
 

Treenode *SearchTree(Key target, Treenode *root, int *targetpos)
{
    if (!root)
        return NULL;
 

    else if (SearchNode(target, root, targetpos))
        return root;
 

    else
        return SearchTree(target, root->branch[*targetpos], targetpos);
}
 /* SearchNode: searches keys in node for target.

 
Pre:  target is a key and current points to a node of a B-tree
Post: Searches keys in node for target; returns location pos of target,
 or branch on which to continue search.
 */
 

Boolean SearchNode(Key target, Treenode *current, int *pos)
{
    if (LT(target, current->entry[1].key)) {   /* Take the leftmost branch. */
        *pos = 0;
        return FALSE;
 

    } else {                      /* Start a sequential search through the keys.    */
        for (*pos = current->count;
             LT(target, current->entry[*pos].key) && *pos > 1; (*pos)--)
            ;
 
        return EQ(target, current->entry[*pos].key);
    }
}
 /* InsertTree: inserts entry into the B-tree.

 
Pre:  The B-tree to which root points has been created, and no entry in the
     B-tree has key equal to newentry.key.
Post: newentry has been inserted into the B-tree; the root is returned.
Uses: PushDown.
 */
Treenode *InsertTree(Treeentry newentry, Treenode *root)
{
    Treeentry medentry; /* node to be reinserted as new root            */
    Treenode *medright; /* subtree on right of medentry               */
    Treenode *newroot;  /* used when the height of the tree increases   */

    if (PushDown(newentry, root, &medentry, &medright)) { /* Tree grows in height.  */
        newroot = (Treenode *)malloc(sizeof(Treenode)); /* Make a new root. */
        newroot->count = 1;
        newroot->entry[1] = medentry;
        newroot->branch[0] = root;
        newroot->branch[1] = medright;
        return newroot;
    }
    return root;
}
 /* PushDown: recursively move down tree searching for newentry.

 
Pre:  newentry belongs in the subtree to which current points.
Post: newentry has been inserted into the subtree to which current points;
      if TRUE is returned, then the height of the subtree has grown,
      and medentry needs to be reinserted higher in the tree, with subtree
      medright on its right.
Uses: PushDown recursively, SearchNode, Split, PushIn.
 */

Boolean PushDown(Treeentry newentry, Treenode *current, Treeentry *medentry,
              Treenode **medright)
{
    int pos;                 /* branch on which to continue the search  */

    if (current == NULL) {  /* cannot insert into empty tree; terminates    */
        *medentry = newentry;
        *medright = NULL;
        return TRUE;

    } else {                 /* Search the current node.    */
        if (SearchNode(newentry.key, current, &pos))
            Warning("Inserting duplicate key into B-tree");
        if (PushDown(newentry, current->branch[pos], medentry, medright))
            if (current->count < MAX) {  /* Reinsert median key.    */
                PushIn(*medentry, *medright, current, pos);
                return FALSE;
            } else {
                Split(*medentry, *medright, current, pos, medentry, medright);
                return TRUE;
            }
        return FALSE;
    }
}
 
/* PushIn: inserts a key into a node

 
Pre:   medentry belongs at index pos in node *current, which has
      room for it.
Post: Inserts key medentry and pointer medright into *current
      at index pos.
 */
 

void PushIn(Treeentry medentry, Treenode *medright, Treenode *current, int pos)

{
                                    /* index to move keys to make room for medentry   */
    int i;
 

    for (i = current->count; i > pos; i--) {
                                    /* Shift all the keys and branches to the right.    */
 
        current->entry[i+1] = current->entry[i];
 
        current->branch[i+1] = current->branch[i];
    }
 

    current->entry[pos+1] = medentry;
 
    current->branch[pos+1] = medright;
 
    current->count++;

}
 
/* Split: splits a full node.

 
Pre:  medentry belongs at index pos of node *current which is full.
Post: Splits node *current with entry medentry and pointer medright at
      index pos into nodes *current and *newright with median
      entry newmedian.
Uses: PushIn.
 */
3 
void Split(Treeentry medentry, Treenode *medright, Treenode *current, int pos,
         Treeentry *newmedian, Treenode **newright)
{
    int i;      /* used for copying from *current to new node   */
 
    int median; /* median position in the combined, overfull node   */
 
    if (pos <= MIN) /* Determine if new key goes to left or right half. */
        median = MIN;
    else
        median = MIN + 1;
 
    /* Get a new node and put it on the right.  */
    *newright = (Treenode *)malloc(sizeof(Treenode));
 
    for (i = median+1; i <= MAX; i++) { /* Move half the keys.  */
        (*newright)->entry[i - median] = current->entry[i];
        (*newright)->branch[i - median] = current->branch[i];
    }
 
    (*newright)->count = MAX - median;
 
    current->count = median;
 
    if (pos <= MIN)     /* Push in the new key. */
        PushIn(medentry, medright, current, pos);
    else
        PushIn(medentry, medright, *newright, pos - median);
 
    *newmedian = current->entry[current->count];
 
    (*newright)->branch[0] = current->branch[current->count];
 
    current->count--;
}
 /* DeleteTree: deletes target from the B-tree.

 
Pre:   target is the key of some entry in the B-tree to which root points.
Post: This entry has been deleted from the B-tree.
Uses: RecDeleteTree.
 */
Treenode *DeleteTree(Key target, Treenode *root)
{
    Treenode *oldroot;      /* used to dispose of an empty root */

    RecDeleteTree(target, root);

    if (root->count == 0) { /* Root is empty.   */
        oldroot = root;
        root = root->branch[0];
        free(oldroot);
    }
    return root;
}
 /* RecDeleteTree: look for target to delete.

 
Pre:   target is the key of some entry in the subtree of a B-tree to which
      current points.
Post: This entry has been deleted from the B-tree.
Uses: RecDeleteTree recursively, SearchNode, Successor, Remove,
      Restore.
 */
void RecDeleteTree(Key target, Treenode *current)
{
    int pos;    /* location of target or of branch on which to search   */
    if (!current) {
        Warning("Target was not in the B-tree.");
        return; /* Hitting an empty tree is an error.   */
    } else {
        if (SearchNode(target, current, &pos))
            if (current->branch[pos-1]) {
                Successor(current, pos);    /* replaces entry[pos] by its successor */
                RecDeleteTree(current->entry[pos].key, current->branch[pos]);
            } else
                Remove(current, pos);   /* removes key from pos of *current   */
        else                /* Target was not found in the current node.    */
            RecDeleteTree(target, current->branch[pos]);
        if (current->branch[pos])
            if (current->branch[pos]->count < MIN)
                Restore(current, pos);
    }
}
 /* Remove: delete an entry and the branch to its right.

 
Pre:   current points to a node in a B-tree with an entry in index pos.
Post: This entry and the branch to its right are removed from *current.
 */
0.75 
void Remove(Treenode *current, int pos)
{
    int i;      /* index for moving entries */
    for (i = pos+1; i <= current->count; i++) {
        current->entry[i-1] = current->entry[i];
        current->branch[i-1] = current->branch[i];
    }
    current->count--;
}
 /* Successor: replaces an entry by its immediate successor.

 
Pre:   current points to a node in a B-tree with an entry in index pos.
Post: This entry is replaced by its immediate successor under order of keys.
 */
void Successor(Treenode *current, int pos)
{
    Treenode *leaf;     /* used to move down the tree to a leaf */

    /* Move as far leftward as possible.    */
    for (leaf = current->branch[pos]; leaf->branch[0]; leaf = leaf->branch[0])
        ;
    current->entry[pos] = leaf->entry[1];
}
 /* Restore: restore the minimum number of entries.

 
Pre:   current points to a node in a B-tree with an entry in index pos;
      the branch to the right of pos has one too few entries.
Post: An entry taken from elsewhere is to restore the minimum number of
      entries by entering it at current->branch[pos].
Uses: MoveLeft, MoveRight, Combine.
 */
 

void Restore(Treenode *current, int pos)

{

    if (pos == 0)   /*  case: leftmost key  */
 
        if (current->branch[1]->count > MIN)
            MoveLeft(current, 1);
 
        else
            Combine(current, 1);
 

    else if (pos == current->count) /*  case: rightmost key */
 
        if (current->branch[pos-1]->count > MIN)
            MoveRight(current, pos);
 
        else
            Combine(current, pos);
 

                                            /*  remaining cases */
    else if (current->branch[pos-1]->count > MIN)
        MoveRight(current, pos);
 

    else if (current->branch[pos+1]->count > MIN)
        MoveLeft(current, pos+1);
 

    else
        Combine(current, pos);

}
 
/* MoveRight: move a key to the right.

 
Pre:   current points to a node in a B-tree with entries in the branches
      pos and pos - 1, with too few in branch pos.
Post: The rightmost entry from branch pos - 1 has moved into
      *current, which has sent an entry into the branch pos.
 */
3 
void MoveRight(Treenode *current, int pos)
{
    int c;
    Treenode *t;

    t = current->branch[pos];
    for (c = t->count; c > 0; c--) {
    /* Shift all keys in the right node one position.   */
        t->entry[c+1] = t->entry[c];
        t->branch[c+1] = t->branch[c];
    }

    t->branch[1] = t->branch[0];    /* Move key from parent to right node.  */
    t->count++;
    t->entry[1] = current->entry[pos];

    t = current->branch[pos-1]; /* Move last key of left node into parent.  */
    current->entry[pos] = t->entry[t->count];
    current->branch[pos]->branch[0] = t->branch[t->count];
    t->count--;
}
 /* MoveLeft: move a key to the left.

 
Pre:   current points to a node in a B-tree with entries in the branches
      pos and pos - 1, with too few in branch pos - 1.
Post: The leftmost entry from branch pos has moved into
      *current, which has sent an entry into the branch pos - 1.
 */
void MoveLeft(Treenode *current, int pos)
{
    int c;
    Treenode *t;

    t = current->branch[pos-1]; /* Move key from parent into left node. */
    t->count++;
    t->entry[t->count] = current->entry[pos];
    t->branch[t->count] = current->branch[pos]->branch[0];

    t = current->branch[pos];   /* Move key from right node into parent. */
    current->entry[pos] = t->entry[1];
    t->branch[0] = t->branch[1];
    t->count--;

    for (c = 1; c <= t->count; c++) {
        /* Shift all keys in right node one position leftward.  */
        t->entry[c] = t->entry[c+1];
        t->branch[c] = t->branch[c+1];
    }
}
 /* Combine: combine adjacent nodes.

 
Pre:   current points to a node in a B-tree with entries in the branches
      pos and pos - 1, with too few to move entries.
Post: The nodes at branches pos - 1 and pos have been combined
      into one node, which also includes the entry formerly in *current at
      index pos.
 */
void Combine(Treenode *current, int pos)
{
    int c;
    Treenode *right;
    Treenode *left;

    right = current->branch[pos];
    left = current->branch[pos-1];      /* Work with the left node. */
    left->count++;              /* Insert the key from the parent.  */
    left->entry[left->count] = current->entry[pos];
    left->branch[left->count] = right->branch[0];

    for (c = 1; c <= right->count; c++) { /* Insert all keys from right node. */
        left->count++;
        left->entry[left->count] = right->entry[c];
        left->branch[left->count] = right->branch[c];
    }

    for (c = pos; c < current->count; c++) { /* Delete key from parent node. */
        current->entry[c] = current->entry[c+1];
        current->branch[c] = current->branch[c+1];
    }
    current->count--;
    free(right);    /* Dispose of the empty right node. */
}
 /*  
Pre:  The B-tree pointed to by root has been created.
Post: The tree has been been traversed in inorder sequence.
 */
void InOrder(Treenode *root)
{
    int pos;

    if (root) {
        InOrder(root->branch[0]);

        for (pos = 1; pos <= root->count; pos++) {
            printf("%c ", root->entry[pos].key);
            InOrder(root->branch[pos]);
        }
    }
}
 /* 
Pre:  The B-tree pointed to by root has been created.
Post: The tree has been been traversed in preorder sequence .
*/
void PreOrder(Treenode *root)
{
    int pos;

    if (root) {
        for (pos = 1; pos <= root->count; pos++)
            printf("%c ", root->entry[pos].key);

        for (pos = 0; pos <= root->count; pos++)
            PreOrder(root->branch[pos]);
    }
}
 /* 
Pre:  The B-tree pointed to by root has been created.
Post: The tree has been been traversed in postorder sequence.
*/
void PostOrder(Treenode *root)
{
    int pos;

    if (root) {
        for (pos = 0; pos <= root->count; pos++)
            PostOrder(root->branch[pos]);

        for (pos = 1; pos <= root->count; pos++)
            printf("%c ", root->entry[pos].key);
    }
}
 typedef struct treenode Treenode;

struct treenode {
    Treeentry entry;
    Boolean red;
    Treenode *left, *right;
};

typedef enum outcome { OK, REDNODE, RIGHTRED, LEFTRED } Outcome;
/* These outcomes from a call to the recursive insertion function describe
the following results of the call:

   
RIGHTRED:
OK:   The color of the current root (of the subtree) has not changed;
              the tree now satisfies the conditions for a red-black tree.
REDNODE: The current root has changed from black to red; modification
              may or may not be needed to restore the red-black properties.
RIGHTRED: The current root and its right child are now both red;
              a color flip or rotation is needed.
LEFTRED: The current root and its left child are now both red;
              a color flip or rotation is needed.
   */
 /* InsertTree: inserts entry into red-black tree.

 
Pre:  root points to the root of a red-black search tree; newentry is an
       entry which is not present in the tree.
Post: A node containing newentry has been inserted into the tree and
       the properties of a red-black tree restored.
 */
Treenode *InsertTree(Treeentry newentry, Treenode *root)
{
    Outcome status;
    RecInsertTree(&root, newentry, &status);
    if (status == REDNODE)
        /*  Always split the root node to keep it black.  Doing so prevents
            two red nodes at the top of the tree and a resulting attempt to
            rotate or flip colors using a parent node that does not exist. */
        root->red = FALSE;
    else if (status != OK)
        Error("Insertion with bad red-black status at root");
    return root;
}
 /* RecInsertTree: recursively move down tree to insert target.

 
Pre:   current is an actual link (not a copy) in a red-black tree; target is
       a key that does not appear in the tree.
Post: A new node has been created with newentry and inserted into the tree;
       the properties of a red-black tree have been restored, except possibly
       at the root *current and one of its children, whose status is given
       by the output parameter status.
Uses: RecInsertTree recursively,  MakeNewNode, ModifyLeft, ModifyRight.
 */
void RecInsertTree(Treenode **current, Treeentry newentry, Outcome *status)
{
    if (!(*current))
        *current = MakeNewNode(newentry, status);
    else if (LT(newentry.key, (*current)->entry.key)) {
        RecInsertTree(&(*current)->left, newentry, status);
        ModifyLeft(current, status);
    } else if (GT(newentry.key, (*current)->entry.key)) {
        RecInsertTree(&(*current)->right, newentry, status);
        ModifyRight(current, status);
    } else  /* target equals key in current node. */
        Warning("Duplicate key inserted into tree");
}
 /* ModifyLeft: update node after left insertion.

 
Pre:   An insertion has been made in the left subtree of *current which
       has returned the value of status  for this subtree.
Post: Any color change or rotation needed for the tree rooted at current 
       has been made, and  status  has been updated.
Uses: RotateRight, FlipColor, DRotateRight.
 */
 

void ModifyLeft(Treenode **current, Outcome *status)
{
    /* The value of status describes the left subtree of current. */
    switch (*status) {
    case OK:    /* No action needed, as tree is already OK. */
        break;
 
    case REDNODE:
        if ((*current)->red)
            *status = LEFTRED;  /* Both current and left child are red. */
        else
            *status = OK;   /* current is black and left is red, so now OK. */
        break;
 
    case LEFTRED:
        if (!(*current)->right) /* An empty subtree behaves like black. */
            RotateRight(current, status);
        else if ((*current)->right->red)    /* Both children are red. */
            FlipColor(current, status);

        else    /* Right child is black; left is red. */
            RotateRight(current, status);
        break;
 
    case RIGHTRED:
        if (!(*current)->right) /* An empty subtree behaves like black. */
            DRotateRight(current, status);
        else if ((*current)->right->red)    /* Both children are red. */
            FlipColor(current, status);
        else    /* Right child is black; left is red. */
            DRotateRight(current, status);
        break;
    }
}
 /* MakeNewNode: create and initialize a new node.

 
Pre:   target is a key to be put in a new node.
Post: A new red node has been created containing key target and
       status becomes REDNODE.
 */
Treenode *MakeNewNode(Treeentry newentry, Outcome *status)
{
    Treenode *new = (Treenode *)malloc(sizeof(Treenode));
 
    new->entry = newentry;
    new->red = TRUE;
    new->left = new->right = NULL;
    *status = REDNODE;
 
    return new;
}
 /*
 
Pre:   An insertion has been made in the right subtree of *current which
       has returned the value of status  for this subtree.
Post: Any color change or rotation needed for the tree rooted at current 
       has been made, and status  has been updated.
Uses: RotateLeft, FlipColor, DRotateLeft.
 */
void  ModifyRight(Treenode **current, Outcome *status)
{
    switch (*status) {
    case OK:    /* No action needed, as tree is already OK. */
        break;

    case REDNODE:
        if ((*current)->red)
            *status = RIGHTRED; /* Both current and right child are red. */

        else
            *status = OK;   /* current is black and right is red, so now OK */
        break;

    case RIGHTRED:
        if (!(*current)->left)  /* An empty subtree behaves like black. */
            RotateLeft(current, status);

        else if ((*current)->left->red) /* Both children are red. */
            FlipColor(current, status);

        else    /* Right child is black; left is red. */
            RotateLeft(current, status);
        break;

    case LEFTRED:
        if (!(*current)->left)  /* An empty subtree behaves like black. */
            DRotateLeft(current, status);

        else if ((*current)->left->red) /* Both children are red. */
            FlipColor(current, status);

        else    /* Right child is black; left is red. */
            DRotateLeft(current, status);
        break;
    }
}
 /*
 
Pre:   The node *current and both its children exist;
    *current is black and both its children are red.
Post: The colors are flipped so *current is red and both its children are
       black;  status becomes REDNODE.
 */
void FlipColor(Treenode **current, Outcome *status)
{
    if (!(*current))
        Error("Colors flipped for empty node");

    else if ((*current)->left == NULL || (*current)->right == NULL)
        Error("Colors flipped for empty subtrees");

    else if ((*current)->red ||
            !(*current)->left->red || !(*current)->right->red)
        Error("FlipColor called with wrong colored nodes");

    else {
        (*current)->red = TRUE;
        (*current)->left->red = FALSE;
        (*current)->right->red = FALSE;
        *status = REDNODE;
    }
}
 /*
 
Pre:   current is an actual pointer (not a copy) to a node;
    its right child exists.
Post: The tree is rotated left around current and the colors changed so
   the new current is black and its left child is red; status becomes OK.
 */
void RotateLeft(Treenode **current, Outcome *status)
{
    Treenode *rightchild;

    if (!(*current))
        Error("Attempt to left rotate empty tree");

    else if ((*current)->right == NULL)
        Error("Left rotate requires nonempty right child");

    else {
        (*current)->red = TRUE;
        rightchild = (*current)->right;

        rightchild->red = FALSE;
        (*current)->right = rightchild->left;

        rightchild->left = *current;
        *current = rightchild;
        *status = OK;
    }
}
 /*
 
Pre:   current is an actual pointer (not a copy) to a node;
    its left child exists.
Post: The tree is rotated right around current and the colors changed so
   the new current is black and its right child is red;  status becomes OK.
 */
void RotateRight(Treenode **current, Outcome *status)
{
    Treenode *leftchild;

    if (!(*current))
        Error("Attempt to right rotate empty tree");

    else if ((*current)->left == NULL)
        Error("Right rotate requires nonempty left child");

    else  {
        (*current)->red = TRUE;
        leftchild = (*current)->left;

        leftchild->red = FALSE;
        (*current)->left = leftchild->right;

        leftchild->right = *current;
        *current = leftchild;
        *status = OK;
    }
}
 /*
 
Pre:   current is an actual pointer (not a copy) to a node, its right child
      and that node's left (grand)child exist.
Post: The tree is double rotated left around current and the colors changed
       so the new current is black and its left child is red. status becomes
       OK.
Uses: RotateRight, RotateLeft.
 */
void DRotateLeft(Treenode **current, Outcome *status)
{
    if (!(*current))
        Error("Double left rotate an empty tree");

    else {
        RotateRight(&(*current)->right, status);
        RotateLeft(current, status);
    }
}
 /*
 
Pre:   current is an actual pointer (not a copy) to a node, its left child and
      that node's right (grand)child exist.
Post: The tree is double rotated right around current and the colors changed
      so the new current is black and its right child is red. status becomes
      OK.
Uses: RotateLeft, RotateRight.
 */
void DRotateRight(Treenode **current, Outcome *status)
{
    if (!(*current))
        Error("Double right rotate an empty tree");

    else {
        RotateLeft(&(*current)->left, status);
        RotateRight(current, status);
    }
}
 
void Recommend(Board game, Player P, Stack *S,
            Value *recvalue, Boolean *gameover);
 
void LookAhead()
{
    Use Recommend to obtain a stack S of possible moves;
    if the recursion terminates (depth == 0 or gameover)
        Return one move and associated value;
    else {
        for each recommended move from S
            Tentatively make the move and recursively LookAhead for the
              best move for the other player;
        Select the best value for P among the values returned in the loop;
        Return the corresponding move and value as the result;
    }
}
 
/* LookAhead: finds the next move

 
Pre:   The game is in a legitimate position for player P; it is the turn of
      player P, and at least one move is possible.
Post: After looking ahead depth levels through the game tree the function
      returns the recommended move recmove, which has a calculated value
      of recvalue.
Uses: Stack functions; functions Recommend, MakeMove, UndoMove,
      LookAhead (recursively), and a constant INFINITY (larger than
      the value of any move).
 */
void LookAhead(Board game, int depth, Player P, Move *recmove, Value *recvalue)
{
    Player opponent;    /* opponent of P                      */
    Move oppmove;       /* recommended move for opponent        */
    Value oppvalue;     /* value returned for opponent's move   */
    Stack S;            /* stack of recommended moves for P   */
    Move tentmove;      /* tentative move being tried in tree   */
    Boolean gameover;

    Recommend(game, P, &S, recvalue, &gameover);
    if (gameover || depth == 0)
        if (!StackEmpty(&S))
            Pop(recmove, &S);   /* Return any one move as the answer.   */
                /* The value recvalue has been set by Recommend.    */
    else {

        /* Investigate all recommended moves.   */

        if (P == FIRST) {       /* Prepare to maximize recvalue.  */
            opponent = SECOND;
            *recvalue = -INFINITY;  /* Set to a value less than any that occurs.    */
        } else {                /* Prepare to minimize recvalue.  */
            opponent = FIRST;
            *recvalue = INFINITY;   /* Set to a value greater than any that occurs. */
        }

        while (!StackEmpty(&S)) {
            Pop(&tentmove, &S);
            MakeMove(game, P, tentmove);
            LookAhead(game, depth - 1,  opponent, &oppmove, &oppvalue);
            UndoMove(game, P, tentmove);

            if ((P == FIRST && oppvalue > *recvalue) ||
                (P == SECOND && oppvalue < *recvalue)) {
                *recvalue = oppvalue;
                *recmove = tentmove;
            }
        }
    }
}