Programming Language Java Basic Setup Implement or adapt a B

Programming Language: Java

Basic Setup: Implement or adapt a BST class (preferred) or a package of data structures and functions that contains implementation of the following operations on BSTs: inorder/preorder/postorder walk, search, maximum, minimum, predecessor, successor, insert and delete. Implement those BST operations on your own. You also need to include testing code to verify the correctness of your program. In particular, you should test all the operations on a randomly built BST. For this project, each node in a BST should at least four fields: key (called element in the provided code), p, left, and right, representing the key value, and parent, left, and right child nodes of the given node. In addition, key values of all nodes in a BST are assumed to be integers.

Solution

public void deleteMin()

{

if (isEmpty()) return;

root = deleteMin(root);

}

private Node deleteMin(Node x)

{

if (x.left == null) return x.right;

x.left = deleteMin(x.left);

x.N = size(x.left) + size(x.right) + 1;

return x;

}

public void delete(Key key)

{ root = delete(root, key); }

private Node delete(Node x, Key key)

{

if (x == null) return null;

int cmp = key.compareTo(x.key);

if (cmp < 0) x.left = delete(x.left, key);

else if (cmp > 0) x.right = delete(x.right, key);

else

{

if (x.right == null) return x.left;

if (x.left == null) return x.right;

Node t = x;

x = min(t.right); // See page 313.

x.right = deleteMin(t.right);

x.left = t.left;

}

x.N = size(x.left) + size(x.right) + 1;

return x;

}