int isFull(struct node *r) {
    if (r == NULL) return 1;
    if ((r->left == NULL) != (r->right == NULL)) return 0;   /* exactly one child */
    return isFull(r->left) && isFull(r->right);
}

/* call as isComplete(root, 0, countNodes(root)) */
int isComplete(struct node *r, int i, int n) {
    if (r == NULL) return 1;
    if (i >= n) return 0;                /* position beyond n-1: there is a gap */
    return isComplete(r->left, 2 * i + 1, n) && isComplete(r->right, 2 * i + 2, n);
}

int isPerfect(struct node *r) {
    int h = height(r), n = countNodes(r);
    return n == (1 << (h + 1)) - 1;      /* n = 2^(h+1) - 1 */
}

int isLeftSkewed(struct node *r) {
    for (; r != NULL; r = r->left)
        if (r->right != NULL) return 0;
    return 1;
}

int isDegenerate(struct node *r) {
    if (r == NULL) return 1;
    if (r->left != NULL && r->right != NULL) return 0;       /* two children */
    return isDegenerate(r->left) && isDegenerate(r->right);
}

/* returns the height, or -2 as soon as some node is unbalanced */
int checkBalanced(struct node *r) {
    int lh, rh;
    if (r == NULL) return -1;
    lh = checkBalanced(r->left);  if (lh == -2) return -2;
    rh = checkBalanced(r->right); if (rh == -2) return -2;
    if (lh - rh > 1 || rh - lh > 1) return -2;
    return 1 + (lh > rh ? lh : rh);
}

/* Binary Tree: level-order insert, traversals, search, delete, count, height */
#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left, *right;
};

struct node *createNode(int x) {
    struct node *n = (struct node *)malloc(sizeof(struct node));
    n->data = x;
    n->left = n->right = NULL;
    return n;
}

/* simple array queue of node pointers */
struct node *q[100];
int front, rear;
void enqueue(struct node *n) { q[rear++] = n; }
struct node *dequeue(void) { return q[front++]; }
int isEmpty(void) { return front == rear; }

/* insert at the first free slot in level order (keeps the tree compact) */
struct node *insert(struct node *root, int x) {
    struct node *t;
    if (root == NULL) return createNode(x);
    front = rear = 0;
    enqueue(root);
    while (!isEmpty()) {
        t = dequeue();
        if (t->left == NULL)  { t->left = createNode(x);  break; }
        else enqueue(t->left);
        if (t->right == NULL) { t->right = createNode(x); break; }
        else enqueue(t->right);
    }
    return root;
}

void preorder(struct node *r)  { if (r) { printf("%d ", r->data); preorder(r->left); preorder(r->right); } }
void inorder(struct node *r)   { if (r) { inorder(r->left); printf("%d ", r->data); inorder(r->right); } }
void postorder(struct node *r) { if (r) { postorder(r->left); postorder(r->right); printf("%d ", r->data); } }

/* ---------- non-recursive versions (explicit stack) ---------- */
/* PRE-ORDER (N L R) */
void preorderIter(struct node *root) {
    struct node *stack[100], *cur;
    int top = -1;
    if (root == NULL) return;
    stack[++top] = root;                         /* start with the root     */
    while (top != -1) {
        cur = stack[top--];                      /* pop and visit           */
        printf("%d ", cur->data);
        if (cur->right) stack[++top] = cur->right; /* push RIGHT first ...  */
        if (cur->left)  stack[++top] = cur->left;  /* ... so LEFT pops first */
    }
}
/* IN-ORDER (L N R) */
void inorderIter(struct node *root) {
    struct node *stack[100], *cur = root;
    int top = -1;
    while (cur != NULL || top != -1) {
        while (cur != NULL) {                    /* go left as far as possible */
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top--];                      /* no left child left: pop */
        printf("%d ", cur->data);                /* visit                   */
        cur = cur->right;                        /* then the right subtree  */
    }
}
/* POST-ORDER (L R N), two stacks */
void postorderIter(struct node *root) {
    struct node *s1[100], *s2[100], *cur;
    int t1 = -1, t2 = -1;
    if (root == NULL) return;
    s1[++t1] = root;
    while (t1 != -1) {
        cur = s1[t1--];
        s2[++t2] = cur;                          /* s2 collects N R L       */
        if (cur->left)  s1[++t1] = cur->left;
        if (cur->right) s1[++t1] = cur->right;
    }
    while (t2 != -1)                             /* reversed: L R N         */
        printf("%d ", s2[t2--]->data);
}

void levelorder(struct node *root) {
    struct node *t;
    if (root == NULL) return;
    front = rear = 0;
    enqueue(root);
    while (!isEmpty()) {
        t = dequeue();
        printf("%d ", t->data);
        if (t->left)  enqueue(t->left);
        if (t->right) enqueue(t->right);
    }
}

/* no ordering, so search must look everywhere: O(n) */
int search(struct node *r, int key) {
    if (r == NULL) return 0;
    if (r->data == key) return 1;
    return search(r->left, key) || search(r->right, key);
}

/* delete: copy the deepest right-most node into the target, then remove the deepest node */
struct node *deleteNode(struct node *root, int key) {
    struct node *t, *target = NULL, *last = NULL, *lastParent = NULL;
    if (root == NULL) return NULL;
    if (root->left == NULL && root->right == NULL) {
        if (root->data == key) { free(root); return NULL; }
        return root;
    }
    front = rear = 0;
    enqueue(root);
    while (!isEmpty()) {
        t = dequeue();
        if (t->data == key && target == NULL) target = t;
        if (t->left)  { lastParent = t; enqueue(t->left); }
        if (t->right) { lastParent = t; enqueue(t->right); }
        last = t;                      /* last node dequeued = deepest right-most */
    }
    if (target == NULL) { printf("%d not found\n", key); return root; }
    target->data = last->data;
    if (lastParent->right == last) lastParent->right = NULL;
    else lastParent->left = NULL;
    free(last);
    return root;
}

int countNodes(struct node *r)  { return r ? 1 + countNodes(r->left) + countNodes(r->right) : 0; }
int countLeaves(struct node *r) {
    if (r == NULL) return 0;
    if (r->left == NULL && r->right == NULL) return 1;
    return countLeaves(r->left) + countLeaves(r->right);
}
int height(struct node *r) {          /* in edges: empty = -1, leaf = 0 */
    int lh, rh;
    if (r == NULL) return -1;
    lh = height(r->left);
    rh = height(r->right);
    return 1 + (lh > rh ? lh : rh);
}

int main(void) {
    struct node *root = NULL;
    int ch, x;
    while (1) {
        printf("\n1.Insert 2.Delete 3.Search 4.Traversals 5.Count/Height 6.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("Value: "); scanf("%d", &x); root = insert(root, x); break;
        case 2: printf("Value: "); scanf("%d", &x); root = deleteNode(root, x); break;
        case 3: printf("Value: "); scanf("%d", &x);
                printf(search(root, x) ? "Found\n" : "Not found\n"); break;
        case 4: printf("Recursive     Pre : "); preorder(root);
                printf("\nNon-recursive Pre : "); preorderIter(root);
                printf("\nRecursive     In  : "); inorder(root);
                printf("\nNon-recursive In  : "); inorderIter(root);
                printf("\nRecursive     Post: "); postorder(root);
                printf("\nNon-recursive Post: "); postorderIter(root);
                printf("\nLevel-order       : "); levelorder(root); printf("\n"); break;
        case 5: printf("Nodes=%d Leaves=%d Height=%d\n", countNodes(root), countLeaves(root), height(root)); break;
        case 6: return 0;
        }
    }
    return 0;
}

/* Binary Search Tree: insert, search, delete (3 cases), min, max, traversals */
#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left, *right;
};

struct node *createNode(int x) {
    struct node *n = (struct node *)malloc(sizeof(struct node));
    n->data = x;
    n->left = n->right = NULL;
    return n;
}

struct node *insert(struct node *root, int x) {
    if (root == NULL) return createNode(x);
    if (x < root->data)      root->left  = insert(root->left, x);
    else if (x > root->data) root->right = insert(root->right, x);
    else printf("%d already exists\n", x);          /* duplicates ignored */
    return root;
}

struct node *search(struct node *root, int key) {   /* iterative, O(h) */
    while (root != NULL && root->data != key)
        root = (key < root->data) ? root->left : root->right;
    return root;
}

struct node *findMin(struct node *r) { while (r && r->left)  r = r->left;  return r; }
struct node *findMax(struct node *r) { while (r && r->right) r = r->right; return r; }

struct node *deleteNode(struct node *root, int key) {
    struct node *temp;
    if (root == NULL) { printf("%d not found\n", key); return NULL; }
    if (key < root->data)      root->left  = deleteNode(root->left, key);
    else if (key > root->data) root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) {            /* case 1 (leaf) and case 2 (only right child) */
            temp = root->right; free(root); return temp;
        }
        if (root->right == NULL) {           /* case 2 (only left child) */
            temp = root->left; free(root); return temp;
        }
        temp = findMin(root->right);         /* case 3: in-order successor */
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

void inorder(struct node *r)   { if (r) { inorder(r->left); printf("%d ", r->data); inorder(r->right); } }
void preorder(struct node *r)  { if (r) { printf("%d ", r->data); preorder(r->left); preorder(r->right); } }
void postorder(struct node *r) { if (r) { postorder(r->left); postorder(r->right); printf("%d ", r->data); } }

int main(void) {
    struct node *root = NULL, *p;
    int ch, x, n, i;
    while (1) {
        printf("\n1.Insert many 2.Search 3.Delete 4.Min/Max 5.Traversals 6.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many keys? "); scanf("%d", &n);
                printf("Enter %d keys: ", n);
                for (i = 0; i < n; i++) { scanf("%d", &x); root = insert(root, x); }
                break;
        case 2: printf("Key: "); scanf("%d", &x);
                printf(search(root, x) ? "Found\n" : "Not found\n"); break;
        case 3: printf("Key: "); scanf("%d", &x); root = deleteNode(root, x); break;
        case 4: if (root == NULL) { printf("Empty\n"); break; }
                p = findMin(root); printf("Min=%d ", p->data);
                p = findMax(root); printf("Max=%d\n", p->data); break;
        case 5: printf("In   : "); inorder(root);
                printf("\nPre  : "); preorder(root);
                printf("\nPost : "); postorder(root); printf("\n"); break;
        case 6: return 0;
        }
    }
    return 0;
}

/* m-way search tree (order M): node structure, search, insert, delete, in-order */
#include <stdio.h>
#include <stdlib.h>
#define M 3                      /* order: at most M children, M-1 keys */

struct mnode {
    int count;                   /* number of keys in use */
    int key[M - 1];              /* key[0] < key[1] < ... */
    struct mnode *child[M];      /* child[i] holds keys between key[i-1] and key[i] */
};

struct mnode *newNode(int x) {
    int i;
    struct mnode *n = (struct mnode *)malloc(sizeof(struct mnode));
    n->count = 1;
    n->key[0] = x;
    for (i = 0; i < M; i++) n->child[i] = NULL;
    return n;
}

/* position of the first key >= x inside one node */
int slot(struct mnode *n, int x) {
    int i = 0;
    while (i < n->count && x > n->key[i]) i++;
    return i;
}

struct mnode *search(struct mnode *root, int x) {
    int i;
    while (root != NULL) {
        i = slot(root, x);
        if (i < root->count && root->key[i] == x) return root;
        root = root->child[i];   /* one pointer per gap between keys */
    }
    return NULL;
}

/* fill a node up to M-1 keys; otherwise go down (creating a new child if needed) */
struct mnode *insert(struct mnode *root, int x) {
    struct mnode *n = root;
    int i, j;
    if (root == NULL) return newNode(x);
    while (1) {
        i = slot(n, x);
        if (i < n->count && n->key[i] == x) return root;          /* duplicate */
        if (n->count < M - 1 && n->child[i] == NULL) {            /* room here */
            for (j = n->count; j > i; j--) {
                n->key[j] = n->key[j - 1];
                n->child[j + 1] = n->child[j];
            }
            n->key[i] = x;
            n->child[i + 1] = NULL;
            n->count++;
            return root;
        }
        if (n->child[i] == NULL) { n->child[i] = newNode(x); return root; }
        n = n->child[i];
    }
}

/* delete x from the subtree rooted at n; returns the (possibly NULL) new subtree root */
struct mnode *deleteKey(struct mnode *n, int x) {
    int i, j, rep;
    struct mnode *t;
    if (n == NULL) { printf("%d not found\n", x); return NULL; }
    i = slot(n, x);
    if (i == n->count || n->key[i] != x) {         /* not in this node: go down */
        n->child[i] = deleteKey(n->child[i], x);
        return n;
    }
    if (n->child[i] == NULL && n->child[i + 1] == NULL) {   /* both side pointers NULL */
        for (j = i; j < n->count - 1; j++) {
            n->key[j] = n->key[j + 1];
            n->child[j + 1] = n->child[j + 2];
        }
        n->child[n->count] = NULL;
        n->count--;
        if (n->count == 0) { free(n); return NULL; }    /* node became empty */
        return n;
    }
    if (n->child[i] != NULL) {                     /* replace by largest key on the left */
        t = n->child[i];
        while (t->child[t->count] != NULL) t = t->child[t->count];
        rep = t->key[t->count - 1];
        n->key[i] = rep;
        n->child[i] = deleteKey(n->child[i], rep);
    } else {                                       /* replace by smallest key on the right */
        t = n->child[i + 1];
        while (t->child[0] != NULL) t = t->child[0];
        rep = t->key[0];
        n->key[i] = rep;
        n->child[i + 1] = deleteKey(n->child[i + 1], rep);
    }
    return n;
}

void show(struct mnode *n) {                    /* [keys](children), _ = NULL */
    int i, any = 0;
    if (n == NULL) { printf("_"); return; }
    printf("[");
    for (i = 0; i < n->count; i++) printf(i ? ",%d" : "%d", n->key[i]);
    printf("]");
    for (i = 0; i <= n->count; i++) if (n->child[i]) any = 1;
    if (any) {
        printf("(");
        for (i = 0; i <= n->count; i++) { if (i) printf(" "); show(n->child[i]); }
        printf(")");
    }
}

void inorder(struct mnode *n) {                 /* prints keys in sorted order */
    int i;
    if (n == NULL) return;
    for (i = 0; i < n->count; i++) {
        inorder(n->child[i]);
        printf("%d ", n->key[i]);
    }
    inorder(n->child[n->count]);
}

int main(void) {
    struct mnode *root = NULL;
    int ch, n, i, x;
    while (1) {
        printf("\n1.Insert many 2.Search 3.Delete 4.Show 5.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &n); printf("Keys: ");
                for (i = 0; i < n; i++) { scanf("%d", &x); root = insert(root, x); } break;
        case 2: printf("Key: "); scanf("%d", &x); printf(search(root, x) ? "Found\n" : "Not found\n"); break;
        case 3: printf("Key: "); scanf("%d", &x); root = deleteKey(root, x); break;
        case 4: printf("Tree: "); show(root); printf("\nIn-order: "); inorder(root); printf("\n"); break;
        case 5: return 0;
        }
    }
    return 0;
}

/* B-Tree of order M: search, insert (split at median), delete (borrow / merge), traversal */
#include <stdio.h>
#include <stdlib.h>
#define M 3                         /* order: max M children, max M-1 keys        */
#define MIN ((M + 1) / 2 - 1)       /* min keys in a non-root node = ceil(M/2) - 1 */

struct bnode {
    int n;                          /* keys in use                                 */
    int key[M];                     /* one extra slot to hold a temporary overflow */
    struct bnode *child[M + 1];
    int leaf;
};

struct bnode *root = NULL;

struct bnode *newNode(int leaf) {
    int i;
    struct bnode *t = (struct bnode *)malloc(sizeof(struct bnode));
    t->n = 0; t->leaf = leaf;
    for (i = 0; i <= M; i++) t->child[i] = NULL;
    return t;
}

int slot(struct bnode *t, int x) { int i = 0; while (i < t->n && x > t->key[i]) i++; return i; }

struct bnode *search(struct bnode *t, int x) {
    int i;
    while (t) {
        i = slot(t, x);
        if (i < t->n && t->key[i] == x) return t;
        if (t->leaf) return NULL;
        t = t->child[i];
    }
    return NULL;
}

/* split overflowing child c = p->child[i] (it holds M keys) around its median */
void splitChild(struct bnode *p, int i) {
    struct bnode *c = p->child[i], *r = newNode(c->leaf);
    int mid = (M + 1) / 2 - 1, j;             /* median index = ceil(M/2) - 1 */
    r->n = c->n - mid - 1;
    for (j = 0; j < r->n; j++) r->key[j] = c->key[mid + 1 + j];
    if (!c->leaf) for (j = 0; j <= r->n; j++) r->child[j] = c->child[mid + 1 + j];
    for (j = p->n; j > i; j--) { p->key[j] = p->key[j - 1]; p->child[j + 1] = p->child[j]; }
    p->key[i] = c->key[mid];                  /* median moves up */
    p->child[i + 1] = r;
    p->n++;
    c->n = mid;
}

/* insert into subtree t; the caller splits t if it overflows */
void insertRec(struct bnode *t, int x) {
    int i = slot(t, x), j;
    if (i < t->n && t->key[i] == x) return;   /* duplicate */
    if (t->leaf) {
        for (j = t->n; j > i; j--) t->key[j] = t->key[j - 1];
        t->key[i] = x; t->n++;
        return;
    }
    insertRec(t->child[i], x);
    if (t->child[i]->n == M) splitChild(t, i);
}

void insert(int x) {
    struct bnode *s;
    if (root == NULL) { root = newNode(1); root->key[0] = x; root->n = 1; return; }
    insertRec(root, x);
    if (root->n == M) {                       /* root overflow: tree grows at the top */
        s = newNode(0); s->child[0] = root; root = s;
        splitChild(s, 0);
    }
}

/* ---------- delete ---------- */
void removeAt(struct bnode *t, int i) {       /* remove key i and child i+1 */
    int j;
    for (j = i; j < t->n - 1; j++) { t->key[j] = t->key[j + 1]; t->child[j + 1] = t->child[j + 2]; }
    t->n--;
}

/* child p->child[i] has MIN-1 keys: borrow from a sibling or merge */
void fix(struct bnode *p, int i) {
    struct bnode *c = p->child[i], *L, *R;
    int j;
    L = (i > 0) ? p->child[i - 1] : NULL;
    R = (i < p->n) ? p->child[i + 1] : NULL;
    if (L && L->n > MIN) {                    /* borrow from left */
        for (j = c->n; j > 0; j--) c->key[j] = c->key[j - 1];
        if (!c->leaf) for (j = c->n + 1; j > 0; j--) c->child[j] = c->child[j - 1];
        c->key[0] = p->key[i - 1];
        if (!c->leaf) c->child[0] = L->child[L->n];
        p->key[i - 1] = L->key[L->n - 1];
        L->n--; c->n++;
    } else if (R && R->n > MIN) {             /* borrow from right */
        c->key[c->n] = p->key[i];
        if (!c->leaf) c->child[c->n + 1] = R->child[0];
        c->n++;
        p->key[i] = R->key[0];
        for (j = 0; j < R->n - 1; j++) R->key[j] = R->key[j + 1];
        if (!R->leaf) for (j = 0; j < R->n; j++) R->child[j] = R->child[j + 1];
        R->n--;
    } else {                                  /* merge with a sibling */
        if (L) { c = L; R = p->child[i]; i--; }  /* merge child[i] and child[i+1] */
        c->key[c->n] = p->key[i];
        for (j = 0; j < R->n; j++) c->key[c->n + 1 + j] = R->key[j];
        if (!c->leaf) for (j = 0; j <= R->n; j++) c->child[c->n + 1 + j] = R->child[j];
        c->n += R->n + 1;
        free(R);
        removeAt(p, i);
    }
}

void deleteRec(struct bnode *t, int x) {
    int i = slot(t, x);
    struct bnode *s;
    if (i < t->n && t->key[i] == x) {
        if (t->leaf) { for (; i < t->n - 1; i++) t->key[i] = t->key[i + 1]; t->n--; return; }
        s = t->child[i + 1];                  /* internal: use the in-order successor */
        while (!s->leaf) s = s->child[0];
        t->key[i] = s->key[0];
        x = s->key[0];
        i = i + 1;                            /* now delete the successor from the right subtree */
    } else if (t->leaf) { printf("%d not found\n", x); return; }
    deleteRec(t->child[i], x);
    if (t->child[i]->n < MIN) fix(t, i);
}

void deleteKey(int x) {
    struct bnode *old;
    if (root == NULL) return;
    deleteRec(root, x);
    if (root->n == 0) {                       /* root emptied: tree shrinks */
        old = root;
        root = root->leaf ? NULL : root->child[0];
        free(old);
    }
}

void inorder(struct bnode *t) {
    int i;
    if (!t) return;
    for (i = 0; i < t->n; i++) { if (!t->leaf) inorder(t->child[i]); printf("%d ", t->key[i]); }
    if (!t->leaf) inorder(t->child[t->n]);
}

void show(struct bnode *t, int level) {       /* one line per node, indented by level */
    int i;
    if (!t) return;
    printf("%*s[", level * 4, "");
    for (i = 0; i < t->n; i++) printf(i ? " %d" : "%d", t->key[i]);
    printf("]\n");
    if (!t->leaf) for (i = 0; i <= t->n; i++) show(t->child[i], level + 1);
}

int main(void) {
    int ch, x, n, i;
    while (1) {
        printf("\n1.Insert many 2.Search 3.Delete 4.Show 5.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &n); printf("Keys: ");
                for (i = 0; i < n; i++) { scanf("%d", &x); insert(x); } break;
        case 2: printf("Key: "); scanf("%d", &x); printf(search(root, x) ? "Found\n" : "Not found\n"); break;
        case 3: printf("Key: "); scanf("%d", &x); deleteKey(x); break;
        case 4: show(root, 0); printf("In-order: "); inorder(root); printf("\n"); break;
        case 5: return 0;
        }
    }
    return 0;
}

/* B+ tree of order M: insert (leaf split copies up, index split moves up), search, range query */
#include <stdio.h>
#include <stdlib.h>
#define M 4                               /* order: at most M children, M-1 keys */

struct bp {
    int leaf, n;
    int key[M];                           /* one spare slot holds a key during an overflow */
    struct bp *child[M + 1];
    struct bp *next;                      /* leaves only: the leaf to the right */
};
struct bp *root = NULL;

struct bp *newNode(int leaf) { struct bp *t = calloc(1, sizeof *t); t->leaf = leaf; return t; }

/* insert x below t; if t splits, return 1 and give back the key and node for the parent */
int insertRec(struct bp *t, int x, int *upKey, struct bp **upNode) {
    int i, j, mid, k;
    struct bp *r, *nr;
    if (t->leaf) {
        for (i = 0; i < t->n && t->key[i] < x; i++) ;
        if (i < t->n && t->key[i] == x) return 0;            /* duplicate */
        for (j = t->n; j > i; j--) t->key[j] = t->key[j - 1];
        t->key[i] = x; t->n++;
        if (t->n < M) return 0;                               /* no overflow */
        mid = (M + 1) / 2;                                    /* left leaf keeps ceil(M/2) keys */
        r = newNode(1);
        for (j = mid; j < t->n; j++) r->key[r->n++] = t->key[j];
        t->n = mid;
        r->next = t->next; t->next = r;                       /* link the new leaf in */
        *upKey = r->key[0];                                   /* COPY the first key up */
        *upNode = r;
        return 1;
    }
    for (i = 0; i < t->n && x >= t->key[i]; i++) ;            /* equal keys go right */
    if (!insertRec(t->child[i], x, &k, &nr)) return 0;
    for (j = t->n; j > i; j--) { t->key[j] = t->key[j - 1]; t->child[j + 1] = t->child[j]; }
    t->key[i] = k; t->child[i + 1] = nr; t->n++;
    if (t->n < M) return 0;
    mid = (M + 1) / 2 - 1;                                    /* median of the index node */
    r = newNode(0);
    for (j = mid + 1; j < t->n; j++) { r->key[r->n] = t->key[j]; r->child[r->n] = t->child[j]; r->n++; }
    r->child[r->n] = t->child[t->n];
    *upKey = t->key[mid];                                     /* MOVE the median up */
    *upNode = r;
    t->n = mid;
    return 1;
}
void insert(int x) {
    int k;
    struct bp *nr, *s;
    if (root == NULL) { root = newNode(1); root->key[0] = x; root->n = 1; return; }
    if (insertRec(root, x, &k, &nr)) {                        /* the root split: grow at the top */
        s = newNode(0);
        s->key[0] = k; s->child[0] = root; s->child[1] = nr; s->n = 1;
        root = s;
    }
}

struct bp *findLeaf(int x) {
    struct bp *t = root;
    int i;
    while (!t->leaf) {
        for (i = 0; i < t->n && x >= t->key[i]; i++) ;
        t = t->child[i];
    }
    return t;
}
int search(int x) {
    struct bp *L;
    int i;
    if (root == NULL) return 0;
    L = findLeaf(x);                                          /* every search ends in a leaf */
    for (i = 0; i < L->n; i++) if (L->key[i] == x) return 1;
    return 0;
}
void range(int lo, int hi) {
    struct bp *L;
    int i;
    if (root == NULL) return;
    for (L = findLeaf(lo); L != NULL; L = L->next)            /* one descent, then walk right */
        for (i = 0; i < L->n; i++) {
            if (L->key[i] > hi) return;
            if (L->key[i] >= lo) printf("%d ", L->key[i]);
        }
}
void show(void) {                                             /* level by level, then the leaf chain */
    struct bp *q[200], *t;
    int f = 0, b = 0, i, lv = 0, cnt;
    if (root == NULL) { printf("empty\n"); return; }
    q[b++] = root;
    while (f < b) {
        cnt = b - f;
        printf("Level %d: ", lv++);
        while (cnt--) {
            t = q[f++];
            printf("[");
            for (i = 0; i < t->n; i++) printf(i ? " %d" : "%d", t->key[i]);
            printf("] ");
            if (!t->leaf) for (i = 0; i <= t->n; i++) q[b++] = t->child[i];
        }
        printf("\n");
    }
    printf("Leaf chain: ");
    for (t = findLeaf(-2147483647); t != NULL; t = t->next) {
        printf("[");
        for (i = 0; i < t->n; i++) printf(i ? " %d" : "%d", t->key[i]);
        printf(t->next ? "] -> " : "]\n");
    }
}

int main(void) {
    int ch, k, i, x, y;
    while (1) {
        printf("\n1.Insert many 2.Search 3.Range 4.Show 5.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &k); printf("Keys: ");
                for (i = 0; i < k; i++) { scanf("%d", &x); insert(x); } break;
        case 2: printf("Key: "); scanf("%d", &x); printf(search(x) ? "Found in a leaf\n" : "Not found\n"); break;
        case 3: printf("Low and high: "); scanf("%d %d", &x, &y); printf("Keys: "); range(x, y); printf("\n"); break;
        case 4: show(); break;
        case 5: return 0;
        }
    }
    return 0;
}

/* AVL Tree: insert and delete with LL, RR, LR, RL rotations; prints balance factors */
#include <stdio.h>
#include <stdlib.h>

struct node {
    int data, height;               /* height in edges: leaf = 0, NULL = -1 */
    struct node *left, *right;
};

int h(struct node *n)  { return n ? n->height : -1; }
int max(int a, int b)  { return a > b ? a : b; }
void update(struct node *n) { n->height = 1 + max(h(n->left), h(n->right)); }
int BF(struct node *n) { return n ? h(n->left) - h(n->right) : 0; }

struct node *createNode(int x) {
    struct node *n = (struct node *)malloc(sizeof(struct node));
    n->data = x; n->height = 0;
    n->left = n->right = NULL;
    return n;
}

struct node *rightRotate(struct node *y) {     /* fixes LL */
    struct node *x = y->left, *T2 = x->right;
    x->right = y;
    y->left = T2;
    update(y); update(x);                     /* y first: it is now below x */
    return x;
}

struct node *leftRotate(struct node *x) {      /* fixes RR */
    struct node *y = x->right, *T2 = y->left;
    y->left = x;
    x->right = T2;
    update(x); update(y);
    return y;
}

/* called on every node on the way back up */
struct node *balance(struct node *n) {
    update(n);
    if (BF(n) > 1) {
        if (BF(n->left) < 0) {                 /* LR */
            printf("  LR at %d\n", n->data);
            n->left = leftRotate(n->left);
        } else printf("  LL at %d\n", n->data);
        return rightRotate(n);
    }
    if (BF(n) < -1) {
        if (BF(n->right) > 0) {                /* RL */
            printf("  RL at %d\n", n->data);
            n->right = rightRotate(n->right);
        } else printf("  RR at %d\n", n->data);
        return leftRotate(n);
    }
    return n;
}

struct node *insert(struct node *n, int x) {
    if (n == NULL) return createNode(x);
    if (x < n->data)      n->left  = insert(n->left, x);
    else if (x > n->data) n->right = insert(n->right, x);
    else return n;                              /* duplicate */
    return balance(n);
}

struct node *deleteNode(struct node *n, int x) {
    struct node *t;
    if (n == NULL) { printf("%d not found\n", x); return NULL; }
    if (x < n->data)      n->left  = deleteNode(n->left, x);
    else if (x > n->data) n->right = deleteNode(n->right, x);
    else {
        if (n->left == NULL || n->right == NULL) {
            t = n->left ? n->left : n->right;
            free(n);
            return t;                           /* NULL for a leaf */
        }
        t = n->right;                           /* in-order successor */
        while (t->left) t = t->left;
        n->data = t->data;
        n->right = deleteNode(n->right, t->data);
    }
    return balance(n);
}

void preorder(struct node *r) {                 /* key(BF) */
    if (r) { printf("%d(%d) ", r->data, BF(r)); preorder(r->left); preorder(r->right); }
}
void inorder(struct node *r) { if (r) { inorder(r->left); printf("%d ", r->data); inorder(r->right); } }

int main(void) {
    struct node *root = NULL;
    int ch, x, n, i;
    while (1) {
        printf("\n1.Insert many 2.Delete 3.Show 4.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &n); printf("Keys: ");
                for (i = 0; i < n; i++) { scanf("%d", &x); root = insert(root, x); } break;
        case 2: printf("Key: "); scanf("%d", &x); root = deleteNode(root, x); break;
        case 3: printf("Pre-order key(BF): "); preorder(root);
                printf("\nIn-order: "); inorder(root);
                printf("\nHeight of tree: %d\n", h(root)); break;
        case 4: return 0;
        }
    }
    return 0;
}

/* Binary max-heap in an array: insert, delete max, build heap (bottom-up), heap sort */
#include <stdio.h>
#define MAX 100

int heap[MAX], n = 0;                 /* heap[0..n-1]; children of i: 2i+1, 2i+2 */

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* move a[i] up while it is larger than its parent */
void heapifyUp(int a[], int i) {
    while (i > 0 && a[(i - 1) / 2] < a[i]) {
        swap(&a[i], &a[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
/* move a[i] down while a child is larger (only the first size elements count) */
void heapifyDown(int a[], int size, int i) {
    int l, r, big;
    while (1) {
        l = 2 * i + 1; r = 2 * i + 2; big = i;
        if (l < size && a[l] > a[big]) big = l;
        if (r < size && a[r] > a[big]) big = r;
        if (big == i) return;
        swap(&a[i], &a[big]);
        i = big;
    }
}

void insert(int x) {
    if (n == MAX) { printf("Heap is full\n"); return; }
    heap[n] = x;                      /* next free position keeps the tree complete */
    heapifyUp(heap, n);
    n++;
}
int deleteMax(void) {
    int top = heap[0];
    heap[0] = heap[n - 1];            /* last element moves to the root */
    n--;
    heapifyDown(heap, n, 0);
    return top;
}
/* Floyd's method: heapify every internal node from the last one up to the root: O(n) */
void buildHeap(int a[], int size) {
    int i;
    for (i = size / 2 - 1; i >= 0; i--) heapifyDown(a, size, i);
}
void heapSort(int a[], int size) {
    int end;
    buildHeap(a, size);
    for (end = size - 1; end > 0; end--) {
        swap(&a[0], &a[end]);         /* largest goes to the end */
        heapifyDown(a, end, 0);       /* restore the heap on the rest */
    }
}
void show(int a[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", a[i]); printf("\n"); }

int main(void) {
    int ch, x, k, i, a[MAX];
    while (1) {
        printf("\n1.Insert many 2.Delete max 3.Display 4.Build heap from array 5.Heap sort 6.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &k); printf("Keys: ");
                for (i = 0; i < k; i++) { scanf("%d", &x); insert(x); } break;
        case 2: if (n == 0) printf("Heap is empty\n"); else printf("Deleted %d\n", deleteMax()); break;
        case 3: printf("Heap array: "); show(heap, n); break;
        case 4: case 5:
                printf("How many? "); scanf("%d", &k); printf("Array: ");
                for (i = 0; i < k; i++) scanf("%d", &a[i]);
                if (ch == 4) { buildHeap(a, k); printf("As a max-heap: "); }
                else { heapSort(a, k); printf("Sorted: "); }
                show(a, k); break;
        case 6: return 0;
        }
    }
    return 0;
}

/* In-threaded binary search tree: insert, search, delete, in-order and pre-order without stack or recursion */
#include <stdio.h>
#include <stdlib.h>

struct tnode {
    int data;
    struct tnode *left, *right;
    int lthread;          /* 1: left  is a thread to the in-order predecessor (or NULL) */
    int rthread;          /* 1: right is a thread to the in-order successor  (or NULL) */
};

struct tnode *insert(struct tnode *root, int x) {
    struct tnode *p = root, *par = NULL, *n;
    while (p != NULL) {                              /* ordinary BST walk ...            */
        if (x == p->data) { printf("%d already exists\n", x); return root; }
        par = p;
        if (x < p->data) { if (p->lthread) break; p = p->left; }   /* ... that stops at a thread */
        else             { if (p->rthread) break; p = p->right; }
    }
    n = malloc(sizeof *n);
    n->data = x; n->lthread = n->rthread = 1;        /* a new node is a leaf: both links are threads */
    if (par == NULL) { n->left = n->right = NULL; return n; }
    if (x < par->data) {
        n->left = par->left;                         /* inherit par's predecessor thread */
        n->right = par;                              /* successor of n is par            */
        par->lthread = 0; par->left = n;
    } else {
        n->right = par->right;                       /* inherit par's successor thread   */
        n->left = par;                               /* predecessor of n is par          */
        par->rthread = 0; par->right = n;
    }
    return root;
}

struct tnode *leftmost(struct tnode *n) {
    while (n != NULL && n->lthread == 0) n = n->left;
    return n;
}
void inorder(struct tnode *root) {
    struct tnode *p = leftmost(root);
    while (p != NULL) {
        printf("%d ", p->data);
        if (p->rthread) p = p->right;                /* follow the thread to the successor */
        else p = leftmost(p->right);                 /* or go to the right subtree's leftmost */
    }
    printf("\n");
}
void preorder(struct tnode *root) {
    struct tnode *p = root;
    while (p != NULL) {
        printf("%d ", p->data);
        if (p->lthread == 0) p = p->left;            /* a real left child comes next */
        else {
            while (p != NULL && p->rthread) p = p->right;   /* climb by threads ... */
            if (p != NULL) p = p->right;                     /* ... to the next right subtree */
        }
    }
    printf("\n");
}
struct tnode *inSucc(struct tnode *p) {             /* in-order successor */
    return p->rthread ? p->right : leftmost(p->right);
}
struct tnode *inPred(struct tnode *p) {             /* in-order predecessor */
    if (p->lthread) return p->left;
    p = p->left;
    while (p->rthread == 0) p = p->right;           /* rightmost node of the left subtree */
    return p;
}
struct tnode *search(struct tnode *root, int x) {
    struct tnode *p = root;
    while (p != NULL) {
        if (x == p->data) return p;
        if (x < p->data) { if (p->lthread) return NULL; p = p->left; }   /* a thread: no child there */
        else             { if (p->rthread) return NULL; p = p->right; }
    }
    return NULL;
}
struct tnode *delete(struct tnode *root, int x) {
    struct tnode *par = NULL, *p = root, *s, *ps, *child;
    while (p != NULL && p->data != x) {             /* find the node and its parent */
        par = p;
        if (x < p->data) p = p->lthread ? NULL : p->left;
        else             p = p->rthread ? NULL : p->right;
    }
    if (p == NULL) { printf("%d not found\n", x); return root; }
    if (p->lthread == 0 && p->rthread == 0) {       /* two children: copy the successor ... */
        ps = p; s = p->right;
        while (s->lthread == 0) { ps = s; s = s->left; }
        p->data = s->data;
        p = s; par = ps;                            /* ... and delete it (it has no left child) */
    }
    if (p->lthread && p->rthread) {                 /* leaf: the parent's link becomes a thread */
        if (par == NULL) root = NULL;
        else if (p == par->left) { par->lthread = 1; par->left = p->left; }
        else                     { par->rthread = 1; par->right = p->right; }
    } else {                                        /* one child: it takes p's place */
        struct tnode *pr = inPred(p), *sc = inSucc(p);
        child = p->lthread ? p->right : p->left;
        if (par == NULL) root = child;
        else if (p == par->left) par->left = child;
        else par->right = child;
        if (p->lthread == 0) pr->right = sc;        /* pred's thread pointed to p: move it on */
        else sc->left = pr;                         /* succ's thread pointed to p: move it back */
    }
    free(p);
    return root;
}
void links(struct tnode *root) {
    struct tnode *p = leftmost(root);
    while (p != NULL) {
        printf("%3d: left = ", p->data);
        if (p->lthread) printf(p->left ? "thread to %-4d" : "NULL          ", p->left ? p->left->data : 0);
        else printf("child %-7d ", p->left->data);
        printf(" right = ");
        if (p->rthread) { if (p->right) printf("thread to %d\n", p->right->data); else printf("NULL\n"); }
        else printf("child %d\n", p->right->data);
        p = p->rthread ? p->right : leftmost(p->right);
    }
}

int main(void) {
    struct tnode *root = NULL;
    int ch, k, i, x;
    while (1) {
        printf("\n1.Insert many 2.In-order 3.Pre-order 4.Show every link 5.Search 6.Delete 7.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &k); printf("Keys: ");
                for (i = 0; i < k; i++) { scanf("%d", &x); root = insert(root, x); } break;
        case 2: printf("In-order (threads, no stack): "); inorder(root); break;
        case 3: printf("Pre-order (threads, no stack): "); preorder(root); break;
        case 4: links(root); break;
        case 5: printf("Key: "); scanf("%d", &x);
                printf(search(root, x) ? "%d found\n" : "%d not found\n", x); break;
        case 6: printf("Key: "); scanf("%d", &x); root = delete(root, x); break;
        case 7: return 0;
        }
    }
    return 0;
}

/* Red-black tree: insert, search and delete with recolouring and rotations, plus a rule check */
#include <stdio.h>
#include <stdlib.h>
#define RED 0
#define BLACK 1

struct node { int data, color; struct node *left, *right, *parent; };
struct node *root = NULL;

void rotateLeft(struct node *x) {
    struct node *y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL) root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x; x->parent = y;
}
void rotateRight(struct node *x) {
    struct node *y = x->left;
    x->left = y->right;
    if (y->right) y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL) root = y;
    else if (x == x->parent->right) x->parent->right = y;
    else x->parent->left = y;
    y->right = x; x->parent = y;
}

void fixInsert(struct node *z) {
    struct node *p, *g, *u;
    while (z != root && z->parent->color == RED) {
        p = z->parent; g = p->parent;
        if (p == g->left) {
            u = g->right;
            if (u != NULL && u->color == RED) {              /* case 1: red uncle */
                printf("  case 1 at %d: recolour\n", z->data);
                p->color = BLACK; u->color = BLACK; g->color = RED;
                z = g;
            } else {
                if (z == p->right) {                         /* case 2: inner child */
                    printf("  case 2 at %d: rotate left at %d\n", z->data, p->data);
                    z = p; rotateLeft(z); p = z->parent;
                }
                printf("  case 3 at %d: rotate right at %d\n", z->data, g->data);
                p->color = BLACK; g->color = RED;            /* case 3: outer child */
                rotateRight(g);
            }
        } else {                                              /* mirror image */
            u = g->left;
            if (u != NULL && u->color == RED) {
                printf("  case 1 at %d: recolour\n", z->data);
                p->color = BLACK; u->color = BLACK; g->color = RED;
                z = g;
            } else {
                if (z == p->left) {
                    printf("  case 2 at %d: rotate right at %d\n", z->data, p->data);
                    z = p; rotateRight(z); p = z->parent;
                }
                printf("  case 3 at %d: rotate left at %d\n", z->data, g->data);
                p->color = BLACK; g->color = RED;
                rotateLeft(g);
            }
        }
    }
    root->color = BLACK;                                      /* the root is always black */
}

void insert(int x) {
    struct node *y = NULL, *t = root, *z;
    while (t != NULL) {                                       /* ordinary BST insert */
        y = t;
        if (x == t->data) { printf("%d already exists\n", x); return; }
        t = x < t->data ? t->left : t->right;
    }
    z = malloc(sizeof *z);
    z->data = x; z->color = RED; z->left = z->right = NULL; z->parent = y;
    if (y == NULL) root = z;
    else if (x < y->data) y->left = z;
    else y->right = z;
    fixInsert(z);
}

struct node *search(int x) {
    struct node *t = root;
    while (t != NULL && t->data != x) t = x < t->data ? t->left : t->right;
    return t;
}
int colourOf(struct node *n) { return n == NULL ? BLACK : n->color; }   /* NIL leaves are black */

/* put subtree v in the place of subtree u */
void transplant(struct node *u, struct node *v) {
    if (u->parent == NULL) root = v;
    else if (u == u->parent->left) u->parent->left = v;
    else u->parent->right = v;
    if (v != NULL) v->parent = u->parent;
}
/* x carries an extra black ("double black"); xp is its parent, because x may be NULL */
void fixDelete(struct node *x, struct node *xp) {
    struct node *w;
    while (x != root && colourOf(x) == BLACK) {
        if (x == xp->left) {
            w = xp->right;                                    /* sibling */
            if (colourOf(w) == RED) {                         /* case 1: red sibling */
                printf("  case 1: sibling %d is red, rotate left at %d\n", w->data, xp->data);
                w->color = BLACK; xp->color = RED; rotateLeft(xp); w = xp->right;
            }
            if (colourOf(w->left) == BLACK && colourOf(w->right) == BLACK) {
                printf("  case 2: sibling %d has two black children, recolour it\n", w->data);
                w->color = RED; x = xp; xp = x->parent;       /* case 2: move the extra black up */
            } else {
                if (colourOf(w->right) == BLACK) {            /* case 3: near child red */
                    printf("  case 3: rotate right at sibling %d\n", w->data);
                    w->left->color = BLACK; w->color = RED; rotateRight(w); w = xp->right;
                }
                printf("  case 4: rotate left at %d\n", xp->data);
                w->color = xp->color; xp->color = BLACK;      /* case 4: far child red */
                w->right->color = BLACK; rotateLeft(xp);
                x = root; xp = NULL;
            }
        } else {                                              /* mirror image */
            w = xp->left;
            if (colourOf(w) == RED) {
                printf("  case 1: sibling %d is red, rotate right at %d\n", w->data, xp->data);
                w->color = BLACK; xp->color = RED; rotateRight(xp); w = xp->left;
            }
            if (colourOf(w->left) == BLACK && colourOf(w->right) == BLACK) {
                printf("  case 2: sibling %d has two black children, recolour it\n", w->data);
                w->color = RED; x = xp; xp = x->parent;
            } else {
                if (colourOf(w->left) == BLACK) {
                    printf("  case 3: rotate left at sibling %d\n", w->data);
                    w->right->color = BLACK; w->color = RED; rotateLeft(w); w = xp->left;
                }
                printf("  case 4: rotate right at %d\n", xp->data);
                w->color = xp->color; xp->color = BLACK;
                w->left->color = BLACK; rotateRight(xp);
                x = root; xp = NULL;
            }
        }
    }
    if (x != NULL) x->color = BLACK;
}
void delete(int k) {
    struct node *z = search(k), *y, *x, *xp;
    int yColour;
    if (z == NULL) { printf("%d not found\n", k); return; }
    y = z; yColour = y->color;
    if (z->left == NULL) { x = z->right; xp = z->parent; transplant(z, z->right); }
    else if (z->right == NULL) { x = z->left; xp = z->parent; transplant(z, z->left); }
    else {                                                    /* two children: use the successor y */
        y = z->right; while (y->left != NULL) y = y->left;
        yColour = y->color; x = y->right;
        if (y->parent == z) xp = y;
        else { xp = y->parent; transplant(y, y->right); y->right = z->right; y->right->parent = y; }
        transplant(z, y); y->left = z->left; y->left->parent = y; y->color = z->color;
    }
    free(z);
    if (yColour == BLACK) fixDelete(x, xp);                   /* removing a red node breaks nothing */
}

/* returns the black-height, or -1 if a rule is broken below r */
int check(struct node *r) {
    int l, rt;
    if (r == NULL) return 1;                                  /* NULL leaves are black */
    if (r->color == RED && ((r->left && r->left->color == RED) || (r->right && r->right->color == RED))) return -1;
    l = check(r->left); rt = check(r->right);
    if (l == -1 || rt == -1 || l != rt) return -1;
    return l + (r->color == BLACK);
}
void preorder(struct node *r) {
    if (r == NULL) return;
    printf("%d%s ", r->data, r->color == RED ? "(R)" : "(B)");
    preorder(r->left); preorder(r->right);
}

int main(void) {
    int ch, k, i, x;
    while (1) {
        printf("\n1.Insert many 2.Show 3.Search 4.Delete 5.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &k); printf("Keys: ");
                for (i = 0; i < k; i++) { scanf("%d", &x); printf("Insert %d\n", x); insert(x); } break;
        case 2: printf("Pre-order: "); preorder(root);
                x = check(root);
                if (x == -1) printf("\nRed-black rules broken!\n");
                else printf("\nAll rules hold. Black-height (counting NULL leaves) = %d\n", x);
                break;
        case 3: printf("Key: "); scanf("%d", &x);
                printf(search(x) ? "%d found\n" : "%d not found\n", x); break;
        case 4: printf("Key: "); scanf("%d", &x); printf("Delete %d\n", x); delete(x); break;
        case 5: return 0;
        }
    }
    return 0;
}

/* Splay tree: every search, insert and delete moves the accessed key to the root */
#include <stdio.h>
#include <stdlib.h>

struct node { int data; struct node *left, *right, *parent; };
struct node *root = NULL;

void rotate(struct node *x) {                    /* lift x one level above its parent p */
    struct node *p = x->parent, *g = p->parent;
    if (x == p->left) { p->left = x->right; if (x->right) x->right->parent = p; x->right = p; }
    else              { p->right = x->left; if (x->left) x->left->parent = p; x->left = p; }
    p->parent = x; x->parent = g;
    if (g == NULL) root = x;
    else if (g->left == p) g->left = x;
    else g->right = x;
}
void splay(struct node *x) {
    struct node *p, *g;
    while (x->parent != NULL) {
        p = x->parent; g = p->parent;
        if (g == NULL) { printf("  zig at %d\n", p->data); rotate(x); }
        else if ((x == p->left) == (p == g->left)) {  /* same side: straight line */
            printf("  zig-zig at %d\n", g->data); rotate(p); rotate(x);
        } else {                                      /* opposite sides: zig-zag  */
            printf("  zig-zag at %d\n", g->data); rotate(x); rotate(x);
        }
    }
}

int search(int x) {
    struct node *t = root, *last = NULL;
    while (t != NULL) {
        last = t;
        if (x == t->data) break;
        t = x < t->data ? t->left : t->right;
    }
    if (last != NULL) splay(last);               /* splay the key, or the last node reached */
    return root != NULL && root->data == x;
}
void insert(int x) {
    struct node *t = root, *y = NULL, *z;
    while (t != NULL) {
        y = t;
        if (x == t->data) { splay(t); return; }
        t = x < t->data ? t->left : t->right;
    }
    z = malloc(sizeof *z);
    z->data = x; z->left = z->right = NULL; z->parent = y;
    if (y == NULL) root = z;
    else if (x < y->data) y->left = z;
    else y->right = z;
    splay(z);                                    /* the new key becomes the root */
}
void deleteKey(int x) {
    struct node *L, *R, *m;
    if (!search(x)) { printf("%d not found\n", x); return; }
    L = root->left; R = root->right;             /* x is now the root: cut it out */
    free(root);
    if (L == NULL) { root = R; if (R) R->parent = NULL; return; }
    L->parent = NULL; root = L;
    for (m = L; m->right != NULL; m = m->right)  /* largest key of the left part */
        ;
    splay(m);                                    /* now it has no right child ... */
    m->right = R;                                /* ... so hang the right part there */
    if (R) R->parent = m;
}
void preorder(struct node *r) { if (r) { printf("%d ", r->data); preorder(r->left); preorder(r->right); } }

int main(void) {
    int ch, k, i, x;
    while (1) {
        printf("\n1.Insert many 2.Search 3.Delete 4.Show 5.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &k); printf("Keys: ");
                for (i = 0; i < k; i++) { scanf("%d", &x); insert(x); } break;
        case 2: printf("Key: "); scanf("%d", &x);
                printf(search(x) ? "Found; " : "Not found; ");
                if (root) printf("root is now %d\n", root->data); else printf("the tree is empty\n"); break;
        case 3: printf("Key: "); scanf("%d", &x); deleteKey(x); break;
        case 4: printf("Pre-order: "); preorder(root); printf("\n"); break;
        case 5: return 0;
        }
    }
    return 0;
}

/* B* tree of order M: insert with redistribution and the 2-to-3 split,
   delete with borrowing and the 3-to-2 merge, search, level print and rule check */
#include <stdio.h>
#include <stdlib.h>

#define MAXM 8                      /* largest order this program accepts */
struct node {
    int n;                          /* number of keys                    */
    int key[2 * MAXM];              /* room for a temporary overflow     */
    struct node *child[2 * MAXM + 1];
};
struct node *root = NULL;
int M = 4;                          /* order, read at the start          */

int minKeys(void) { return (2 * M + 1) / 3 - 1; }          /* ceil((2M-1)/3) - 1 */
int rootMax(void) { return 2 * ((2 * M - 2) / 3); }        /* Knuth: the root may be a little bigger */
int maxKeys(struct node *n) { return n == root ? rootMax() : M - 1; }
int isLeaf(struct node *n) { return n->child[0] == NULL; }
struct node *newNode(void) { return calloc(1, sizeof(struct node)); }
int indexIn(struct node *p, struct node *c) { int i = 0; while (p->child[i] != c) i++; return i; }
void printNode(struct node *n) { int i; printf("["); for (i = 0; i < n->n; i++) printf(i ? " %d" : "%d", n->key[i]); printf("]"); }

int search(int x) {
    struct node *t = root; int i;
    while (t != NULL) {
        i = 0; while (i < t->n && x > t->key[i]) i++;
        if (i < t->n && t->key[i] == x) return 1;
        if (isLeaf(t)) return 0;
        t = t->child[i];
    }
    return 0;
}

/* ---- insert ---- */
void shiftRight(struct node *L, int *sep, struct node *R) {   /* L gives its largest key, through the parent */
    int j;
    for (j = R->n; j > 0; j--) R->key[j] = R->key[j - 1];
    for (j = R->n + 1; j > 0; j--) R->child[j] = R->child[j - 1];
    R->key[0] = *sep; R->child[0] = L->child[L->n]; L->child[L->n] = NULL; R->n++;
    *sep = L->key[--L->n];
}
void shiftLeft(struct node *L, int *sep, struct node *R) {    /* R gives its smallest key, through the parent */
    int j;
    L->key[L->n] = *sep; L->child[L->n + 1] = R->child[0]; L->n++;
    *sep = R->key[0];
    for (j = 0; j < R->n - 1; j++) R->key[j] = R->key[j + 1];
    for (j = 0; j < R->n; j++) R->child[j] = R->child[j + 1];
    R->child[R->n] = NULL; R->n--;
}
/* fill node d with cnt keys from all[] (and cnt+1 children from ch[]) */
void fill(struct node *d, int *all, struct node **ch, int *k, int *c, int cnt) {
    int i;
    for (i = 0; i <= 2 * MAXM; i++) d->child[i] = NULL;
    for (i = 0; i < cnt; i++) d->key[i] = all[(*k)++];
    for (i = 0; i <= cnt; i++) d->child[i] = ch[(*c)++];
    d->n = cnt;
}
void split2to3(struct node *p, int a) {          /* children a and a+1 of p become three nodes */
    struct node *A = p->child[a], *B = p->child[a + 1], *N = newNode(), *ch[6 * MAXM];
    int all[4 * MAXM], t = 0, nc = 0, i, s1, s2, s3, k = 0, c = 0, up1, up2;
    for (i = 0; i < A->n; i++) all[t++] = A->key[i];
    all[t++] = p->key[a];
    for (i = 0; i < B->n; i++) all[t++] = B->key[i];
    for (i = 0; i <= A->n; i++) ch[nc++] = A->child[i];
    for (i = 0; i <= B->n; i++) ch[nc++] = B->child[i];
    s1 = (t - 2) / 3; s2 = (t - 2 - s1) / 2; s3 = t - 2 - s1 - s2;
    fill(A, all, ch, &k, &c, s1); up1 = all[k++];
    fill(B, all, ch, &k, &c, s2); up2 = all[k++];
    fill(N, all, ch, &k, &c, s3);
    for (i = p->n; i > a + 1; i--) p->key[i] = p->key[i - 1];
    for (i = p->n + 1; i > a + 2; i--) p->child[i] = p->child[i - 1];
    p->key[a] = up1; p->key[a + 1] = up2; p->child[a + 2] = N; p->n++;
    printf("  2-to-3 split: "); printNode(A); printf(" %d ", up1); printNode(B); printf(" %d ", up2); printNode(N); printf("\n");
}
void splitRoot(void) {
    struct node *old = root, *L = newNode(), *R = newNode();
    int t = old->n, mid = (t - 1) / 2, i;
    for (i = 0; i < mid; i++) L->key[i] = old->key[i];
    for (i = 0; i <= mid; i++) L->child[i] = old->child[i];
    L->n = mid;
    for (i = mid + 1; i < t; i++) R->key[i - mid - 1] = old->key[i];
    for (i = mid + 1; i <= t; i++) R->child[i - mid - 1] = old->child[i];
    R->n = t - mid - 1;
    root = newNode(); root->key[0] = old->key[mid]; root->child[0] = L; root->child[1] = R; root->n = 1;
    printf("  root split: %d is the new root\n", old->key[mid]);
    free(old);
}
void insert(int x) {
    struct node *path[64], *n = root, *p, *L, *R;
    int top = 0, i, j, ci;
    if (root == NULL) { root = newNode(); root->key[0] = x; root->n = 1; return; }
    while (1) {
        i = 0; while (i < n->n && x > n->key[i]) i++;
        if (i < n->n && n->key[i] == x) { printf("  %d already exists\n", x); return; }
        if (isLeaf(n)) break;
        path[top++] = n; n = n->child[i];
    }
    for (j = n->n; j > i; j--) n->key[j] = n->key[j - 1];
    n->key[i] = x; n->n++;
    while (n->n > maxKeys(n)) {                        /* overflow */
        if (n == root) { splitRoot(); return; }
        p = path[--top]; ci = indexIn(p, n);
        R = ci < p->n ? p->child[ci + 1] : NULL;
        L = ci > 0 ? p->child[ci - 1] : NULL;
        if (R != NULL && R->n < M - 1) { shiftRight(n, &p->key[ci], R); printf("  redistribute to the right sibling: %d goes up\n", p->key[ci]); return; }
        if (L != NULL && L->n < M - 1) { shiftLeft(L, &p->key[ci - 1], n); printf("  redistribute to the left sibling: %d goes up\n", p->key[ci - 1]); return; }
        split2to3(p, R != NULL ? ci : ci - 1);
        n = p;                                          /* the parent gained a key */
    }
}

/* ---- delete ---- */
void borrowLeft(struct node *L, int *sep, struct node *n) {    /* L lends its largest key */
    int j;
    for (j = n->n; j > 0; j--) n->key[j] = n->key[j - 1];
    for (j = n->n + 1; j > 0; j--) n->child[j] = n->child[j - 1];
    n->key[0] = *sep; n->child[0] = L->child[L->n]; L->child[L->n] = NULL; n->n++;
    *sep = L->key[--L->n];
}
void deleteKey(struct node *p, int i, int ci) {                /* remove key i and child ci from p */
    int j;
    for (j = i; j < p->n - 1; j++) p->key[j] = p->key[j + 1];
    for (j = ci; j < p->n; j++) p->child[j] = p->child[j + 1];
    p->child[p->n] = NULL; p->n--;
}
void delete(int x) {
    struct node *path[64], *n = root, *p, *L, *R, *X, *Y, *Z, *host, *ch[9 * MAXM];
    int top = 0, i, j, ci, w, t, nc, k, c, all[6 * MAXM], mk = minKeys(), s1, s2, s3, up1, up2, hi;
    while (n != NULL) {
        i = 0; while (i < n->n && x > n->key[i]) i++;
        if (i < n->n && n->key[i] == x) break;
        if (isLeaf(n)) n = NULL; else { path[top++] = n; n = n->child[i]; }
    }
    if (n == NULL) { printf("  %d not found\n", x); return; }
    if (!isLeaf(n)) {                                  /* internal key: use the in-order successor */
        host = n; hi = i; path[top++] = n; n = n->child[i + 1];
        while (!isLeaf(n)) { path[top++] = n; n = n->child[0]; }
        host->key[hi] = n->key[0]; i = 0;
        printf("  %d is internal: replaced by its successor %d\n", x, n->key[0]);
    }
    for (j = i; j < n->n - 1; j++) n->key[j] = n->key[j + 1];
    n->n--;
    while (n != root && n->n < mk) {                   /* underflow */
        p = path[--top]; ci = indexIn(p, n);
        L = ci > 0 ? p->child[ci - 1] : NULL;
        R = ci < p->n ? p->child[ci + 1] : NULL;
        if (L != NULL && L->n > mk) { borrowLeft(L, &p->key[ci - 1], n); printf("  borrow from the left sibling\n"); return; }
        if (R != NULL && R->n > mk) { shiftLeft(n, &p->key[ci], R); printf("  borrow from the right sibling\n"); return; }
        if (p->n == 1) {                               /* only two children: merge them into one */
            X = p->child[0]; Y = p->child[1];
            X->key[X->n] = p->key[0];
            for (j = 0; j < Y->n; j++) X->key[X->n + 1 + j] = Y->key[j];
            for (j = 0; j <= Y->n; j++) X->child[X->n + 1 + j] = Y->child[j];
            X->n += Y->n + 1; free(Y);
            p->n = 0; p->child[1] = NULL;
            printf("  2-to-1 merge: "); printNode(X); printf("\n");
            n = p; continue;
        }
        w = ci == 0 ? 0 : (ci == p->n ? ci - 2 : ci - 1);
        X = p->child[w]; Y = p->child[w + 1]; Z = p->child[w + 2];
        t = 0; nc = 0;
        for (j = 0; j < X->n; j++) all[t++] = X->key[j];
        all[t++] = p->key[w];
        for (j = 0; j < Y->n; j++) all[t++] = Y->key[j];
        all[t++] = p->key[w + 1];
        for (j = 0; j < Z->n; j++) all[t++] = Z->key[j];
        for (j = 0; j <= X->n; j++) ch[nc++] = X->child[j];
        for (j = 0; j <= Y->n; j++) ch[nc++] = Y->child[j];
        for (j = 0; j <= Z->n; j++) ch[nc++] = Z->child[j];
        k = 0; c = 0;
        if (t - 2 >= 3 * mk) {                         /* enough keys: share among the three */
            s1 = (t - 2) / 3; s2 = (t - 2 - s1) / 2; s3 = t - 2 - s1 - s2;
            fill(X, all, ch, &k, &c, s1); up1 = all[k++];
            fill(Y, all, ch, &k, &c, s2); up2 = all[k++];
            fill(Z, all, ch, &k, &c, s3);
            p->key[w] = up1; p->key[w + 1] = up2;
            printf("  share among three nodes\n");
            return;
        }
        s1 = (t - 1) / 2;                              /* 3-to-2 merge */
        fill(X, all, ch, &k, &c, s1); up1 = all[k++];
        fill(Y, all, ch, &k, &c, t - 1 - s1);
        free(Z);
        p->key[w] = up1; deleteKey(p, w + 1, w + 2);
        printf("  3-to-2 merge: "); printNode(X); printf(" %d ", up1); printNode(Y); printf("\n");
        n = p;
    }
    if (root->n == 0) {
        n = root;
        root = isLeaf(n) ? NULL : n->child[0];
        free(n);
        if (root != NULL) printf("  root removed: height - 1\n");
    }
}

/* ---- print and check ---- */
void printLevels(void) {
    struct node *q[512]; int lev[512], h = 0, tl = 0, cur = -1, i;
    if (root == NULL) { printf("empty\n"); return; }
    q[tl] = root; lev[tl++] = 0;
    while (h < tl) {
        struct node *n = q[h]; int d = lev[h++];
        if (d != cur) { printf(d ? "\nLevel %d: " : "Level %d: ", d); cur = d; } else printf(" ");
        printNode(n);
        if (!isLeaf(n)) for (i = 0; i <= n->n; i++) { q[tl] = n->child[i]; lev[tl++] = d + 1; }
    }
    printf("\n");
}
int leafDepth, lastKey, okFlag;
void check(struct node *n, int d, int isRoot) {
    int i;
    if (n->n > (isRoot ? rootMax() : M - 1) || n->n < (isRoot ? 1 : minKeys())) okFlag = 0;
    if (isLeaf(n)) {
        if (leafDepth < 0) leafDepth = d; else if (leafDepth != d) okFlag = 0;
        for (i = 0; i < n->n; i++) { if (n->key[i] <= lastKey) okFlag = 0; lastKey = n->key[i]; }
        return;
    }
    for (i = 0; i <= n->n; i++) {
        if (n->child[i] == NULL) { okFlag = 0; return; }
        check(n->child[i], d + 1, 0);
        if (i < n->n) { if (n->key[i] <= lastKey) okFlag = 0; lastKey = n->key[i]; }
    }
}
int rulesHold(void) { leafDepth = -1; lastKey = -2147483647; okFlag = 1; if (root) check(root, 0, 1); return okFlag; }

int main(void) {
    int ch, k, i, x;
    printf("Order m (3 to %d): ", MAXM - 1);
    if (scanf("%d", &M) != 1 || M < 3 || M >= MAXM) return 0;
    printf("Non-root nodes keep %d to %d keys; the root keeps 1 to %d keys\n", minKeys(), M - 1, rootMax());
    while (1) {
        printf("\n1.Insert many 2.Show 3.Search 4.Delete 5.Exit\nChoice: ");
        if (scanf("%d", &ch) != 1) break;
        switch (ch) {
        case 1: printf("How many? "); scanf("%d", &k); printf("Keys: ");
                for (i = 0; i < k; i++) { scanf("%d", &x); printf("Insert %d\n", x); insert(x); } break;
        case 2: printLevels(); printf(rulesHold() ? "All B* rules hold\n" : "B* rules broken!\n"); break;
        case 3: printf("Key: "); scanf("%d", &x); printf(search(x) ? "%d found\n" : "%d not found\n", x); break;
        case 4: printf("Key: "); scanf("%d", &x); printf("Delete %d\n", x); delete(x); break;
        case 5: return 0;
        }
    }
    return 0;
}