All pastes #1547903 Raw Edit

Concise (at best) AVL tree balan

public c v1 · immutable
#1547903 ·published 2009-08-30 03:15 UTC
rendered paste body
struct AvlNode {   signed char bal;   AvlKey k;   AvlValue v;   AvlNode *c[2];}; static void avlRol(AvlNode **a, AvlNode **b, AvlNode **c) {   AvlNode *t = *a;   *a = *b;   *b = *c;   *c = t;} // *n must have balance of -2 or 2static void avlBalance(AvlNode **np) {   AvlNode *n = *np, *nc, *ncc;   int b = (n->bal > 0), nb = 1-b;   int cb = (n->c[b]->bal > 0);   nc = n->c[b];   ncc = nc->c[nb];    if (cb == nb) {      static const signed char abTbl[] = {1,0,0,1,0,0,0,0,0,-1,-1,0};      const signed char *tbl = abTbl+(ncc->bal+1)*4+b+b;      n->bal = tbl[0];      nc->bal = tbl[1];      if (ncc)         ncc->bal = 0;      avlRol(nc->c+nb, nc->c[nb]->c+b, n->c+b);   } else {      n->bal = 0;      n->c[b]->bal = 0;   }    avlRol(n->c+b, n->c[b]->c+nb, np);}