[Java] [Binary Search Trees] Remove within the node (remove than gets called be

Question

[Java] [Binary Search Trees] Remove within the node (remove than gets called be an iterator).

Current code: http://pastebin.com/uapiebzw

Current code with parent field: http://pastebin.com/ibdGaLwc

I am tasked with removing the node returned by next(). When the iterator calls it's own remove the current element should than call the remove that is within the node class and than successfully remove that node. I'm current stuck at setting up a successful iterator remove. Everything i tried ends in a a NullPointerExcpetion. What is a successful way to implement the iterator remove that removes the current node and updates the versions? (Versions are there to prevent staleness).

Also I'm aware that the remove in the Node class is empty. I tried a code that test just one element in the tree and it failed.

Explanation / Answer

//to do that we just need to write correctly remove () function of Node Class .

//below function of ContactTreeList

public void remove()

{

checkVersion();

current=current.remove(current); // current object of Node type

itVersion = version++; }

//remove() function of Node class, made some changes for the desired update

//we used this function to get inoreder successor

//these are member function of Node Class:
Node minValue(Node inoder_succ)
{
while (inoder_succ.left != null)
{
inoder_succ = inoder_succ.left;
}
return inorder_succ;
}

Node remove(Node root)
{
// tree is empty
if (root == null) return root;
// This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
Node inoder_succ=minValue(root.right);

// Delete the inorder successor
root.right = remove(inoder_succ);
}
return root;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.