| 25,63 → 25,165 |
|---|
| * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| #include <string.h> |
| #include <stdio.h> |
| |
| #include "mavl.h" |
| |
| extern void the_print(); |
| //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); |
| //the_print(); |
| mavl_rot(n,parent,dir); |
| //the_print(); |
| return; |
| } |
| |
| static int adj_bal(struct mavlnode *n, struct mavlnode **parent, int dir) |
| |
| |
| /* |
| * dir == 0 adj_bal_r |
| * dir == 1 adj_bal_l |
| */ |
| |
| static int |
| adj_bal(struct mavlnode *n, struct mavlnode **parent, int dir, int sdir) |
| { |
| |
| int sdir = dir ? 1:-1; |
| if (n->s[dir]->bal == sdir) { |
| n->bal = 0; |
| n->s[dir]->bal = 0; |
| mavl_rot(n, parent, dir); |
| return 0; |
| } |
| |
| int b; |
| //printf("adj ball called n->sdir-bal:%d dir:%d\n",n->s[dir]->bal,sdir); |
| if (n->s[dir]->bal == 0) { |
| n->bal = sdir; |
| n->s[dir]->bal = -sdir; |
| mavl_rot(n, parent, dir); |
| mavl_rot(n, parent,dir); |
| return 0; |
| } |
| |
| if (n->s[dir]->bal == 1) { |
| if (n->s[dir]->bal == sdir) { |
| n->bal = 0; |
| n->s[dir]->bal = 0; |
| n->s[dir]->s[1-dir]->bal = 0; |
| mavl_drot(n, parent,dir); |
| mavl_rot(n, parent,dir); |
| return 1; |
| } |
| return -11; /* that should never happen */ |
| } |
| |
| if (n->s[dir]->bal == -sdir) { |
| //the_print(); |
| // n->bal = 0; |
| // n->bal = n->s[dir]->bal; //-sdir; |
| |
| /* if (n->s[1-dir] != NULL) |
| n->bal = n->s[1-dir]->bal ? 0 : -sdir; |
| else |
| n->bal = 0; |
| */ |
| // n->s[1-dir]->bal-sdir: 0; |
| |
| |
| // n->s[dir]->bal *= (n->s[dir]->s[1-sdir]->bal)*19; //sdir; //sdir*9 ; ok w |
| |
| // n->s[dir]->bal = 999; |
| // |
| b = n->s[dir]->s[1-dir]->bal; |
| |
| if (b == 0){ |
| n->s[dir]->bal = 0; |
| } else if (b == sdir) { |
| n->s[dir]->bal = 0 ; |
| } else if (b == -sdir){ |
| n->s[dir]->bal = sdir; |
| } else{ |
| printf("Kack\n"); |
| exit(0); |
| } |
| |
| |
| n->s[dir]->s[1-dir]->bal = 0; // ok z |
| |
| mavl_drot2(n, parent,dir); |
| |
| { |
| int l,r; |
| l = n->s[0] ? 1 : 0; |
| r = n->s[1] ? 1 : 0; |
| n->bal = r-l; |
| } |
| // n->bal=98; |
| return 1; |
| |
| // mavl_drot2(n, parent,dir); |
| //return 0; |
| n->bal = n->s[dir]->bal; //-sdir; |
| // mavl_drot2(n, parent,dir); |
| // return 0; |
| n->s[dir]->bal = 0; //n->s[dir]->bal*-1; |
| //mavl_rot(n->s[dir],&n->s[dir],1-dir); |
| // n->bal = 0; //-sdir; |
| n->s[dir]->s[1-dir]->bal = 0; //-1* n->s[dir]->s[1-dir]->bal; //0; |
| //mavl_rot(n->s[dir],&n->s[dir],dir); |
| mavl_drot2(n, parent,dir); |
| return 0; |
| return 1; |
| } |
| |
| printf("BAX\n"); |
| exit(0); |
| } |
| |
| |
| static int |
| adj_bala(struct mavlnode *n, struct mavlnode **parent, int dir, int sdir) |
| { |
| |
| int b; |
| if (n->s[dir]->bal == sdir) { |
| n->bal = 0; |
| n->s[dir]->bal = 0; |
| mavl_rot(n, parent,dir); |
| return 0; |
| } |
| |
| b = n->s[dir]->s[1-dir]->bal; |
| if (b==-sdir){ |
| n->bal = 0; |
| n->s[dir]->bal = sdir; |
| }else if (b==sdir){ |
| n->bal = -sdir; |
| n->s[dir]->bal = 0; |
| }else{ |
| n->bal = 0; |
| n->s[dir]->bal = 0; |
| } |
| |
| n->s[dir]->s[1-dir]->bal = 0; |
| mavl_drot(n, parent,dir); |
| return 0; |
| |
| } |
| |
| static int |
| mavl_del_lo(struct mavl * t, struct mavlnode **parent, void *data) |
| { |
| struct mavlnode *n = *parent; |
| |
| /* walk down left */ |
| if (n->s[0]) { |
| int dir=0,sdir; |
| int bal = mavl_del_lo(t, &n->s[0], data); |
| n->bal += bal; |
| if (n->bal == 1) { |
| sdir = dir ? 1:-1; |
| n->bal -= bal*sdir; |
| 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; |
| } |
| if (n->bal != 2) |
| return bal; |
| /* adj_bal_l(n, parent);*/ |
| return 0; |
| return bal; |
| } |
| |
| /* found the lowest element */ |
| |
| *parent = n->s[1]; |
| (void) memcpy(data,mavlnode_dataptr(n),t->data_size); |
| |
| 122,38 → 224,51 |
|---|
| } |
| |
| /* node has two children */ |
| |
| if (t->del) { |
| t->del(mavlnode_dataptr(n)); |
| } |
| t->count--; |
| bal = mavl_del_lo(t,&n->s[1], mavlnode_dataptr(n)); |
| n->bal -= bal; |
| if (n->bal == -1) |
| dir = 1; |
| sdir = dir ? 1:-1; |
| n->bal -= bal*sdir; |
| if (n->bal == -sdir) |
| return 0; |
| |
| if (n->bal != -2) |
| if (n->bal == -2*sdir){ |
| bal = adj_bal(n,parent,1-dir,-sdir); |
| if (bal == 99 ) |
| return 0; |
| return bal; |
| } |
| return bal; |
| |
| return adj_bal(n, parent,1); |
| |
| } |
| |
| dir = rc < 0 ? 0 : 1; |
| sdir = dir ? -1:1; |
| |
| if (!n->s[dir]){ |
| exit(0); |
| } |
| |
| bal = mavl_del0(t, &n->s[dir], data); |
| if (bal == 2) |
| return 2; |
| n->bal += bal*sdir; |
| if (n->bal == sdir) |
| sdir = dir ? 1:-1; |
| n->bal -= bal*sdir; |
| if (n->bal == -sdir) |
| return 0; |
| |
| if (n->bal != 2*sdir) |
| if (n->bal == -2*sdir){ |
| bal = adj_bal(n,parent,1-dir,-sdir); |
| if (bal == 99 ) |
| return 0; |
| return bal; |
| } |
| return bal; |
| |
| return adj_bal(n, parent,1-dir); |
| /* return adj_bal(n, parent,1-dir,bal);*/ |
| |
| |
| |
| |
| } |
| |
| |