/* x is ys only child */ if (y->left != NIL) x = y->left;

x = y->right;

/* remove y from the parent chain */ x->parent = y->parent; if (y->parent)

if (y == y->parent->left) y->parent->left = x;

y->parent->right = x;

root = x; if (y != z) z->data = y->data;

if (y->color == BLACK)

deleteFixup (x);

free (y);

Node *findNode(T data) {

/*******************************

* find node containing data * *******************************/

Node *current = root; while(current != NIL)

if(compEQ(data, current->data)) return (current);

current = compLT (data, current->data) ? current->left : current->right;

return(0);

4.8 Коды для разделенных списков

typedef int T;/* type of item to be sorted */

#define compLT(a,b) (a < b) #define compEQ(a,b) (a == b)

* levels range from (0 .. MAXLEVEL)

#define MAXLEVEL 15

typedef struct Node {

T data;/* users data */

struct Node *forward[1]; /* skip list forward pointer */

} Node;

typedef struct { Node *hdr; int listLevel;

} SkipList;

/* list Header */ /* current level of list */

SkipList list;

/* skip list information */

#define NIL list.hdr

Node *insertNode(T data) { int i, newLevel; Node *update[MAXLEVEL+1]; Node *x;

/***********************************************

* allocate node for data and insert in list * ***********************************************/

/* find where data belongs */ x = list.hdr;

for (i = list.listLevel; i >= 0; i--) { while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data)) x = x->forward[i]; update[i] = x;

if (x != NIL && compEQ(x->data, data)) return(x);

/* determine level */ newLevel = 0;

while (rand() < RAND MAX/2) newLevel++;

if (newLevel > MAXLEVEL) newLevel = MAXLEVEL;

if (newLevel > list.listLevel) {

for (i = list.listLevel + 1; i <= newLevel; i++) update[i] = NIL;

/* make new node */ if ((x = malloc(sizeof(Node) +

newLevel*sizeof(Node *))) == 0) {

printf ("insufficient memory (insertNode)\n");

exit(1);

x->data = data;

/* update forward links */ for (i = 0; i <= newLevel; i++) {

x->forward[i] = update[i]->forward[i];

update[i]->forward[i] = x;

return(x);

x->forward[0];

list.listLevel = newLevel;

void deleteNode(T data) { int i;

Node *update[MAXLEVEL+1], *x;

/*******************************************

*delete node containing data from list * *******************************************/

/* find where data belongs */ x = list.hdr;

for (i = list.listLevel; i >= 0; i-- ) { while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data)) x = x->forward[i]; update[i] = x;

x = x->forward[0];

if (x == NIL !compEQ(x->data, data)) return;

/* adjust forward pointers */ for (i = 0; i <= list.listLevel; i++) {

if (update[i]->forward[i] != x) break;

update[i]->forward[i] = x->forward[i];

free (x);

/* adjust header level */ while ((list.listLevel > 0)

&& (list.hdr->forward[list.listLevel] == NIL))

list.listLevel-- ;

Node *findNode(T data) {

Node *x = list.hdr;

/*******************************

*find node containing data * *******************************/

for (i = list.listLevel; i >= 0; i-- ) { while (x->forward[i] != NIL

&& compLT(x->forward[i]->data, data)) x = x->forward[i];

x = x->forward[0];

if (x != NIL && compEQ(x->data, data)) return (x); return(0);

void initList() { int i;