CompetitiveProgramming icon indicating copy to clipboard operation
CompetitiveProgramming copied to clipboard

Memory leak in AVL tree

Open Tagl opened this issue 11 months ago • 0 comments

There is a memory leak in the AVL tree. An early return in the erase function causes a memory leak. Can be resolved by changing

    else if (n->l && n->r) {
      node *s = successor(n);
      erase(s, false);
      s->p = n->p, s->l = n->l, s->r = n->r;
      if (n->l) n->l->p = s;
      if (n->r) n->r->p = s;
      parent_leg(n) = s, fix(s);
      return;
    }

to

    else if (n->l && n->r) {
      node *s = successor(n);
      erase(s, false);
      s->p = n->p, s->l = n->l, s->r = n->r;
      if (n->l) n->l->p = s;
      if (n->r) n->r->p = s;
      parent_leg(n) = s, fix(s);
      delete n;
      return;
    }

Tagl avatar Jan 20 '25 21:01 Tagl