Remove code

Subject: Remove code
From: Kevin Chan (kachan@cs.washington.edu)
Date: Fri May 03 2002 - 00:12:57 PDT

• sorted by: [ date ] [ thread ] [ subject ] [ author ]
• Next message: Matthew Cary: "Hash Times"
• Previous message: James Nicholas Deibel: "326: The Usefulness of Hashtables"

Alright, I wasn't expecting everyone to literally use my code from the
last e-mail message, but because everyone is and are claiming that there
are bugs. (Yes there was bug, the only bug was the fact that I did not set
any of the pointers on the current node to NULL. So you get the runaway
node problem.)

The following is the answer to the remove assignment. You may use it if
you feel you want to use the code in the AVL assignment.

DISCLAIMER: This code worked and still works under the remove assignment.
It is not guaranteed to work in the AVL assignment. The biggest thing I
can see is the fact that this remove function uses the successor but you
are expected to use the predecessor.

  TreeNode* replacement = NULL;
  if (RChild() && LChild())
  {
      replacement = this->Succ();
      replacement->Remove();
      replacement->SetLChild(LChild());
      replacement->SetRChild(RChild());
  }

  else if (RChild() && !LChild())
      replacement = RChild();

  else if (!RChild() && LChild())
      replacement = LChild();

  else
      assert(RChild() == NULL && LChild() == NULL);

  if (Parent())
  {
      if (Parent()->LChild() == this)
          Parent()->SetLChild(replacement);
      else
      {
          assert (Parent()->RChild() == this);
          Parent()->SetRChild(replacement);
      }
  }

  this->SetLChild(NULL);
  this->SetRChild(NULL);
  this->SetParent(NULL);

  TreeNode::CancelEmphasize();

  return replacement;
}

• Next message: Matthew Cary: "Hash Times"
• Previous message: James Nicholas Deibel: "326: The Usefulness of Hashtables"

This archive was generated by hypermail 2b25 : Fri May 03 2002 - 00:13:10 PDT