Question

1 Approved Answer

Posted on Sep 23, 2024

Here are 4 classes: AVLtree, BinarySearchTree, BinaryNode, and TreePrinter. None of them need to be modified. Please make a tester with a main method for

Here are 4 classes: AVLtree, BinarySearchTree, BinaryNode, and TreePrinter. None of them need to be modified. Please make a tester with a main method for these classes to print out all the AVL and Binary Search Trees.

*****************************************AVLTREE:****************************************************************************************************

public class AVLTree> extends BinarySearchTree { private static final int ALLOWED_IMBALANCE = 1;

private boolean shouldPrintRotations;

public AVLTree() { this(false); }

public AVLTree(boolean shouldPrintRotations) { this.shouldPrintRotations = shouldPrintRotations; }

public boolean isBalanced() { return isBalanced(root); }

private boolean isBalanced(BinaryNode root) { if(root == null) { return true; } else { int leftHeight = height(root.getLeft()); int rightHeight = height(root.getRight()); return Math.abs(leftHeight - rightHeight) <= 1; } }

@Override protected BinaryNode insert(T data, BinaryNode root) { return balance(super.insert(data, root)); }

@Override protected BinaryNode remove(T data, BinaryNode root) { return balance(super.remove(data, root)); }

private BinaryNode balance(BinaryNode root) { if(root == null) { return null; }

if(height(root.getLeft()) - height(root.getRight()) > 1) { if(height(root.getLeft().getLeft()) >= height(root.getLeft().getRight())) { root = singleRightRotation(root); } else { root = doubleLeftRightRotation(root); } } else if(height(root.getRight()) - height(root.getLeft()) > 1) { if(height(root.getRight().getRight()) >= height(root.getRight().getLeft())) { root = singleLeftRotation(root); } else { root = doubleRightLeftRotation(root); } }

return root; }

private BinaryNode singleRightRotation(BinaryNode k2) { if(shouldPrintRotations) { System.out.println("Single Right Rotation: " + k2.getData()); } BinaryNode k1 = k2.getLeft(); k2.setLeft(k1.getRight()); k1.setRight(k2); k2.setHeight(Math.max(height(k2.getLeft()), height(k2.getRight())) + 1); k1.setHeight(Math.max(height(k1.getLeft()), k2.getHeight()) + 1); return k1; }

private BinaryNode singleLeftRotation(BinaryNode k1) { if(shouldPrintRotations) { System.out.println("Single Left Rotation: " + k1.getData()); } BinaryNode k2 = k1.getRight(); k1.setRight(k2.getLeft()); k2.setLeft(k1); k1.setHeight(Math.max(height(k1.getLeft()), height(k1.getRight())) + 1); k2.setHeight(Math.max(height(k2.getRight()), k1.getHeight()) + 1); return k2; }

private BinaryNode doubleLeftRightRotation(BinaryNode k3) { if(shouldPrintRotations) { System.out.println("Double Left-Right Rotation: " + k3.getData()); } k3.setLeft(singleLeftRotation(k3.getLeft())); return singleRightRotation(k3); }

private BinaryNode doubleRightLeftRotation(BinaryNode k1) { if(shouldPrintRotations) { System.out.println("Double Right-Left Rotation: " + k1.getData()); } k1.setRight(singleRightRotation(k1.getRight())); return singleLeftRotation(k1); } }

*************************************************************BINARYSEARCHTREE*****************************************************************************************************

import java.util.Comparator; public class BinarySearchTree> { protected BinaryNode root; public BinarySearchTree() { root = null; } public void empty() { root = null; } public boolean isEmpty(){ return root == null; } public BinaryNode getRoot(){ return root; } public int height() { return height(root); } protected int height(BinaryNode root) { if(root == null) { return -1; } else { return Math.max(height(root.getLeft()), height(root.getRight())) + 1; } } public boolean contains(T data){ return contains(data, root); } protected boolean contains(T data, BinaryNode root){ if(root == null){ return false; } int compareResult = root.getData().compareTo(data); if(compareResult > 0){ return contains(data, root.getLeft()); } else if(compareResult < 0){ return contains(data, root.getRight()); } else{ return true; } } public T findMin() { BinaryNode node = findMin(root); return node == null ? null : node.getData(); } protected BinaryNode findMin(BinaryNode root) { if(root == null) { return null; } else if(root.getLeft() == null) { return root; } else { return findMin(root.getLeft()); } } public T findMax() { BinaryNode node = findMax(root); return node == null ? null : node.getData(); } protected BinaryNode findMax(BinaryNode root) { if(root == null) { return null; } else if(root.getRight() == null) { return root; } else { return findMin(root.getRight()); } }

public void insert(T data) { root = insert(data, root); }

protected BinaryNode insert(T data, BinaryNode root) { if(root == null) { return new BinaryNode<>(data); } int compareResult = root.getData().compareTo(data);

if(compareResult > 0) { root.setLeft(insert(data, root.getLeft())); } else if(compareResult < 0) { root.setRight(insert(data, root.getRight())); } return root; } public void remove(T data) { root = remove(data, root); } protected BinaryNode remove(T data, BinaryNode root) { if(root == null) { return null; } int compareResult = root.getData().compareTo(data); if(compareResult > 0) { root.setLeft(remove(data, root.getLeft())); } else if(compareResult < 0) { root.setRight(remove(data, root.getRight())); } else if(root.getLeft() != null && root.getRight() != null) { root.setData(findMin(root.getRight()).getData()); root.setRight(remove(root.getData(), root.getRight())); } else { root = root.getLeft() != null ? root.getLeft() : root.getRight(); } return root; } public void printTree() { printTree(root); } protected void printTree(BinaryNode root) { if(root != null) { printTree(root.getLeft()); System.out.println(root.getData()); printTree(root.getRight()); } } }

******************************************************************BINARYNODE**********************************************************************************************************

public class BinaryNode> { private T data; private int height; private BinaryNode left; private BinaryNode right;

public BinaryNode(T data) { this(data, null, null); }

public BinaryNode(T data, BinaryNode left, BinaryNode right) { this.data = data; this.left = left; this.right = right; this.height = 0; }

public T getData() { return data; }

public void setData(T data) { this.data = data; }

public BinaryNode getLeft() { return left; }

public void setLeft(BinaryNode left) { this.left = left; }

public BinaryNode getRight() { return right; }

public void setRight(BinaryNode right) { this.right = right; }

public int getHeight() { return height; }

public void setHeight(int height) { this.height = height; } }

**************************************************************************TREEPRINTER*************************************************************************************************

public class TreePrinter { private static final int MAX_LEVELS = 6; private BinarySearchTree tree; // the tree private int height; // its height // Powers of 2 private static int POWERS_OF_2[] = new int[MAX_LEVELS+2]; static { int power = 1; for (int i = 0; i < MAX_LEVELS + 2; i++) { POWERS_OF_2[i] = power; power *= 2; } } /** * Constructor * @param tree the tree to print. */ public TreePrinter(BinarySearchTree tree) { this.tree = tree; this.height = tree.height(); } /** * Print the tree using a level-order traversal. * @param label the label to print before the tree. */ public void print(String label) { System.out.println(label);

// Queue of nodes at this level. BinaryNode thisLevelNodes[] = (BinaryNode[]) new BinaryNode[1]; int offset = POWERS_OF_2[(height+1)]-1; thisLevelNodes[0] = tree.getRoot(); // Loop to print each level of nodes. for (int level = 0; level <= height; level++) { if (level > MAX_LEVELS) { System.out.println("*** Too many levels to print. ***"); break; } // Print node data. printData(level, offset, thisLevelNodes); if (level != height) { // Print outgoing pointers /\ from each parent node. printOutgoingPointers(level, offset, thisLevelNodes); offset = POWERS_OF_2[height - level] - 1; // Print connecting dashes ---- if (level < height-1) { printConnectingDashes(level, offset, thisLevelNodes); } // Print incoming pointers / and \ to each child node. printIncomingPointers(level, offset, thisLevelNodes); // Prepare the next level of nodes. thisLevelNodes = nextLevel(level, thisLevelNodes); } } } /** * Print node data. * @param level the current level * @param offset the current offset * @param levelNodes the current level of nodes */ private void printData(int level, int offset, BinaryNode levelNodes[]) { printSpaces(offset); int k = POWERS_OF_2[level]; for (int i = 0; i < k; i++) { BinaryNode node = levelNodes[i]; if (node != null) { System.out.printf("%3d ", node.getData()); } else { System.out.print(" "); } // Space over to the next node in this level. if (i < k-1) printSpaces(2*offset - 2); } System.out.println(); } /** * Print outgoing pointers /\ from each non-null parent node. * @param level the current level * @param offset the current offset * @param levelNodes the current level of nodes */ private void printOutgoingPointers(int level, int offset, BinaryNode levelNodes[]) { printSpaces(offset); int k = POWERS_OF_2[level]; for (int i = 0; i < k; i++) { BinaryNode node = levelNodes[i]; // Has left child: print / if ((node != null) && (node.getLeft() != null)) { System.out.print(" /"); } // No left child: print space else { System.out.print(" "); } // Has right child: print \ if ((node != null) && (node.getRight() != null)) { System.out.print("\\ "); } // No right child: print space else { System.out.print(" "); } // Space over to the next node in this level. if (i < k-1) printSpaces(2*offset-2); } System.out.println(); } /** * Print the connecting dashes between * an outgoing pointer and an incoming pointer. * @param level the current level * @param offset the current offset * @param levelNodes the current level of nodes */ private void printConnectingDashes(int level, int offset, BinaryNode levelNodes[]) { if (offset > 1) printSpaces(offset); int k = POWERS_OF_2[level]; for (int i = 0; i < k; i++) { BinaryNode node = levelNodes[i]; // Has left child: print dashes if ((node != null) && (node.getLeft() != null)) { printSpaces(3); printDashes(offset-1); } // No left child: print spaces else { printSpaces(offset+2); } // Has right child: print dashes if ((node != null) && (node.getRight() != null)) { printSpaces(2); printDashes(offset-1); } // No right child: print spaces else { printSpaces(offset+1); } // Space over to the next node in this level. if (i < k-1) printSpaces(2*offset+1); } System.out.println(); } /** * Print incoming pointers / or \ to each non-null child node. * @param level the current level * @param offset the current offset * @param levelNodes the current level of nodes */ private void printIncomingPointers(int level, int offset, BinaryNode levelNodes[]) { printSpaces(offset); int k = POWERS_OF_2[level]; for (int i = 0; i < k; i++) { BinaryNode node = levelNodes[i]; // Left child: print / if ((node != null) && (node.getLeft() != null)) { System.out.print(" /"); } // No left child: print spaces else { printSpaces(3); } // Right child: print \ if ((node != null) && (node.getRight() != null)) { printSpaces(2*offset); System.out.print("\\"); } // No right child: print spaces else { printSpaces(2*offset+1); } // Space over to the next node in this level. if (i < k-1) printSpaces(2*offset); } System.out.println(); } /** * Prepare the next level of nodes. * @param level the current level * @param levelNodes the current level of nodes * @return the next level of nodes. */ private BinaryNode[] nextLevel(int level, BinaryNode levelNodes[]) { BinaryNode nextLevel[] = (BinaryNode[]) new BinaryNode[POWERS_OF_2[level+1]]; for (int i = 0; i < POWERS_OF_2[level]; i++) { BinaryNode node = levelNodes[i]; // Queue the left child nodes of each non-null parent node. nextLevel[2*i] = (node != null) && (node.getLeft() != null) ? node.getLeft() : null; // Queue the right child nodes of each non-null parent node. nextLevel[2*i+1] = (node != null) && (node.getRight() != null) ? node.getRight() : null; } return nextLevel; } /** * Print spaces. * @param count the number of spaces. */ private void printSpaces(int count) { for (int i = 0; i < count; i++) System.out.print(" "); } /** * Print dashes. * @param count the number of dashes. */ private void printDashes(int count) { for (int i = 0; i < count; i++) System.out.print("-"); } }

Thanks!!