Question

Redo the binary search tree class to implement lazy deletion. Note carefully that this affects all of the routines. Especially challenging are findMin and findMax, which must now be done recursively.

Answer 1

PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU

class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {

  private static class BinaryNode<AnyType> {

    // Constructors

    BinaryNode(AnyType theElement) {
      this(theElement, null, null);
      deleted = false;
    }

    BinaryNode(
      AnyType theElement,
      BinaryNode<AnyType> lt,
      BinaryNode<AnyType> rt
    ) {
      element = theElement;

      left = lt;

      right = rt;

      deleted = false;
    }

    AnyType element;

    BinaryNode<AnyType> left;

    BinaryNode<AnyType> right;

    //declare an additional boolean instance

    //variable called deleted

    boolean deleted;
  }

  private BinaryNode<AnyType> root;

  public BinarySearchTree() {
    root = null;
  }

  public void makeEmpty() {
    root = null;
  }

  public boolean isEmpty() {
    return root == null;
  }

  public boolean contains(AnyType x) {
    return contains(x, root);
  }

  public AnyType findMin() {
    if (isEmpty()) throw new UnderflowException();

    return findMin(root).element;
  }

  public AnyType findMax() {
    if (isEmpty()) throw new UnderflowException();

    return findMax(root).element;
  }

  public void insert(AnyType x) {
    root = insert(x, root);
  }

  public void remove(AnyType x) {
    root = remove(x, root);
  }

  public void printTree() {
    if (isEmpty()) System.out.println("Empty tree"); else printTree(root);
  }

  //definition of the method contains()

  private boolean contains(AnyType x, BinaryNode<AnyType> t) {
    if (t == null) return false;

    int compareResult = x.compareTo(t.element);

    if (
      compareResult < 0
    ) return contains(x, t.left); else { //recursively calling contains() method
      //If the location found has a node that has been deleted,

      //then tree does not contain value.

      if (t.deleted) return false; else return true; // Otherwise, tree contains value.
    }
  }

  //definition of the method findMin()

  //it is the recursive method.

  private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
    //if the root is null then return null value

    if (t == null) return null;

    //if the root is not null, then check if there are values in

    //the left subtree that have not been deleted

    if (
      hasLeftSubTree(t)
    ) //call findMin with the left child as the argument. //if hasLeftSubTree is true, then recursively

    return findMin(t.left);

    //Otherwise if the root has not been deleted, return the root node.

    if (!t.deleted) return t;

    //if there are undeleted nodes in the right subtree

    //(hasRightSubTree is true), then recursively call

    //findMin with the right child as an argument

    if (hasRightSubTree(t)) return findMin(t.right);

    return null;
  }

  //definition of the method findMax()

  //it is the recursive method.

  private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
    //if the root is null then return null value

    if (t == null) return null;

    //If hasRightSubTree, recursively call findMax on right subtree.

    if (hasRightSubTree(t)) return findMax(t.right);

    //Otherwise if the root has not been deleted, return the root node.

    if (!t.deleted) return t;

    //Otherwise, if hasLeftSubTree, recursively call

    //findMax with the left child as an argument.

    if (hasLeftSubTree(t)) return findMax(t.left);

    return null;
  }

  /* definition of the method hasLeftSubTree()

     * recursive method to find out if there are any undeleted nodes

     * in the left subtree of the node passed in as an argument.

     */

  private boolean hasLeftSubTree(BinaryNode<AnyType> t) {
    //if the root is null then return null value

    if (t == null) return false;

    //If the node is not null and the left child is not null,

    //and the left node is not deleted, then the boolean returns true.

    if (t.left == null) return false;

    if (!t.left.deleted) return true;

    //Otherwise, if the leftSubtree or rightSubtree exists for the left child,

    //then the boolean returns true. Otherwise, it returns false

    //and all nodes in left subtree have been deleted.

    if (hasLeftSubTree(t.left) || hasRightSubTree(t.left)) return true;

    return false;
  }

  /* definition of the method hasRightSubTree()

     * recursive method to find out if there are any undeleted nodes

     * in the right subtree of the node passed in as an argument.

     */

  private boolean hasRightSubTree(BinaryNode<AnyType> t) {
    //if the root is null then return null value

    if (t == null) return false;

    //If the node is not null and the right child is not null,

    //and the right node is not deleted, then the boolean returns true.

    if (t.right == null) return false;

    if (!t.right.deleted) return true;

    //Otherwise, if the leftSubtree or rightSubtree exists for the right child,

    //then the boolean returns true. Otherwise, it returns false

    //and all nodes in right subtree have been deleted.

    if (hasRightSubTree(t.right) || hasLeftSubTree(t.right)) return true;

    return false;
  }

  //definition of the method insert()

  private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
    if (t == null) return new BinaryNode<AnyType>(x, null, null);

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) t.left = insert(x, t.left); else if (
      compareResult > 0
    ) t.right = insert(x, t.right);
    //If the value exists in the tree but in a node in which

    //"deleted" is true, then we mark "deleted" as false.

    else {
      if (t.deleted) t.deleted = false;
    }

    return t;
  }

  //definition of the method remove()

  private BinaryNode<AnyType> 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 not not deleted

      if (
        !t.deleted
      ) t.deleted = true; //change the boolean variable "deleted" to true.
    }

    return t;
  }

  //definition of the method printTree()

  //prints the values of the tree

  private void printTree(BinaryNode<AnyType> t) {
    if (t != null) {
      printTree(t.left);

      System.out.println(t.element);

      printTree(t.right);
    }
  }

  //definition of the method height()

  //returns the height of the tree

  private int height(BinaryNode<AnyType> t) {
    if (t == null) return -1; else return (
      1 + Math.max(height(t.left), height(t.right))
    );
  }

  //definition of the method main()

  //to test the methods

  public static void main(String[] args) {
    //create an object of BinarySearchTree class

    BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();

    //insert the values in the tree

    //using insert method

    tree.insert(50);

    tree.insert(45);

    tree.insert(46);

    tree.insert(78);

    tree.insert(29);

    tree.insert(89);

    tree.insert(41);

    tree.insert(60);

    tree.insert(30);

    tree.insert(98);

    tree.insert(78);

    //print the values of the tree using printTree() method

    System.out.println("The Binary tree is elements is: ");

    tree.printTree();

    //find the maximum and minimum values using the methods

    //findMax() and findMin()

    System.out.println("The maximum element is: " + tree.findMax());

    System.out.println("The minimum element is: " + tree.findMin());
  }
}

class UnderflowException extends RuntimeException {

  public UnderflowException() {}

  public UnderflowException(String message) {
    super(message);
  }
}