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);
}
}
```

Create an add method for the BST (Binary Search Tree) class.
add(self, new_value: object) -> None:
"""This method adds new value to the tree, maintaining BST
property. Duplicates must be allowed and placed in the right
subtree."""
Example #1: tree = BST()
print(tree) tree.add(10)
tree.add(15)
tree.add(5)
print(tree)
tree.add(15)
tree.add(15)
print(tree)
tree.add(5)
print(tree)
Output:
TREE in order { }
TREE in order { 5, 10, 15 }
TREE in order { 5, 10, 15, 15, 15 }
TREE in order {...

In this lab, you will write a program that creates a binary
search tree based on user input. Then, the user will indicate what
order to print the values in. **Please write in C code**
Start with the bst.h and bst.c base code provided to you. You
will need to modify the source and header file to complete this
lab.
bst.h:
#ifndef BST_H
#define BST_H
typedef struct BSTNode
{
int value;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
BSTNode*...

This assignment involves using a binary search tree (BST) to
keep track of all words in a text document. It produces a
cross-reference, or a concordance. This is very much like
assignment 4, except that you must use a different data structure.
You may use some of the code you wrote for that assignment, such as
input parsing, for this one.
Remember that in a binary search tree, the value to the left of
the root is less than the...

Take a look at the file GenericMethods.java.
There are three methods you must implement:
·public static <T extends
Comparable<T>> int findMin(T[] arr): Iterate through the
array to find the index of the smallest element in the array. If
there are two elements with the smallest value, the method should
return the index of the first one. The method should run in
O(n).
·public static <T extends
Comparable<T>> int findMinRecursive(T[] arr): Should
behave just like findMin, but should be implemented
recursively....

The main goal is to implement two recursive methods, each is
built to manipulate linked data structures. To host these methods
you also have to define two utterly simplified node classes.
1.) Add a class named BinaryNode to the
project. This class supports the linked representation of binary
trees. However, for the BinaryNode class
Generic implementation not needed, the nodes will store integer
values
The standard methods will not be needed in this exercise except
the constructor
2.) Add a...

Complete the redblacktree in Java.
Add a public boolean isBlack field to the Node inner
class. Make every Node object have a false isBlack field, all new
node is red by default.
In the end of the insert method, set the root node of
your red black tree to be black.
Implement the rotate() and recolor() functions, and
create tests for them in a separate class.
import java.util.LinkedList;
public class BinarySearchTree<T extends
Comparable<T>> {
protected static class Node<T> {
public...

import java.util.ArrayList;
/*
Rules:
1. Allow Tester to iterate
through all nodes using the in-order traversal as the
default.
This
means, in Tester the following code should work for an instance of
this class
called bst
that is storing Student objects for the data:
BinarySearchTree_Lab08<String> bst = new
BinarySearchTree_Lab08<String>();
bst.add("Man");
bst.add("Soda"); bst.add("Flag");
bst.add("Home");
bst.add("Today"); bst.add("Jack");
...

STRICT DOWNVOTE IF NOT DONE FULLY, WILL REPORT ALSO IF
COPY PASTED OR MODIFIED ANSWER Develop a class, using
templates, to provide functionality for a set of recursive
functions. The functions specified as recursive must be written
recursively (not iterativly). The UML class specifications are
provided below. A main will be provided. Additionally, a make file
will need to be developed and submitted. ● Recursion Set Class The
recursion set template class will implement the template functions.
recursionSet -length: int...

Please read the article and answear about
questions.
Determining the Value of the Business
After you have completed a thorough and exacting investigation,
you need to analyze all the infor- mation you have gathered. This
is the time to consult with your business, financial, and legal
advis- ers to arrive at an estimate of the value of the business.
Outside advisers are impartial and are more likely to see the bad
things about the business than are you. You should...

Delta airlines case study
Global strategy. Describe the current global
strategy and provide evidence about how the firms resources
incompetencies support the given pressures regarding costs and
local responsiveness. Describe entry modes have they usually used,
and whether they are appropriate for the given strategy. Any key
issues in their global strategy?
casestudy:
Atlanta, June 17, 2014. Sea of Delta employees and their
families swarmed between food trucks, amusement park booths, and
entertainment venues that were scattered throughout what would...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 29 minutes ago

asked 49 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago