Chapter 26, Problem 26.5PE

Program Plan Intro

Program Plan:

• Include the required import statement.
• Define the main class.
  • Define the main method using public static main.
    • Allocate memory to the class “Test”.
    • Define the “Test” class.
    • Declare the object for the AVLTree2.
    • Get the input integers from the user.
    • Get the “k” value from the user.
    • Display the results.
  • Define the “AVLTree2” class.
    • Create a default constructor and constructor.
    • The “createNewNode” method is used to return the “AVLTree2” value.
    • The “rootSize” method is used to return the size of the root.
    • The “find” method is used to return searching element.
    • The “find” method is used to search the given element in the AVL tree and then return that element.
    • Define “insert” method.
      • Override the “insert” method in the program.
      • Check if the element is already in the tree or not.
      • The element is not in the tree balance from element to the root.
      • Return the inserted element.
    • Define “updateHeight” method.
      • If the leaf node is null, set the height of the tree is 0.
      • If the left subtree is null, calculate the height and set it into the variable.
      • If the right subtree is null, calculate the height and set it into the variable.
      • Otherwise, calculate the total height of the tree and set it into the variable.
    • Define “updateSize” method.
      • If the leaf node is null, set the size of the tree is 1.
      • If the left subtree is null, calculate the size and set it into the variable.
      • If the right subtree is null, calculate the size and set it into the variable.
      • Otherwise, calculate the total size of the tree and set it into the variable.
    • Define “balancePath” method.
      • Declare the array list.
      • Check the size.
      • Call the “updateHeight” and “updateSize” methods.
      • Balance the nodes in the path from the specified node to the root is necessary.
    • Define “balanceFactor” method.
      • If the node has no right subtree, return the height.
      • If the node has no left subtree, return the height.
      • Otherwise return full height.
    • Define “balanceLL” method.
      • Here “A” is left heavy and “B” is right heavy.
      • If “A” is equal to “root”, then assign “B” to “root”.
      • Otherwise, if the “parentOfA.left” is equal to “A”, then assign “B” to “parentOfA.left”.
        • Otherwise, assign “B” to “parentOfA.right”.
      • Make “T1” as left subtree of A and make “A” the left child of “B”.
      • Call the methods.
    • Define “balanceLR” method.
      • Here “A” is left heavy and “B” is right heavy.
      • If “A” is equal to “root”, then assign “C” to “root”.
      • Otherwise, if the “parentOfA.left” is equal to “A”, then assign “C” to “parentOfA.left”.
        • Otherwise, assign “C” to “parentOfA.right”.
      • Make “T3” as left subtree of A and make “T2” the left child of “B”.
    • Call the methods.
    • Define “balanceRR” method.
      • Here “A” is left heavy and “B” is right heavy.
      • If “A” is equal to “root”, then assign “B” to “root”.
      • Otherwise, if the “parentOfA.left” is equal to “A”, then assign “B” to “parentOfA.left”.
        • Otherwise, assign “B” to “parentOfA.right”.
      • Make “T2” as right subtree of “A”.
      • Call the methods.
    • Define “balanceRL” method.
      • Here “A” is left heavy and “B” is right heavy.
      • If “A” is equal to “root”, then assign “C” to “root”.
      • Otherwise, if the “parentOfA.left” is equal to “A”, then assign “C” to “parentOfA.left”.
        • Otherwise, assign “C” to “parentOfA.right”.
      • Make “T3” as left subtree of A and make “T2” the right subtree of “B”.
      • Call the methods.
    • Define “delete” method.
      • If the “root” is null, the element is not in the tree.
      • Locate the node to be deleted and also allocate its parent node.
      • If the “current” value is null, then the element is not in the tree.
      • The “current” has no left children, then connect the parent with the right child of the current node.
      • The “current” has a left children, then locate the rightmost node in the left subtree of the current node and also its parent.
      • Replace the element in current by the element in rightmost.
      • Balance the tree if necessary.
      • Return the inserted element.
    • Define “AVLTree2Node” method.
      • Declare the variable.
      • Override the method.
  • Define the “BST2” class.
    • Declare the required variables.
    • Create a default BST2 class.
    • Create a binary tree from an array of objects.
    • The “height” method will return the height of the tree.
    • Define the “search” method.
      • Start the traverse from the root of the tree.
      • If the search element is in the left subtree set that value in “current” variable otherwise set the “current” variable as right subtree value.
    • Define the “insert” method.
      • If the root is null create the tree otherwise insert the value into left or right subtree.
    • Define the “createNewNode”
      • Return the result of new node creations.
    • Define the “inorder”
      • Inorder traverse from the root.
    • Define the protected “inorder” method
      • Traverse the tree according to the inorder traversal concept.
    • Define the “postorder”
      • Postorder traverse from the root.
    • Define the protected “postorder” method
      • Traverse the tree according to the postorder traversal concept.
    • Define the “preorder”
      • Preorder traverse from the root.
    • Define the protected “preorder” method
      • Traverse the tree according to the preorder traversal concept.
    • Define the “TreeNode” class
      • Declare the required variables.
      • Define the constructor.
    • Define the “getSize” method.
      • Return the size.
    • Define the “getRoot” method
      • Return the root.
    • Define the “java.util.ArrayList” method.
      • Create an object for the array list.
      • If the “current” is not equal to null, add the value to the list.
      • If the “current” is less than 0, set the “current” as left subtree element otherwise set the “current” as right subtree element.
      • Return the list.
    • Define the “delete” method.
      • If the “current” is not equal to null, add the value to the list.
      • If the “current” is less than 0, delete the “current” as left subtree element otherwise delete the “current” as right subtree element.
      • Return the list.
    • Define the “iterator” method.
      • Call the “inorderIterator” and return the value.
    • Define the “inorderIterator”
      • Create an object for that method and return the value
    • Define the “inorderIterator” class.
      • Declare the variables.
      • Define the constructor.
        • Call the “inorder” method.
      • Define the “inorder” method.
        • Call the inner “inorder” method with the argument.
      • Define the TreeNode “inorder” method.
        • If the root value is null return the value, otherwise add the value into the list.
      • Define the “hasNext” method
        • If the “current” value is less than size of the list return true otherwise return false.
      • Define the “next” method
        • Return the list.
      • Define the “remove” method.
        • Call the delete method.
        • Clear the list then call the “inorder” method.
    • Define the “clear” method
      • Set the values to the variables

Tree.java:

• Include the required import statement
• Define the interface in “Tree” class.
  • Declare the required methods.
  • Define the required methods.

Program Description Answer

The below program will get the input integers from the user and find the k^th minimum value in the list as follows:

Explanation of Solution

Program:

“Tree.java” is referred in Listing 25.3 from chapter 25 (Page No.:958).

//Test.java

//import statement

import java.util.Collection;

import java.util.Scanner;

//class Test

public class Test

{

// main method

public static void main(String[] args)

{

//create the objects

AVLTree2<Double> tree = new AVLTree2<>();

Scanner input = new Scanner(System.in);

/* prompt the user to enter 15 integers and store them in the tree*/

System.out.print("Enter 15 numbers: ");

for (int i = 0; i < 15; i++)

{

//insert into the tree

tree.insert(input.nextDouble());

}

//get the "k" number from the user

System.out.print("Enter k: ");

double k = input.nextDouble();

//display the output

System.out.println("The " + (int)k + "th smallest number is " + tree.find(k));

}

}

//definition of "AVLTree2" class

class AVLTree2<E extends Comparable<E>> extends BST2<E>

{

//create a default constructor

public AVLTree2()

{

}

//create a constructor

public AVLTree2(E[] objects)

{

//rebuild the objects

super(objects);

}

@Override

//definition of "createNewNode" method

protected AVLTree2Node<E> createNewNode(E e)

{

//return statement

return new AVLTree2Node<E>(e);

}

//definition of "rootSize" method

public int rootSize()

{

//return statement

return ((AVLTree2Node<E>) this.root).size;

}

//definition of "find" method

public E find(double k)

{

//return statement

return find(k, (AVLTree2Node<E>) this.root);

}

//definition of "find" method

public E find(double k, AVLTree2Node<E> node)

{

//check the condition

if (k < 0 || k > this.size)

{

//return statement

return null;

}

//check the condition

else if (node.left == null && k == 1)

{

//return statement

return node.element;

}

//check the condition

else if (node.left == null && k == 2)

{

//return statement

return node.right.element;

}

//check the condition

else if (k <= ((AVLTree2Node<E>) node.left).size)

{

//return statement

return find(k, (AVLTree2Node<E>) node.left);

}

//check the condition

else if (k == (((AVLTree2Node<E>) node.left).size) + 1)

{

//return statement

return node.element;

}

//otherwise

else

{

//return statement

return find(k - (((AVLTree2Node<E>) node.left).size) - 1,(AVLTree2Node<E>) node.right);

}

}

@Override

//definition of "insert" method 

public boolean insert(E e)

{

//declare the variable

boolean successful = super.insert(e);

//check the condition

if (!successful)

{

//return statement

return false;

}

else

{

//call the method

balancePath(e);

}

//return statement

return true;

}

//definition of "updateHeight" method

private void updateHeight(AVLTree2Node<E> node)

{

//check the condition

if (node.left == null && node.right == null)

{

//assign the value

node.height = 0;

}

//check the condition

else if (node.left == null)

{

// calculate and assign the value

node.height = 1 + ((AVLTree2Node<E>) (node.right)).height;

}

//check the condition

else if (node.right == null)

{

//calculate and assign the value

node.height = 1 + ((AVLTree2Node<E>) (node.left)).height;

}

else

{

//calculate and assign the value

node.height = 1 + Math.max(((AVLTree2Node<E>) (node.right)).height, ((AVLTree2Node<E>) (node.left)).height);

}

}

//definition of "updateSize" method

private void updateSize(AVLTree2Node<E> node)

{

//check the condition

if (node.left == null && node.right == null)

{

//assign the value

node.size = 1;

}

//check the condition

else if (node.left == null)

{

//calculate and assign the value

node.size = 1 + ((AVLTree2Node<E>) (node.right)).size;

}

//check the condition

else if (node.right == null)

{

//calculate and assign the value

node.size = 1 + ((AVLTree2Node<E>) (node.left)).size;

}

else

{

//calculate and assign the value

node.size = 1 + (((AVLTree2Node<E>) (node.right)).size) + (((AVLTree2Node<E>) (node.left)).size);

}

}

//definition of "balancePath" method

private void balancePath(E e)

{

//set the path

java.util.ArrayList<TreeNode<E>> path = path(e);

//check the condition

for (int i = path.size() - 1; i >= 0; i--)

{

//set the path

AVLTree2Node<E> A = (AVLTree2Node<E>) (path.get(i));

//call the method

updateHeight(A);

updateSize(A);

/*check the condition and set it into the "parentOFA" variable*/

AVLTree2Node<E> parentOfA = (A == root) ? null : (AVLTree2Node<E>) (path

.get(i - 1));

//check the condition

switch (balanceFactor(A))

{

case -2:

//check the condition

if (balanceFactor((AVLTree2Node<E>) A.left) <= 0)

{

// perform LL rotation

balanceLL(A, parentOfA);

}

else

{

// perform LR rotation

balanceLR(A, parentOfA);

}

break;

case +2:

//check the condition

if (balanceFactor((AVLTree2Node<E>) A.right) >= 0)

{

// perform RR rotation

balanceRR(A, parentOfA);

}

else

{

// perform RL rotation

balanceRL(A, parentOfA);

}

}

}

}

//definition of "balanceFactor" method

private int balanceFactor(AVLTree2Node<E> node)

{

//check the condition

if (node.right == null)

{

//return statement

return -node.height;

}

//check the condition

else if (node.left == null)

{

//return statement

return +node.height;

}

else

{

//return statement

return ((AVLTree2Node<E>) node.right).height

- ((AVLTree2Node<E>) node.left).height;

}

}

//defintion of "balanceLL" method

private void balanceLL(TreeNode<E> A, TreeNode<E> parentOfA)

{

//set the value

TreeNode<E> B = A.left;

//check the condition

if (A == root)

{

//set the value

root = B;

}

else

{

//check the condition

if (parentOfA.left == A)

{

//set the value

parentOfA.left = B;

}

else

{

//set the value

parentOfA.right = B;

}

}

//set the value

A.left = B.right;

B.right = A;

// call the method and adjust heights

updateHeight((AVLTree2Node<E>) A);

updateSize((AVLTree2Node<E>) A);

updateHeight((AVLTree2Node<E>) B);

updateSize((AVLTree2Node<E>) B);

}

//definition of "balanceLR" method

private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA)

{

//set the value

TreeNode<E> B = A.left;

TreeNode<E> C = B.right;

//check the condition

if (A == root)

{

//set the value

root = C;

}

else

{

//check the condition

if (parentOfA.left == A)

{

//set the value

parentOfA.left = C;

}

else

{

//set the value

parentOfA.right = C;

}

}

//set the values

A.left = C.right;

B.right = C.left;

C.left = B;

C.right = A;

// call the method and adjust heights

updateHeight((AVLTree2Node<E>) A);

updateHeight((AVLTree2Node<E>) B);

updateHeight((AVLTree2Node<E>) C);

updateSize((AVLTree2Node<E>) A);

updateSize((AVLTree2Node<E>) B);

updateSize((AVLTree2Node<E>) C);

}

//definition of "balanceRR" method

private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA)

{

//set the value

TreeNode<E> B = A.right;

//check the condition

if (A == root)

{

//set the value

root = B;

}

else

{

//check the condition

if (parentOfA.left == A)

{

//set the value

parentOfA.left = B;

}

else

{

//set the value

parentOfA.right = B;

}

}

//set the value

A.right = B.left;

B.left = A;

//call the methods

updateHeight((AVLTree2Node<E>) A);

updateHeight((AVLTree2Node<E>) B);

updateSize((AVLTree2Node<E>) A);

updateSize((AVLTree2Node<E>) B);

}

//definition of "balanceRL" method

private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA)

{

//set the value

TreeNode<E> B = A.right;

TreeNode<E> C = B.left;

//check the condition

if (A == root)

{

//set the value

root = C;

}

else

{

//check the condition

if (parentOfA.left == A)

{

//set the value

parentOfA.left = C;

}

else

{

//set the value

parentOfA.right = C;

}

}

//set the values

A.right = C.left;

B.left = C.right;

C.left = A;

C.right = B;

// call the methods and adjust heights

updateHeight((AVLTree2Node<E>) A);

updateHeight((AVLTree2Node<E>) B);

updateHeight((AVLTree2Node<E>) C);

updateSize((AVLTree2Node<E>) A);

updateSize((AVLTree2Node<E>) B);

updateSize((AVLTree2Node<E>) C);

}

@Override

//definition of "delete" method

public boolean delete(E element)

{

//check the condition

if (root == null)

{

//return statement

return false;

}

// declare the variables

TreeNode<E> parent = null;

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//check the condition

if (element.compareTo(current.element) < 0)

{

//set the value

parent = current;

current = current.left;

}

//check the condition

else if (element.compareTo(current.element) > 0)

{

//set the value

parent = current;

current = current.right;

}

else

{

//break statement

break;

}

}

//check the condition

if (current == null)

{

//return statement

return false;

}

//check the condition

if (current.left == null)

{

//check the condition

if (parent == null)

{

//set the value

root = current.right;

}

else

{

//check the condition

if (element.compareTo(parent.element) < 0)

{

//set the value

parent.left = current.right;

}

else

{

//set the value

parent.right = current.right;

}

//set the value

balancePath(parent.element);

}

}

else

{

//set the value

TreeNode<E> parentOfRightMost = current;

TreeNode<E> rightMost = current.left;

//check the condition

while (rightMost.right != null)

{

//set the value

parentOfRightMost = rightMost;

rightMost = rightMost.right;

}

//set the value

current.element = rightMost.element;

//check the condition

if (parentOfRightMost.right == rightMost)

{

//set the value

parentOfRightMost.right = rightMost.left;

}

else

{

//set the value

parentOfRightMost.left = rightMost.left;

}

// balance the tree if necessary

balancePath(parentOfRightMost.element);

}

//decrement the "size"

size--;

//return statement

return true;

}

//definition of "AVLTree2Node" class

protected static class AVLTree2Node<E extends Comparable<E>> extends

BST2.TreeNode<E>

{

//declare the required variables

protected int height = 0;

protected int size = 0;

//constructor

public AVLTree2Node(E o)

{

//override the method

super(o);

}

}

}

//definition of "BST" class

class BST2<E extends Comparable<E>> implements Tree<E>

{

//declare the variables

protected TreeNode<E> root;

protected int size = 0;

//create a default binary tree

public BST2()

{

}

//create a binary tree from an array of objects

public BST2(E[] objects)

{

//check the condition

for (int i = 0; i < objects.length; i++)

{

//insert the values

insert(objects[i]);

}

}

@Override

//definition of "search" method

public boolean search(E e)

{

//start from the root

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

current = current.left;

}

//check the condition

else if (e.compareTo(current.element) > 0)

{

//set the value

current = current.right;

}

//otherwise

else

{

//return statement

return true;

}

}

//return statement

return false;

}

@Override

//definition of "insert" method

public boolean insert(E e)

{

//check the condition

if (root == null)

{

//create a new root

root = createNewNode(e);

}

//otherwise

else

{

// locate the parent node

TreeNode<E> parent = null;

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

parent = current;

current = current.left;

}

//check the condition

else if (e.compareTo(current.element) > 0)

{

//set the value

parent = current;

current = current.right;

}

else

{

//return statement

return false;

}

}

//check the condition

if (e.compareTo(parent.element) < 0)

{

//create a new node

parent.left = createNewNode(e);

}

else

{

//create a new node

parent.right = createNewNode(e);

}

}

//increment the size

size++;

//return statement

return true;

}

//definition of "createNewNode"

protected TreeNode<E> createNewNode(E e)

{

//return the statement

return new TreeNode<E>(e);

}

@Override

//definition of "inorder"

public void inorder()

{

//inorder traverse from the root

inorder(root);

}

//definition of inorder

protected void inorder(TreeNode<E> root)

{

//check the condition

if (root == null)

{

//return statement

return;

}

// inorder traversal from a subtree

inorder(root.left);

//display the element

System.out.print(root.element + " ");

// inorder traversal from a subtree

inorder(root.right);

}

@Override

// definition of "postoder"

public void postorder()

{

// postorder traversal from the root

postorder(root);

}

// definition of "postorder"

protected void postorder(TreeNode<E> root)

{

//check the condition

if (root == null)

{

//return statement

return;

}

//postorder traversal from a subtree

postorder(root.left);

postorder(root.right);

//display the element

System.out.print(root.element + " ");

}

@Override

//definition of "preorder"

public void preorder()

{

// preorder traversal from the root

preorder(root);

}

//definition of "preorder"

protected void preorder(TreeNode<E> root)

{

//check the condition

if (root == null)

{

//return statement

return;

}

//display the value

System.out.print(root.element + " ");

// preorder traversal from a subtree

preorder(root.left);

preorder(root.right);

}

//definition of "TreeNode" class

public static class TreeNode<E extends Comparable<E>>

{

//declare the variables

protected E element;

protected TreeNode<E> left;

protected TreeNode<E> right;

//definition of constructor

public TreeNode(E e)

{

//set the value

element = e;

}

}

@Override

// definition of "getSize" method

public int getSize()

{

//return statement

return size;

}

// definition of "getRoot" method

public TreeNode getRoot()

{

//return statement

return root;

}

// definition of method

public java.util.ArrayList<TreeNode<E>> path(E e)

{

//create an object

java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();

// start from the root

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//add the node to the list

list.add(current);

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

current = current.left;

}

//check the condition

else if (e.compareTo(current.element) > 0)

{

//set the value

current = current.right;

}

else

//break statement

break;

}

//return statement

return list;

}

@Override

//definition of "delete" method

public boolean delete(E e)

{

// declare the variables

TreeNode<E> parent = null;

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

parent = current;

current = current.left;

}

//check the condition

else if (e.compareTo(current.element) > 0)

{

//set the value

parent = current;

current = current.right;

}

else

//break statement

break;

}

//check the condition

if (current == null)

return false;

//check the condition

if (current.left == null)

{

//check the condition

if (parent == null)

{

//set the value

root = current.right;

}

else

{

//check the condition

if (e.compareTo(parent.element) < 0)

//set the value

parent.left = current.right;

else

//set the value

parent.right = current.right;

}

}

else

{

//set the value

TreeNode<E> parentOfRightMost = current;

TreeNode<E> rightMost = current.left;

//check the condition

while (rightMost.right != null)

{

//set the value

parentOfRightMost = rightMost;

rightMost = rightMost.right;

}

//set the value

current.element = rightMost.element;

//check the condition

if (parentOfRightMost.right == rightMost)

//set the value

parentOfRightMost.right = rightMost.left;

else

//set the value

parentOfRightMost.left = rightMost.left;

}

//decrement the "size"

size--;

//return statement

return true;

}

@Override

//definition of "inorderIterator"

public java.util.Iterator<E> iterator()

{

//return statement

return new InorderIterator();

}

// definition of class "InorderIterator"

class InorderIterator implements java.util.Iterator

{

// store the elements in a list

private java.util.ArrayList<E> list = new java.util.ArrayList<E>();

//declare the variable

private int current = 0;

//constructor

public InorderIterator()

{

//call the method

inorder();

}

//definition of inorder traversal from the root

private void inorder()

{

//call the method

inorder(root);

}

/*definition of inorder traversal from a subtree */

private void inorder(TreeNode<E> root)

{

//check the condition

if (root == null)

//return statement

return;

//call the method

inorder(root.left);

//add the value to the list

list.add(root.element);

//call the method

inorder(root.right);

}

//definition of "hasNext"

public boolean hasNext()

{

//check the condition

if (current < list.size())

//return statement

return true;

//return statement

return false;

}

//definition of "next" method

public Object next()

{

//return statement

return list.get(current++);

}

// definition of "remove" method

public void remove()

{

//delete the current element

delete(list.get(current));

// clear the list

list.clear();

// rebuild the list

inorder();

}

}

// definition of "clear" method

public void clear()

{

//set the values

root = null;

size = 0;

}

}

Sample Output

Enter 15 numbers: 3

5

1

8

4

7

12

10

9

6

11

14

0

15

2

Enter k: 4

The 4th smallest number is 3.0