Given the reference-based implementation of the binary tree discussed in class (
ID: 3734881 • Letter: G
Question
Given the reference-based implementation of the binary tree discussed in class (the code can be obtained under content->other->binary tree code), add a method to the LinkedBinaryTree named pruneSubtree(p), that removes the entire subtree rooted at position p (update reference variables for all node on the subtree), making sure to update the size variable so that it can reflect the accurate number of nodes on the tree after pruning.
Binary tree:
Goldwasser *
>. */
children. *
exists). *
exists). *
exists). *
}
LinkedBinaryTree:
/*
* Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
*
* Developed for use with the book:
*
* Data Structures and Algorithms in Java, Sixth Edition
* Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
* John Wiley & Sons, 2014
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* Concrete implementation of a binary tree using a node-based, linked structure.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {
//---------------- nested Node class ----------------
/** Nested static class for a binary tree node. */
protected static class Node<E> implements Position<E> {
private E element; // an element stored at this node
private Node<E> parent; // a reference to the parent node (if any)
private Node<E> left; // a reference to the left child (if any)
private Node<E> right; // a reference to the right child (if any)
/**
* Constructs a node with the given element and neighbors.
*
* @param e the element to be stored
* @param above reference to a parent node
* @param leftChild reference to a left child node
* @param rightChild reference to a right child node
*/
public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) {
element = e;
parent = above;
left = leftChild;
right = rightChild;
}
// accessor methods
public E getElement() { return element; }
public Node<E> getParent() { return parent; }
public Node<E> getLeft() { return left; }
public Node<E> getRight() { return right; }
// update methods
public void setElement(E e) { element = e; }
public void setParent(Node<E> parentNode) { parent = parentNode; }
public void setLeft(Node<E> leftChild) { left = leftChild; }
public void setRight(Node<E> rightChild) { right = rightChild; }
} //----------- end of nested Node class -----------
/** Factory function to create a new node storing element e. */
protected Node<E> createNode(E e, Node<E> parent,
Node<E> left, Node<E> right) {
return new Node<E>(e, parent, left, right);
}
// LinkedBinaryTree instance variables
/** The root of the binary tree */
protected Node<E> root = null; // root of the tree
/** The number of nodes in the binary tree */
private int size = 0; // number of nodes in the tree
// constructor
/** Construts an empty binary tree. */
public LinkedBinaryTree() { } // constructs an empty binary tree
// nonpublic utility
/**
* Verifies that a Position belongs to the appropriate class, and is
* not one that has been previously removed. Note that our current
* implementation does not actually verify that the position belongs
* to this particular list instance.
*
* @param p a Position (that should belong to this tree)
* @return the underlying Node instance for the position
* @throws IllegalArgumentException if an invalid position is detected
*/
protected Node<E> validate(Position<E> p) throws IllegalArgumentException {
if (!(p instanceof Node))
throw new IllegalArgumentException("Not valid position type");
Node<E> node = (Node<E>) p; // safe cast
if (node.getParent() == node) // our convention for defunct node
throw new IllegalArgumentException("p is no longer in the tree");
return node;
}
// accessor methods (not already implemented in AbstractBinaryTree)
/**
* Returns the number of nodes in the tree.
* @return number of nodes in the tree
*/
@Override
public int size() {
return size;
}
/**
* Returns the root Position of the tree (or null if tree is empty).
* @return root Position of the tree (or null if tree is empty)
*/
@Override
public Position<E> root() {
return root;
}
/**
* Returns the Position of p's parent (or null if p is root).
*
* @param p A valid Position within the tree
* @return Position of p's parent (or null if p is root)
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
@Override
public Position<E> parent(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getParent();
}
/**
* Returns the Position of p's left child (or null if no child exists).
*
* @param p A valid Position within the tree
* @return the Position of the left child (or null if no child exists)
* @throws IllegalArgumentException if p is not a valid Position for this tree
*/
@Override
public Position<E> left(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getLeft();
}
/**
* Returns the Position of p's right child (or null if no child exists).
*
* @param p A valid Position within the tree
* @return the Position of the right child (or null if no child exists)
* @throws IllegalArgumentException if p is not a valid Position for this tree
*/
@Override
public Position<E> right(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getRight();
}
// update methods supported by this class
/**
* Places element e at the root of an empty tree and returns its new Position.
*
* @param e the new element
* @return the Position of the new element
* @throws IllegalStateException if the tree is not empty
*/
public Position<E> addRoot(E e) throws IllegalStateException {
if (!isEmpty()) throw new IllegalStateException("Tree is not empty");
root = createNode(e, null, null, null);
size = 1;
return root;
}
/**
* Creates a new left child of Position p storing element e and returns its Position.
*
* @param p the Position to the left of which the new element is inserted
* @param e the new element
* @return the Position of the new element
* @throws IllegalArgumentException if p is not a valid Position for this tree
* @throws IllegalArgumentException if p already has a left child
*/
public Position<E> addLeft(Position<E> p, E e)
throws IllegalArgumentException {
Node<E> parent = validate(p);
if (parent.getLeft() != null)
throw new IllegalArgumentException("p already has a left child");
Node<E> child = createNode(e, parent, null, null);
parent.setLeft(child);
size++;
return child;
}
/**
* Creates a new right child of Position p storing element e and returns its Position.
*
* @param p the Position to the right of which the new element is inserted
* @param e the new element
* @return the Position of the new element
* @throws IllegalArgumentException if p is not a valid Position for this tree.
* @throws IllegalArgumentException if p already has a right child
*/
public Position<E> addRight(Position<E> p, E e)
throws IllegalArgumentException {
Node<E> parent = validate(p);
if (parent.getRight() != null)
throw new IllegalArgumentException("p already has a right child");
Node<E> child = createNode(e, parent, null, null);
parent.setRight(child);
size++;
return child;
}
/**
* Replaces the element at Position p with element e and returns the replaced element.
*
* @param p the relevant Position
* @param e the new element
* @return the replaced element
* @throws IllegalArgumentException if p is not a valid Position for this tree.
*/
public E set(Position<E> p, E e) throws IllegalArgumentException {
Node<E> node = validate(p);
E temp = node.getElement();
node.setElement(e);
return temp;
}
/**
* Attaches trees t1 and t2, respectively, as the left and right subtree of the
* leaf Position p. As a side effect, t1 and t2 are set to empty trees.
*
* @param p a leaf of the tree
* @param t1 an independent tree whose structure becomes the left child of p
* @param t2 an independent tree whose structure becomes the right child of p
* @throws IllegalArgumentException if p is not a valid Position for this tree
* @throws IllegalArgumentException if p is not a leaf
*/
public void attach(Position<E> p, LinkedBinaryTree<E> t1,
LinkedBinaryTree<E> t2) throws IllegalArgumentException {
Node<E> node = validate(p);
if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");
size += t1.size() + t2.size();
if (!t1.isEmpty()) { // attach t1 as left subtree of node
t1.root.setParent(node);
node.setLeft(t1.root);
t1.root = null;
t1.size = 0;
}
if (!t2.isEmpty()) { // attach t2 as right subtree of node
t2.root.setParent(node);
node.setRight(t2.root);
t2.root = null;
t2.size = 0;
}
}
/**
* Removes the node at Position p and replaces it with its child, if any.
*
* @param p the relevant Position
* @return element that was removed
* @throws IllegalArgumentException if p is not a valid Position for this tree.
* @throws IllegalArgumentException if p has two children.
*/
public E remove(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
if (numChildren(p) == 2)
throw new IllegalArgumentException("p has two children");
Node<E> child = (node.getLeft() != null ? node.getLeft() : node.getRight() );
if (child != null)
child.setParent(node.getParent()); // child's grandparent becomes its parent
if (node == root)
root = child; // child becomes root
else {
Node<E> parent = node.getParent();
if (node == parent.getLeft())
parent.setLeft(child);
else
parent.setRight(child);
}
size--;
E temp = node.getElement();
node.setElement(null); // help garbage collection
node.setLeft(null);
node.setRight(null);
node.setParent(node); // our convention for defunct node
return temp;
}
} //----------- end of LinkedBinaryTree class -----------
Explanation / Answer
Binary Tree : An information structure in which we have hubs containing information and two references to different hubs, one on the left and one on the right.
Parallel Tree comprise of Nodes
Hubs are only questions of a class and every hub has information and a connection to one side hub and right hub.
Typically we call the beginning hub of a tree as root.
Left and right hub of a Leaf hub focuses to NULL so you will realize that you have come to the finish of the tree.
Paired Search Tree:
Regularly we call it as BST, is a sort of Binary tree which has a unique property.
Hubs littler than root goes to one side of the root and Nodes more prominent than root goes to one side of the root.
Activities:
Insert(int n) : Add a hub the tree with esteem n. Its O(lgn)
Find(int n) : Find a hub the tree with esteem n. Its O(lgn)
Erase (int n) : Delete a hub the tree with esteem n. Its O(lgn)
Show(): Prints the whole tree in expanding request. O(n).
Detail Explanations for the Operations:
Find(int n):
Its extremely straightforward task to perform.
begin from the root and contrast root.data and n
on the off chance that root.data is more prominent than n that implies we have to go to one side of the root.If root.data is littler than n that implies we have to go to one side of the root.if any purpose of time root.data is equivalent to the n then we have discovered the hub, return genuine.
in the event that we reach to the leaves (end of the tree) return false, we didn't discover the component
Insert(int n):
Particularly like discover() task.
To embed a hub our first errand is to discover the place to embed the hub.
Take current = root .
begin from the current and contrast root.data and n
in the event that current.data is more noteworthy than n that implies we have to go to one side of the root.
in the event that current.data is littler than n that implies we have to go to one side of the root.
on the off chance that any purpose of time current is invalid that implies we have come to the leaf hub, embed your hub here with the assistance of parent hub.
Delete(int n):
Confounded than Find() and Insert() tasks. Here we need to manage 3 cases.
Hub to be erased is a leaf hub ( No Children).
Hub to be erased has just a single youngster.
Hub to be erased has two childrens.
Hub to be erased is a leaf hub ( No Children).
its an extremely basic case, if a hub to be erased has no youngsters then simply cross to that hub, monitor parent hub and the side in which the hub exist(left or right) and set parent.left = invalid or parent.right = invalid;
Hub to be erased has just a single kid.
its a marginally complex case. in the event that a hub to be deleted(deleteNode) has just a single youngster then simply navigate to that hub, monitor parent hub and the side in which the hub exist(left or right).
check which side youngster is invalid (since it has just a single tyke).
Say hub to be erased has tyke on its left side . At that point take the whole sub tree from the left side and add it to the parent and the side on which deleteNode exist, see stage 1 and case.
Hub to be erased has two youngsters.
Presently this is very energizing
You just can't supplant the deleteNode with any of its tyke,
What to do now?????
Dont stress we have answer for this
Discover The Successor:
Successor is the hub which will supplant the erased hub. Presently the inquiry is to how to discover it and where to discover it.
Successor is the littler hub in the correct sub tree of the hub to be erased.
Show() : To think about how we are showing hubs in expanding request
public class BinarySearchTree {
public static Node root;
public BinarySearchTree(){
this.root = null;
}
public boolean find(int id){
Node current = root;
while(current!=null){
if(current.data==id){
return true;
}else if(current.data>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
public boolean delete(int id){
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String arg[]){
BinarySearchTree b = new BinarySearchTree();
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("Original Tree : ");
b.display(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4 exists : " + b.find(4));
System.out.println("Delete Node with no children (2) : " + b.delete(2));
b.display(root);
System.out.println(" Delete Node with one child (4) : " + b.delete(4));
b.display(root);
System.out.println(" Delete Node with Two children (10) : " + b.delete(10));
b.display(root);
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.