#include #include #include #define EVEN 0 #define ODD 1 #define MINUSINFINITY -1000000000 #define PLUSINFINITY 1000000000 typedef struct _node { int key; struct _node *L, *R, *P; } tnode; typedef tnode *BST; typedef struct { tnode *x, *y; int gap; } neighbor; BST insert ( BST T, int x ) { BST p, q; p = T; q = NULL; while (p) { if (p -> key == x) return T; q = p; p = (x < p -> key) ? p -> L : p -> R; } p = (tnode *)malloc(sizeof(tnode)); p -> key = x; p -> L = p -> R = NULL; p -> P = q; if (q == NULL) return p; if (x < q -> key) q -> L = p; else q -> R = p; return T; } /* Assumes n >= 3 */ BST gentree ( int n ) { BST T; int i, j, t, *gaps, *keys; gaps = (int *)malloc(n * sizeof(int)); gaps[0] = rand() % 100; for (i=1; ikey); ++(*npr); preorder(T->L, npr); preorder(T->R, npr); } /* T is the current node, and *P is the previous node in the inorder traversal */ void inorder ( BST T, BST *P, neighbor *N, int parity ) { int gap; if (T == NULL) return; inorder(T->L, P, N, parity); if (parity == EVEN) { if (*P != NULL) { gap = (T -> key) - ((*P) -> key); if (gap < N -> gap) { N -> x = *P; N -> y = T; N -> gap = gap; } } } else { if (*P != NULL) { gap = (T -> key) - ((*P) -> key); if (gap > N -> gap) { N -> x = *P; N -> y = T; N -> gap = gap; } } } *P = T; inorder(T->R, P, N, parity); } neighbor findnbr ( BST T, int parity ) { neighbor N; BST P; N.x = N.y = NULL; N.gap = (parity == EVEN) ? PLUSINFINITY : MINUSINFINITY; P = NULL; inorder(T,&P,&N,parity); return N; } BST lrotate ( BST u ) { BST v, w; v = u -> R; if (v == NULL) { fprintf(stderr, "*** Left rotate not allowed\n"); return u; } w = v -> L; v -> L = u; u -> R = w; v -> P = u -> P; u -> P = v; if (w) w -> P = u; return v; } BST rrotate ( BST u ) { BST v, w; v = u -> L; if (v == NULL) { fprintf(stderr, "*** Right rotate not allowed\n"); return u; } w = v -> R; v -> R = u; u -> L = w; v -> P = u -> P; u -> P = v; if (w) w -> P = u; return v; } BST makechild ( BST T, neighbor N, int parity ) { int nrots = 0; BST p, q; if (parity == EVEN) { if ((N.y) -> L) { printf("*** Case 1: x is a descendent of y\n"); while ((N.y) -> L != N.x) { (N.y) -> L = lrotate((N.y) -> L); ++nrots; } } else { printf("*** Case 2: y is a descendent of x\n"); while ((N.x) -> R != N.y) { (N.x) -> R = rrotate((N.x) -> R); ++nrots; } p = (N.x) -> P; q = lrotate(N.x); ++nrots; if (p == NULL) { printf("*** Rotation at root\n"); T = q; } else if (q -> key < p -> key) p -> L = q; else p -> R = q; } printf(" Number of rotations = %d\n", nrots); printf(" y = %d, y -> L = %d, y -> R = ", N.y -> key, N.y -> L -> key); if (N.y -> R) printf("%d\n", N.y -> R -> key); else printf("NULL\n"); } else { if ((N.x) -> R) { printf("*** Case 1: y is a descendent of x\n"); while((N.x) -> R != N.y) { (N.x) -> R = rrotate((N.x) -> R); ++nrots; } } else { printf("*** Case 2: x is a descendent of y\n"); while ((N.y) -> L != N.x) { (N.y) -> L = lrotate((N.y) -> L); ++nrots; } p = (N.y) -> P; q = rrotate(N.y); ++nrots; if (p == NULL) { printf("*** Rotation at root\n"); T = q; } else if (q -> key < p -> key) p -> L = q; else p -> R = q; } printf(" Number of rotations = %d\n", nrots); printf(" x = %d, x -> L = ", N.x -> key); if (N.x -> L) printf("%d", N.x -> L -> key); else printf("NULL"); printf(", x -> R = %d\n", N.x -> R -> key); } return T; } int main ( int argc, char *argv[] ) { int n, npr, parity; BST T; neighbor N; srand((unsigned int)time(NULL)); if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n); if (argc > 2) parity = atoi(argv[2]); else scanf("%d", &parity); parity %= 2; if (parity < 0) parity = -parity; printf("%s PC\nn = %d\n", (parity == 0) ? "EVEN" : "ODD", n); T = gentree(n); printf("\n+++ Preorder traversal of initial tree"); npr = 0; preorder(T, &npr); printf("\n"); printf("\n+++ Finding %s neighbor\n", (parity == 0) ? "closest" : "farthest"); N = findnbr(T,parity); printf(" x = %d, y = %d, gap = %d\n", (N.x)->key, (N.y)->key, N.gap); printf("\n+++ Bringing neighboring key to child position\n"); T = makechild(T,N,parity); printf("\n+++ Preorder traversal of final tree"); npr = 0; preorder(T, &npr); printf("\n"); exit(0); }