7,24 → 7,28 |
n->bal = n->s[ (n->s[0]->bal>n->s[1]->bal) ? 0 : 1 ]->bal+1; |
} |
|
/* dir = 1 rot left */ |
/* p p |
* / / |
* n ----> b |
* / \ / \ |
* b n 2 |
* / \ . / \ |
* 1 2 1 |
*/ |
|
/* |
* dir = 1 rot left |
* dir = 0 rot right |
*/ |
static struct mavlnode * |
rot(struct mavlnode *n, struct mavlnode **parent, int dir) |
{ |
*parent = n->s[dir]; |
n->s[dir]=(*parent)->s[1-dir]; |
n->s[dir]=n; |
(*parent)->s[1-dir]==n; |
recalc(n); |
recalc(*parent); |
return *parentl; |
|
/* struct mavlnode *tmp; |
*parent = n->s[dir]; |
tmp = n->s[dir]->s[1-dir]; |
n->s[dir]->s[1-dir]=n; |
n->s[dir]=tmp; |
return NULL; |
*/ |
return *parent; |
} |
|
|
40,6 → 44,38 |
return rot(n,parent,1-d); |
} |
|
static struct mavlnode * |
mav_insert0(struct mavl *t, struct mavlnode **parent, const void **data) |
{ |
int rc; |
struct mavlnode *n ; |
if (*parent==NULL){ |
*parent = mavlnode_create(t, *data); |
*data = mavlnode_dataptr(*parent); |
if (*parent==NULL) |
return NULL; |
/*return MAVL_E_NOMEM;*/ |
t->count++; |
(*parent)->bal=1; |
return *parent; |
} |
|
rc = t->cmp(*data, mavlnode_dataptr(n)); |
if (rc == 0) { |
/* element exists */ |
*data = mavlnode_dataptr(n); |
return NULL; |
} |
|
n = *parent; |
|
/* rc is > 0 here */ |
mav_insert0(t, &(n->s[ rc>0 ? 1:0 ]), data); |
|
|
|
} |
|
void * |
mav_insert(struct mavl *t, const void *data, int *exists) |
{ |