Arc Forumnew | comments | leaders | submitlogin
4 points by waterhouse 5011 days ago | link | parent

What I was doing was getting the AVL tree to work (which, by the way, took a certain amount of thinking, debugging, and rewriting). Implementing them with hash tables, with convenient notation, was entirely appropriate for the task at hand. And now that I've got it in working form, it's easy to go and replace the hash table parts with structs or something. In fact, I think that was pretty clearly on my mind, because I described in footnote 2, in some detail, how one might implement the nodes using things other than hash tables. It was not my intention that the nodes should forever remain hash tables. I think you misunderstand me greatly.

And by the way, I did re-implement it in C, using structs, before I wrote the original post. Here's an excerpt.

  avl_node * node_r(st_h *d, avl_node *x, avl_node *y) {
    if (x->dp > 1+y->dp) {
      if (x->lf->dp > x->rt->dp)
        return node(x->dt, x->lf, node(d, x->rt, y));
      else return node(x->rt->dt, node(x->dt, x->lf, x->rt->lf), node(d,x->rt->rt, y)); }
    else {
      if (y->rt->dp > 1+y->lf->dp) {
        if (y->rt->dp > y->lf->dp)
  	return node(y->dt, node(d,x,y->lf), y->rt);
        else return node(y->lf->dt, node(d,x,y->lf->lf), node(y->dt, y->lf->rt, y->rt)); }
      else return node(d,x,y);
    }}
Feels good, man. (The above code, by the way, fails to free() the obsolete nodes. That could be fixed if necessary.) Fortunately, I didn't really have to debug that code; I cribbed directly from my Arc code.