| 26,22 → 26,11 |
|---|
| */ |
| #include <string.h> |
| #include <stdio.h> |
| #include <assert.h> |
| |
| #include "mavl.h" |
| |
| extern void the_print(); |
| |
| static void |
| mavl_drot2(struct mavlnode *n, struct mavlnode **parent, int dir) |
| { |
| |
| mavl_rot(n->s[dir],&n->s[dir],1-dir); |
| mavl_rot(n,parent,dir); |
| return; |
| } |
| |
| |
| |
| /* |
| * dir == 0 adj_bal_r |
| * dir == 1 adj_bal_l |
| 66,43 → 55,8 |
|---|
| |
| if (n->s[dir]->bal == -sdir) { |
| |
| /* if (n->s[1-dir] != NULL) |
| n->bal = n->s[1-dir]->bal ? 0 : -sdir; |
| else |
| n->bal = 0; |
| */ |
| b = n->s[dir]->s[1-dir]->bal; |
| |
| |
| |
| |
| { |
| int l,r; |
| l = n->s[0] ? 1 : 0; |
| r = n->s[1] ? 1 : 0; |
| l = n->s[0] ? n->s[0]->bal : 0; |
| r = n->s[1] ? n->s[1]->bal : 0; |
| n->bal = r+l; |
| |
| if (!n->s[dir]->s[dir]) n->bal = 0; |
| |
| |
| } |
| |
| /* |
| b = n->s[dir]->s[1-dir]->bal; |
| if (b==0) { |
| n->bal = -sdir; |
| } |
| else if (b==-sdir) { |
| n->bal=0; |
| } else { |
| printf("No\n"); |
| exit(0); |
| } |
| */ |
| |
| b = n->s[dir]->s[1-dir]->bal; |
| |
| if (b == 0){ |
| n->s[dir]->bal = 0; |
| n->bal=0; |
| 113,27 → 67,18 |
|---|
| n->s[dir]->bal = sdir; |
| n->bal=0; |
| } else{ |
| printf("Kack\n"); |
| exit(0); |
| assert(0*sdir); |
| } |
| |
| |
| n->s[dir]->s[1-dir]->bal = 0; |
| |
| |
| mavl_drot2(n, parent,dir); |
| return 1; |
| |
| n->bal = n->s[dir]->bal; |
| n->s[dir]->bal = 0; |
| n->s[dir]->s[1-dir]->bal = 0; |
| mavl_drot2(n, parent,dir); |
| return 0; |
| return 1; |
| mavl_drot(n, parent,dir); |
| return 1; |
| } |
| |
| printf("BAX\n"); |
| exit(0); |
| assert(0*sdir); |
| return 0; |
| } |
| |
| static int |
| 149,10 → 94,7 |
|---|
| if (n->bal == -sdir) |
| return 0; |
| if (n->bal == -2*sdir){ |
| bal = adj_bal(n,parent,1-dir,-sdir); |
| if (bal == 99) |
| return 0; |
| return bal; |
| return adj_bal(n,parent,1-dir,-sdir); |
| } |
| return bal; |
| } |
| 160,7 → 102,6 |
|---|
| /* found the lowest element */ |
| *parent = n->s[1]; |
| (void) memcpy(data,mavlnode_dataptr(n),t->data_size); |
| |
| t->free(n); |
| return 1; |
| |
| 209,10 → 150,7 |
|---|
| if (n->bal == -sdir) |
| return 0; |
| if (n->bal == -2*sdir){ |
| bal = adj_bal(n,parent,1-dir,-sdir); |
| if (bal == 99 ) |
| return 0; |
| return bal; |
| return adj_bal(n,parent,1-dir,-sdir); |
| } |
| return bal; |
| |
| 221,11 → 159,11 |
|---|
| dir = rc < 0 ? 0 : 1; |
| sdir = dir ? -1:1; |
| |
| if (!n->s[dir]){ |
| /* if (!n->s[dir]){ |
| printf("wrongdir\n"); |
| exit(0); |
| } |
| |
| */ |
| bal = mavl_del0(t, &n->s[dir], data); |
| sdir = dir ? 1:-1; |
| n->bal -= bal*sdir; |
| 232,28 → 170,18 |
|---|
| if (n->bal == -sdir) |
| return 0; |
| if (n->bal == -2*sdir){ |
| bal = adj_bal(n,parent,1-dir,-sdir); |
| if (bal == 99 ) |
| return 0; |
| return bal; |
| return adj_bal(n,parent,1-dir,-sdir); |
| } |
| return bal; |
| |
| /* return adj_bal(n, parent,1-dir,bal);*/ |
| |
| |
| |
| |
| } |
| |
| |
| |
| void |
| *mavl_del(struct mavl *t, const void *data) |
| { |
| void *d; |
| int rc; |
| |
| |
| if (!t->root) |
| return NULL; |
| |