As the title says I am currently trying to find the max node of a BST and I want to delete it. I have the methods to findMax node and remove node ready from my Algorithm book, but I cant figure out how to use them in the main method. I have a method that can insert the nodes by entering a number, for instance 8, which will print a tree in level ordered: 4, 2, 6, 1, 3, 5, 7 where 4 is the root. I want to be able to find the last node and delete it. What I have so far are these methods:
public BinaryNode remove(AnyType x, BinaryNode<AnyType> t)
{
if(t == null)
return t;
int compareResult = x.compareTo(t.element);
if(compareResult < 0 )
t.left = remove(x, t.left);
else if(compareResult > 0)
t.right = remove(x, t.right);
else if(t.left != null && t.right != null)
{
t.element = (AnyType) findMax(t.right).element;
t.right = remove(t.element, t.right);
}
else
t = (t.left != null) ? t.left : t.right;
return t;
}
public BinaryNode<AnyType> remove(AnyType x)
{
return root = remove(x, root);
}
public BinaryNode<AnyType> findMax(BinaryNode<AnyType> t)
{
if(t != null)
while(t.right != null)
t = t.right;
return t;
}
My main method looks like this:
public static void main(String[] args)
{
CompleteBinarySearchTree<Integer> bst = new CompleteBinarySearchTree<>();
BinaryNode<Integer> tree = bst.createBinarySearchTree(bst.insertNodes(8));
bst.printLevelOrderedBST(tree);
}
I want to be able to freely insert any nodes and the tree should still be able to delete the max node. I can't figure out how to call the remove() method on the findMax(). I can of course call remove(7, tree) and it will delete the 7, but that is not what I want. Any help is much appreciated.
The key to deleting the max node is that you have to keep track of its parent, so you can update the parent's right pointer (set it to null). You also have to handle the case where the node you pass has no right child, in which the node itself is the largest node.
The code below shows the basic idea. Untested, but should be close.
// removes the largest node in the binary tree with root at t.
// returns the new root.
public BinaryNode<AnyType> removeMax(BinaryNode<AnyType> t)
{
if (t == null) return null;
if (t.right == null) {
// the node passed in is the largest.
return t.left;
}
// traverse the right branch to the last node,
// keeping track of the previous node so you can correctly set its
// right pointer to null.
BinaryNode<AnyType> parent = t;
BinaryNode<AnyType> child = parent.right;
while (child.right != null) {
parent = child;
child = child.right;
}
parent.right = null;
return t;
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments