| 1,20 → 1,21 |
|---|
| #include <stdio.h> |
| |
| #include "mavl.h" |
| |
| static int |
| mav_getbal(struct mavlnode *n) |
| getbal(struct mavlnode *n) |
| { |
| return n==NULL ? 0:n->bal; |
| return n==NULL ? 0 : n->bal; |
| } |
| |
| static int |
| recalc(struct mavlnode *n){ |
| int b0,b1; |
| b0 = mav_getbal( n->s[0] ); |
| b1 = mav_getbal( n->s[1] ); |
| b0 = getbal( n->s[0] ); |
| b1 = getbal( n->s[1] ); |
| return (b1>b0 ? b1 : b0)+1; |
| |
| /* n->bal = n->s[ (mav_getbal(n->s[0])->bal > n->s[1]->bal) ? 0 : 1 ]->bal+1;*/ |
| /* n->bal = n->s[ (getbal(n->s[0])->bal > n->s[1]->bal) ? 0 : 1 ]->bal+1;*/ |
| } |
| |
| /* p p |
| 24,39 → 25,62 |
|---|
| * b n 2 |
| * / \ . / \ |
| * 1 2 1 |
| */ |
| */ |
| |
| /* |
| 2 |
| \ |
| 1 |
| \ |
| 0 |
| */ |
| |
| /* |
| * dir = 1 rot left |
| * dir = 0 rot right |
| */ |
| static struct mavlnode * |
| rot(struct mavlnode *n, struct mavlnode **parent, int dir) |
| rot(struct mavlnode *n, int dir) |
| { |
| *parent = n->s[dir]; |
| n->s[dir]=(*parent)->s[1-dir]; |
| (*parent)->s[1-dir]=n; |
| recalc(n); |
| recalc(*parent); |
| return *parent; |
| struct mavlnode * r; |
| r = n->s[dir]; |
| n->s[dir]=r->s[1-dir]; |
| r->s[1-dir]=n; |
| /* n->bal = recalc(n);*/ |
| /* r->bal = recalc(r);*/ |
| n->bal=0; |
| r->bal=0; |
| return r; |
| } |
| |
| |
| static struct mavlnode * |
| balance ( struct mavlnode *n, struct mavlnode **parent) { |
| balance ( struct mavlnode *n) { |
| int b,d; |
| b = n->s[1]->bal - n->s[0]->bal; |
| /* b = n->s[1]->bal - n->s[0]->bal;*/ |
| |
| /* b = getbal(n->s[1]) - getbal( n->s[0] );*/ |
| |
| b = n->bal; |
| |
| if (b>-2 && b<2) |
| return n; |
| d = b<0 ? 1:0; |
| |
| printf("should rotate! %d\n",b); |
| return rot(n,1); |
| |
| /* d = b<0 ? 1:0; |
| if (n->s[d]->bal - n->s[1-d]->bal == -d/2) |
| n->s[d]=rot(n->s[d],parent,d); |
| return rot(n,parent,1-d); |
| return rot(n,parent,1-d);*/ |
| |
| } |
| |
| static struct mavlnode * |
| mav_insert0(struct mavl *t, struct mavlnode *root, const void **data) |
| { |
| struct mavlnode * nnn; |
| |
| int rc,dir; |
| if (root==NULL){ |
| root = mavlnode_create(t, *data); |
| 65,7 → 89,7 |
|---|
| *data = mavlnode_dataptr(root); |
| /*return MAVL_E_NOMEM;*/ |
| t->count++; |
| root->bal=1; |
| root->bal=0; |
| return root; |
| } |
| |
| 78,11 → 102,15 |
|---|
| |
| /* rc is > 0 here */ |
| dir = rc>0 ? 1:0; |
| /* root->bal +=dir;*/ /*recalc(root); */ |
| root->s[dir] = mav_insert0(t, root->s[dir], data); |
| root->bal = recalc(root); |
| |
| |
| return root; |
| nnn = balance(root); |
| printf("Return %p === %p\n",root,nnn); |
| return balance(nnn); |
| |
| /* return root; */ |
| /* recalc(n);*/ |
| } |
| |