import java.util.ArrayList; enum TREETYPE {BST, AVL, SPLAY}; public class WirelessPower…
- User
import java.util.ArrayList;
enum TREETYPE {BST, AVL, SPLAY};
public class WirelessPower { public int DEFAULT_HEIGHT = 0; public int DEFAULT_ID = 0; public int MINID = 10000; public int MAXID = 99999; public int MINLAT = -90; public int MAXLAT = 90; public int MINLONG = -180; public int MAXLONG = 180;
/**
- The constructor performs the required initializations. It creates an empty object. It also
- specifies the type of the tree. The tree can be a regular BST which does not perform any
- re-structuring. It can be an AVL tree which re-balances the tree after every insertion or removal.
- The third type is a Splay tree which splays the accessed node to the tree root.
- @param type one of the enumerators ot TREETYPE */ public WirelessPower(TREETYPE type) { this.m_type = type; // Initalize m_type to type of tree m_root = null; // Initalzing root of the tree to null }
/**
-
@return the enumerated type of TREETYPE */ TREETYPE getType() {
return m_type; // returning the type of tree. }
/**
- Copy constructor for WirelessPower */ public WirelessPower(WirelessPower rhs) { //Copying the type of tree m_type = rhs.m_type; //Deep copy of the tree. m_root = copyOfTree(rhs.m_root); }
/**
- This function inserts a Customer object into the tree in the proper position.
- The Customer::m_id should be used as the key to traverse the WirelessPower tree
- and abide by BST traversal rules. The comparison operators (>, <, ==, !=) work with
- the int type in C++. A Customer id is a unique number in the range MINID - MAXID.
- We do not allow a duplicate id or an object with invalid id in the tree.
- Note:
- • In the WirelessPower tree data structure every node is a Customer object which is
-
represented as a pointer to the Customer object. Therefore, for every insertion we -
need to allocate memory and use the information of customer to initialize the new node. -
Memory allocation takes place in the WirelessPower class. - • If the tree type is BST, after an insertion, we should update the height for all nodes
-
in the insertion path. - • If the tree type is AVL, after an insertion, we should update the height of each node in
-
the insertion path as well as check for an imbalance at each node in this path. - • If the tree type is SPLAY, after and insertion, we need to splay the inserted node
-
and bring it to the root of the tree while the tree preserves the BST property as well as updating the node heights.
*/ // aCustomer here is the ID.. public void insert(Customer aCustomer) {
//ArrayList to keep Track of nodes. ArrayList tempNodes = new ArrayList<>();
// Check for valid range of ID if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) { return; } // Check if tree is empty if (isEmpty()) { // Create a new customer node and set it as the root since tree is empty m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); return; } // To determine which type of insertion to use / rebalance as well switch (getType()) { case BST: m_root = insertBST(m_root, aCustomer,tempNodes); balance(tempNodes); break; case AVL: m_root = insertAVL(m_root, aCustomer,tempNodes); balance(tempNodes); break; case SPLAY: // m_root = insertBST(m_root, aCustomer); m_root = splay(m_root, aCustomer); break; }}
/**
- The clear function makes it an empty tree. */ public void clear() { m_root = null; }
/**
-
The remove function traverses the tree to find a node with the id and removes
-
it from the tree. In the case of BST or AVL tree the remove function should also update
-
the heights for all nodes in the removal path. If the tree type is SPLAY, the remove
-
function does not remove the node. */ public void remove(int id) { ArrayList tempNodes = new ArrayList<>();
switch (getType()) { case BST: m_root = deleteRecursively(m_root, id,tempNodes);
break; case AVL: m_root = deleteRecursively(m_root, id,tempNodes); break; case SPLAY: //Do nothing if SPLAY tree break;} }
/**
- This function sets the type of an existing WirelessPower object. Once the type is changed,
- the function should re-structure the tree according to the following rules:
- • If the type is changed from BST or SPLAY to AVL, the function should reconstruct the
-
tree as an AVL tree. In the case of reconstruction the nodes are transferred from the -
old tree to the new tree. There should not be any reallocation of memory. - • If the type is changed from AVL to BST or Splay, there is no need for reconstruction.
-
After change the tree operations will perform according to the new type. - • Any change between BST and SPLAY types will not trigger a reconstruction. After
-
change the tree operations will perform according to the new type.
*/ public void setType(TREETYPE type) { //If the new type is the same as current just return //Nothing to do. if(m_type == type) { return; }
switch(m_type) { //AVL doesn't need to be reconstructed to BST or SPLAY case AVL: //Just update the variable to tree type instead. if (type == TREETYPE.BST || type == TREETYPE.SPLAY) { m_type =type; // Update the type } break; case BST: if(type == TREETYPE.AVL){ BstToAVL(); m_type = type; } else { m_type = type; } break; case SPLAY: if(type == TREETYPE.AVL) { BstToAVL(); m_type = type; } break; default: break; }}
/**
- creates an exact deep copy of the rhs. */ public Customer copy(WirelessPower rhs) { //Create a new customer root to hold for the copy of tree //But first check if it's empty. if(rhs.m_root == null) { return null; } //Copying the nodes recursively. Customer nRoot = copyOfTree(rhs.m_root); return nRoot; }
public String dumpTree() { String result = ""; result = dump(m_root, result); return result; }
public String dump(Customer aCustomer, String result) { if (aCustomer == null) { return result; } //System.out.print("Customer: "+aCustomer.getID()+" result: "+result); result += "("; result = dump(aCustomer.m_left, result);// first visit the left child result += aCustomer.m_id + ":" + aCustomer.m_height;// second visit the node itself result = dump(aCustomer.m_right, result);// third visit the right child result += ")"; return result; }
// *********************************************************************************************** // Used for testing - provided for you // *********************************************************************************************** public Customer getRoot() { return m_root; }
public String listCustomers() { String result = ""; result = list(m_root, result); return result.trim(); }
private String list(Customer aCustomer, String result) { if (aCustomer == null) { return result; } //System.out.println("Customer: " + aCustomer.getID() + " result: " + result); result = list(aCustomer.m_left, result);// first visit the left child // second visit the node itself result += aCustomer.m_id + ":" + aCustomer.getLatitude() + ":" + aCustomer.getLongitude() + "\n"; result = list(aCustomer.m_right, result);// third visit the right child return result; }
private Customer m_root; //the root of the BST private TREETYPE m_type; // the type of tree, BST, AVL or SPLAY
// *************************************************** // Any private helper functions must be delared here! // ***************************************************
//Function to check if tree is empty. private boolean isEmpty() { return m_root == null; }
//Helper function to recursively copy a tree structure private Customer copyOfTree(Customer node){ //Base case if(node == null) { return null; } //Creating a new customer with the same properties.. Customer newCustomer = new Customer(node.getID(),node.getLatitude(),node.getLongitude());
//Recursively copy the left and right child newCustomer.setLeft(copyOfTree(node.getLeft())); newCustomer.setRight(copyOfTree(node.getRight())); //Also copying the height newCustomer.setHeight((node.getHeight())); return newCustomer;}
//Calculate balance factor. private int getBalance(Customer node) { // Base case if (node == null) { return 0; }
int leftHeight = getHeight(node.getLeft()); int rightHeight = getHeight(node.getRight()); return leftHeight - rightHeight;}
//AVL Balance private Customer balance(ArrayList node) { // Traverse from bottom (the most recently inserted node) to the root for (int i = node.size() - 1; i >= 0; i--) { Customer currNode = node.get(i); // Update the height of the current node updateHeight(currNode);
// Balance the current node and set it to its parent Customer balancedNode = performRotation(currNode); // Update the current node's reference in the parent if (i > 0) { Customer parentNode = node.get(i - 1); if (parentNode.getLeft() == currNode) { parentNode.setLeft(balancedNode); } else { parentNode.setRight(balancedNode); } } else { return balancedNode; // Return the new root if we're at the top } } return node.get(0); // Return the root node at the end}
private Customer performRotation(Customer node) { // Left Left Case if (getBalance(node) > 1 && getBalance(node.getLeft()) >= 0) { return rightRotate(node); } // Left Right Case if (getBalance(node) > 1 && getBalance(node.getLeft()) < 0) { node.setLeft(leftRotate(node.getLeft())); return rightRotate(node); } // Right Right Case if (getBalance(node) < -1 && getBalance(node.getRight()) <= 0) { return leftRotate(node); } // Right Left Case if (getBalance(node) < -1 && getBalance(node.getRight()) > 0) { node.setRight(rightRotate(node.getRight())); return leftRotate(node); } return node; // Return node if no rotations were needed }
//Perform right rotation for AVL tree. private Customer rightRotate (Customer y) { //Making x the new root of the subtree. Customer x = y.getLeft(); //Storing the right child of x. Customer temp = x.getRight();
//Rotate to -> //y becomes the right child of x x.setRight(y); //temp(the right child of x) becomes the left child //Of y y.setLeft(temp); //Now we update the heights. updateHeight(y); updateHeight(x); //New root return x;}
//Perform left rotation for AVL tree. private Customer leftRotate(Customer y) { //Making x the new root of the subtree. Customer x = y.getRight(); //Storing the left child of x Customer temp = x.getLeft();
//Rotate to <- //y become the left child of x. x.setLeft(y); //temp(the left child of x) becomes the right child //Of Y y.setRight(temp); //Update height updateHeight(y); updateHeight(x); return x;}
//Rotate function for splay to the left. private Customer leftRotateSplay(Customer x) {
// No rotation possible for these two cases if(x == null) { return x; } if(x.getRight() == null) { return x; } //Y is the new root after totation Customer y = x.getRight(); //Move the left child of y to be the right child of x x.setRight(y.getLeft()); //Rotatiing here y.setLeft(x); updateHeight(x); updateHeight(y); return y;}
//Rotate function for splay to the right private Customer rightRotateSplay (Customer x ) {
// No rotation possible for these two cases if(x == null) { return x; } if(x.getLeft() == null) { return x; } //Y is the new root after rotation Customer y = x.getLeft(); //Move the right child of y to be the left child of x x.setLeft(y.getRight()); //Rotating here y.setRight(x); updateHeight(x); updateHeight(y); return y;}
//Updates the height of tree. private void updateHeight(Customer node) { if (node != null) { // Calculate the height of left and right children int leftHeight = getHeight(node.getLeft()); int rightHeight = getHeight(node.getRight());
// Update the height of the current node node.setHeight(1 + Math.max(leftHeight, rightHeight));} }
// Get the height of a node private int getHeight(Customer node) { if (node == null) { return -1; // } else { return node.getHeight(); } }
//Deletes nodes from a tree recursively. private Customer deleteRecursively(Customer node, int id, ArrayList pathNodes) { if (node == null) { return null; // Node not found, return null }
// Add the current node to the path pathNodes.add(node); if (id < node.getID()) { node.setLeft(deleteRecursively(node.getLeft(), id, pathNodes)); } else if (id > node.getID()) { node.setRight(deleteRecursively(node.getRight(), id, pathNodes)); } else { // Node to be deleted found if (node.getLeft() == null) { return node.getRight(); // No left child, replace with right child } else if (node.getRight() == null) { return node.getLeft(); // No right child, replace with left child } // Node with two children: Get the inorder successor Customer temp = minValueNode(node.getRight()); // Copy the inorder successor's data to this node node.setID(temp.getID()); node.setLatitude(temp.getLatitude()); node.setLongitude(temp.getLongitude()); // Delete the inorder successor node.setRight(deleteRecursively(node.getRight(), temp.getID(), pathNodes)); } // After deletion, update the height and rebalance updateHeight(node); return balance(pathNodes); // Rebalance after deletion}
private Customer minValueNode(Customer node) { Customer current = node; while (current.getLeft() != null) { current = current.getLeft(); } return current; }
//Help find the mininum private Customer findMin(Customer node) { //Go to the left most child in tree (Min) while(node.getLeft() != null & node.getLeft() != null) { node = node.getLeft(); } return node; }
public void BstToAVL() { // Creating an ArrayList to hold the nodes in sorted order ArrayList nodeList = new ArrayList<>();
// Filling the ArrayList with nodes in sorted order traverseInOrder(m_root, nodeList); // Converting the ArrayList to an AVL tree m_root = arrayToAVL(nodeList, 0, nodeList.size() - 1);}
// Recursively build the AVL tree subtrees private Customer arrayToAVL(ArrayList nodeList, int start, int end) { // No elements left in our tree if (start > end) { return null; } // Find the middle of the ArrayList. int mid = (start + end) / 2; // Create a root node Customer node = nodeList.get(mid);
// Create the left subtree node.setLeft(arrayToAVL(nodeList, start, mid - 1)); // Create the right subtree node.setRight(arrayToAVL(nodeList, mid + 1, end)); return node;}
// Traverse tree in order (Left subtree then root, then right subtree) // While storing the values into our ArrayList. private void traverseInOrder(Customer node, ArrayList nodeList) { // If node is null, no nodes left if (node == null) { return; } // Traverse left of subtree first traverseInOrder(node.getLeft(), nodeList); // Add the current node to our ArrayList nodeList.add(node); // Traverse right of subtree afterwards traverseInOrder(node.getRight(), nodeList); }
//Helper function to insert a BST Tree. private Customer insertBST(Customer node, Customer aCustomer, ArrayList tempNodes) { //Base case if (node == null) { return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); }
//If key already in the tree return the node. //No Duplicates. if(node.getID() == aCustomer.getID()) { return node; } //Adding current node to the list tempNodes.add(node); //Down the tree.. if(aCustomer.getID() < node.getID()) { node.setLeft(insertBST(node.getLeft(), aCustomer, tempNodes)); } else { node.setRight(insertBST(node.getRight(), aCustomer, tempNodes)); } //Update the height of the ancestor node updateHeight(node); return node;}
//AVL Insertion private Customer insertAVL(Customer node, Customer aCustomer, ArrayList tempNodes) { // If the tree is empty, create a new node and return it if (node == null) { return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); }
// If the key already exists, return the node (no duplicates) if (node.getID() == aCustomer.getID()) { return node; // Early return to prevent infinite recursion on duplicates } // Add the current node to the list tempNodes.add(node); // Traverse the tree and insert the new customer if (aCustomer.getID() < node.getID()) { System.out.println("Going left: " + node.getID()); node.setLeft(insertAVL(node.getLeft(), aCustomer, tempNodes)); } else { System.out.println("Going right: " + node.getID()); node.setRight(insertAVL(node.getRight(), aCustomer, tempNodes)); } // Update the height of the ancestor node updateHeight(node); // Balance the node and return the potentially new root of this subtree return balance(tempNodes);}
private Customer splay(Customer node, Customer aCustomer) { // Base case: if node is null or key is found if (node == null || node.getID() == aCustomer.getID()) { return node; }
// Our ID is in the left subtree if (aCustomer.getID() < node.getID()) { // If left child is null return node (key not found) if (node.getLeft() == null) { return node; } // Zig-Zig (Left Left) if (aCustomer.getID() < node.getLeft().getID()) { // splay the left left grandchild node.getLeft().setLeft(splay(node.getLeft().getLeft(), aCustomer)); // perform first right rotation node = rightRotateSplay(node); } // Zig-Zag (Left Right) else if (aCustomer.getID() > node.getLeft().getID()) { // splay the left right grandchild node.getLeft().setRight(splay(node.getLeft().getRight(), aCustomer)); // perform left rotation on left child if (node.getLeft().getRight() != null) { node.setLeft(leftRotateSplay(node.getLeft())); } } //second right rotation if needed if (node.getLeft() == null) { // return the current node if the left child is null return node; } else { return rightRotateSplay(node); } } else { // Our id in the right subtree // If right child is null return node (key not found) if (node.getRight() == null) { return node; } // Zag-Zag (Right Right) if (aCustomer.getID() > node.getRight().getID()) { //splay the right-right grandchild node.getRight().setRight(splay(node.getRight().getRight(), aCustomer)); //first left rotation node = leftRotateSplay(node); } // Zag-Zig (Right Left) else if (aCustomer.getID() < node.getRight().getID()) { // splay the right-left grandchild node.getRight().setLeft(splay(node.getRight().getLeft(), aCustomer)); //right rotation on right child if (node.getRight().getLeft() != null) { node.setRight(rightRotateSplay(node.getRight())); } } if (node.getRight() == null) { return node; } else { return leftRotateSplay(node); } }}
class Customer { int DEFAULT_HEIGHT = 0; int DEFAULT_ID = 0;
Customer(int id, double lat, double longitude){ m_id = id; m_latitude = lat; m_longitude = longitude; m_left = null; m_right = null; m_height = DEFAULT_HEIGHT; } //used for testing that ids are put in trees correctly Customer(int id){ m_id = id; m_latitude = 0; m_longitude = 0; m_left = null; m_right = null; m_height = DEFAULT_HEIGHT; } int getHeight() {return m_height;} Customer getLeft() {return m_left;} Customer getRight() {return m_right;} int getID() {return m_id;} double getLatitude() {return m_latitude;} double getLongitude() {return m_longitude;} void setID(int id){m_id=id;} void setLatitude(double lat) {m_latitude=lat;} void setLongitude(double longitude) {m_longitude=longitude;} void setHeight(int height){m_height=height;} void setLeft(Customer left){m_left=left;} void setRight(Customer right){m_right=right;} String getLatStr() { String text = ""; int latSeconds = (int)(Math.abs(m_latitude * 3600)); int latDegrees = latSeconds / 3600; latSeconds = latSeconds % 3600; int latMinutes = latSeconds / 60; latSeconds %= 60; char latDirection = (m_latitude >= 0) ? 'N' : 'S'; text = Integer.toString(latDegrees) + "\u00B0 " + Integer.toString(latMinutes) + "' " + Integer.toString(latSeconds) + "\" " + latDirection; return text; } String getLongStr() { String text = ""; int longSeconds = (int)(Math.abs(m_longitude * 3600)); int longDegrees = longSeconds / 3600; longSeconds = longSeconds % 3600; int longMinutes = longSeconds / 60; longSeconds %= 60; char longDirection = (m_longitude >= 0) ? 'E' : 'W'; text = Integer.toString(longDegrees) + "\u00B0 " + Integer.toString(longMinutes) + "' " + Integer.toString(longSeconds) + "\" " + longDirection; return text; } //private data members private int m_id; private double m_latitude; private double m_longitude; private Customer m_left; //the pointer to the left child in the BST private Customer m_right; //the pointer to the right child in the BST private int m_height; //the height of node in the BST} // end of class Customer } //end of class WirelessPower
Im running into a problem with this code when running these test
import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.AfterEach; import org.junit.jupiter.api.BeforeEach; import org.junit.jupiter.api.Test;
class WirelessPowerTestAVL { WirelessPower s1,s2,s3; WirelessPower.Customer d0,d1,d2,d3,d4,d5,d6,d7,d8,d9;
@BeforeEach void setUp() throws Exception { s2 = new WirelessPower(TREETYPE.BST); s3 = new WirelessPower(TREETYPE.SPLAY); s1 = new WirelessPower(TREETYPE.AVL); d0 = s1.new Customer(10000); // min id d1 = s1.new Customer(53002,51.5078,-0.0878);//London Bridge (North & West) d2 = s1.new Customer(20201, 39.2554, -76.7107); //Catonsville campus (North & West) d3 = s1.new Customer(60496, 48.8584, 2.2945); //Eiffel Tower (North & East) d4 = s1.new Customer(19289,43.6150,-116.2023);//Boise, ID (North & West) d5 = s1.new Customer(27904, 55.7558, 37.6173);//Catherine Palace Moscow Russia (North & East) d6 = s1.new Customer(93209, -33.8568, 151.2153);//Sydney Opera House (South & East) d7 = s1.new Customer(19224, 40.4319,116.5704);//Great Wall of China (North & East) d8 = s1.new Customer(19372, 27.1751, 78.0421);//Taj Mahal (North & East) d9 = s1.new Customer(26241, -13.1632,-72.5453);//Machu Picchu (South & West) } @AfterEach void tearDown() throws Exception { s3 = s2 = s1 = null; } @Test void testWirelessPowerConstructor() { assertNull(s1.getRoot()); assertTrue(s2.getRoot() == null); assertFalse(s3.getRoot() != null); assertEquals(TREETYPE.AVL,s1.getType()); assertEquals(TREETYPE.BST,s2.getType()); assertEquals(TREETYPE.SPLAY,s3.getType()); } @Test void testInsertEasyAVL() { s1.insert(d1); //this Customer is the root of the tree assertEquals(53002,s1.getRoot().getID()); assertEquals(51.5078, s1.getRoot().getLatitude()); assertEquals(-0.0878, s1.getRoot().getLongitude()); //insert to the left of the root s1.insert(d2); assertEquals(20201,s1.getRoot().getLeft().getID()); assertEquals(39.2554, s1.getRoot().getLeft().getLatitude()); assertEquals(-76.7107, s1.getRoot().getLeft().getLongitude()); //insert to the right of the root s1.insert(d3); assertEquals(60496,s1.getRoot().getRight().getID()); assertEquals(48.8584, s1.getRoot().getRight().getLatitude()); assertEquals(2.2945, s1.getRoot().getRight().getLongitude()); //check the heights assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree()); } @Test void testInsertAVLNoRebalance() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root s1.insert(d7);//left of left of left of root s1.insert(d8); //right of left of left of root s1.insert(d9); //left of right of left of root assertEquals(53002,s1.getRoot().getID()); assertEquals(60496,s1.getRoot().getRight().getID()); assertEquals(20201,s1.getRoot().getLeft().getID()); assertEquals(19289,s1.getRoot().getLeft().getLeft().getID()); assertEquals(27904,s1.getRoot().getLeft().getRight().getID()); assertEquals(93209,s1.getRoot().getRight().getRight().getID()); assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID()); assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID()); assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID()); assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree()); } @Test void testInsertRebalanceEasyAVL() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d4); //left of left of root //requires a rebalance assertEquals(20201,s1.getRoot().getID()); assertEquals(53002,s1.getRoot().getRight().getID()); assertEquals(19289,s1.getRoot().getLeft().getID()); //check the heights assertEquals("((19289:0)20201:1(53002:0))",s1.dumpTree()); } @Test void testInsertDeepCopyOfParameterAVL() { s1.insert(d1); s1.insert(d2); assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878",s1.listCustomers()); d1.setID(93300); s1.insert(d1); assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n93300:51.5078:-0.0878",s1.listCustomers()); //check the heights assertEquals("((20201:0)53002:1(93300:0))",s1.dumpTree()); } @Test void testInsertRebalanceAVL() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d7);//left of left of left of root assertEquals(53002,s1.getRoot().getID()); assertEquals(60496,s1.getRoot().getRight().getID()); assertEquals(19289,s1.getRoot().getLeft().getID()); assertEquals(19224,s1.getRoot().getLeft().getLeft().getID()); assertEquals(20201,s1.getRoot().getLeft().getRight().getID()); System.out.println(s1.dumpTree()); } @Test void testInsertDuplicateAVL() { s1.insert(d1); s1.insert(d2); s1.insert(d3); assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945",s1.listCustomers()); s1.insert(s1.new Customer(60496)); //No duplicate IDs assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945",s1.listCustomers()); } @Test void testInsertErrorAVL() { WirelessPower.Customer d10 = s1.new Customer(500,48.8584,2.2945); s1.insert(d10); //ID is less than minimum assertNull(s1.getRoot()); } @Test void testClearAVL() { //create a tree s1.insert(d1); s1.insert(d2); s1.insert(d3); s1.clear(); assertNull(s1.getRoot()); } @Test void testRemoveEasyAVL() { //create a simple tree s1.insert(d1); s1.insert(d2); s1.insert(d3); //remove the node to the right of the root s1.remove(60496); //this is d3 assertNull(s1.getRoot().getRight()); //check the heights assertEquals("((20201:0)53002:1)",s1.dumpTree()); } @Test void testRemoveNoRebalanceAVL() { //create a simple tree s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root //insert d6 (goes to right of right of root) s1.insert(d6); //delete 60496 which is right of root with a right child s1.remove(60496); //93209 (d6) should now be right of root assertEquals(93209, s1.getRoot().getRight().getID()); } @Test void testRemoveRebalanceEasyAVL() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root s1.insert(d7);//left of left of left of root //delete 27904 which is right of left of root and requires a rebalance s1.remove(27904); assertEquals(53002,s1.getRoot().getID()); assertEquals(60496,s1.getRoot().getRight().getID()); assertEquals(19289,s1.getRoot().getLeft().getID()); assertEquals(19224,s1.getRoot().getLeft().getLeft().getID()); assertEquals(20201,s1.getRoot().getLeft().getRight().getID()); //check the heights assertEquals("(((19224:0)19289:1(20201:0))53002:2(60496:1(93209:0)))",s1.dumpTree()); } @Test void testHeightChangesAVL() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root assertEquals(1,s1.getRoot().getHeight()); s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root assertEquals(2,s1.getRoot().getHeight()); s1.insert(d7);//left of left of left of root s1.insert(d8); //right of left of left of root s1.insert(d9); //left of right of left of root assertEquals(3,s1.getRoot().getHeight()); //check the heights assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree()); } @Test void testRemoveNoRebalAVL() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root s1.insert(d7);//left of left of left of root s1.insert(d8); //right of left of left of root s1.insert(d9); //left of right of left of root String result = s1.listCustomers(); assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n19372:27.1751:78.0421\n20201:39.2554:-76.7107\n26241:-13.1632:-72.5453\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result); s1.remove(19372); result = s1.listCustomers(); assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n26241:-13.1632:-72.5453\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result); //check the heights assertEquals("((((19224:0)19289:1)20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree()); } @Test void testRemoveReBalEasyAVL() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root s1.insert(d7);//left of left of left of root System.out.println(s1.dumpTree()); String result = s1.listCustomers(); assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result); s1.remove(27904); result = s1.listCustomers(); assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result); assertEquals("(((19224:0)19289:1(20201:0))53002:2(60496:1(93209:0)))",s1.dumpTree()); } @Test void testCopyConstructorEasyAVL() { s1.insert(d1); s1.insert(d2); s1.insert(d3); assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree()); WirelessPower s4 = new WirelessPower(s1); // this Customer is the root of the tree assertEquals(53002, s4.getRoot().getID()); assertEquals(51.5078, s4.getRoot().getLatitude()); assertEquals(-0.0878, s4.getRoot().getLongitude()); // left of the root assertEquals(20201, s4.getRoot().getLeft().getID()); assertEquals(39.2554, s4.getRoot().getLeft().getLatitude()); assertEquals(-76.7107, s4.getRoot().getLeft().getLongitude()); // right of the root assertEquals(60496, s4.getRoot().getRight().getID()); assertEquals(48.8584, s4.getRoot().getRight().getLatitude()); assertEquals(2.2945, s4.getRoot().getRight().getLongitude()); assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree()); assertEquals("((20201:0)53002:1(60496:0))", s4.dumpTree()); } @Test void testCopyConstructorAVL() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root s1.insert(d7);//left of left of left of root s1.insert(d8); //right of left of left of root s1.insert(d9); //left of right of left of root WirelessPower s4 = new WirelessPower(s1); assertEquals(53002,s4.getRoot().getID()); assertEquals(60496,s4.getRoot().getRight().getID()); assertEquals(20201,s4.getRoot().getLeft().getID()); assertEquals(19289,s4.getRoot().getLeft().getLeft().getID()); assertEquals(27904,s4.getRoot().getLeft().getRight().getID()); assertEquals(93209,s4.getRoot().getRight().getRight().getID()); assertEquals(19224,s4.getRoot().getLeft().getLeft().getLeft().getID()); assertEquals(19372,s4.getRoot().getLeft().getLeft().getRight().getID()); assertEquals(26241,s4.getRoot().getLeft().getRight().getLeft().getID()); } @Test void testSetTypeAVLtoBST() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root s1.insert(d7);//left of left of left of root s1.insert(d8); //right of left of left of root s1.insert(d9); //left of right of left of root assertEquals(53002,s1.getRoot().getID()); assertEquals(60496,s1.getRoot().getRight().getID()); assertEquals(20201,s1.getRoot().getLeft().getID()); assertEquals(19289,s1.getRoot().getLeft().getLeft().getID()); assertEquals(27904,s1.getRoot().getLeft().getRight().getID()); assertEquals(93209,s1.getRoot().getRight().getRight().getID()); assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID()); assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID()); assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID()); assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree()); //convert AVL tree to BST tree s1.setType(TREETYPE.BST); //no change assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree()); assertEquals(TREETYPE.BST,s1.getType()); } @Test void testSetTypeAVLtoSplay() { s1.insert(d1); //root s1.insert(d2); //left of root s1.insert(d3); //right of root s1.insert(d4); //left of left of root s1.insert(d5); //right of left of root s1.insert(d6); //right of right of root s1.insert(d7);//left of left of left of root s1.insert(d8); //right of left of left of root s1.insert(d9); //left of right of left of root assertEquals(53002,s1.getRoot().getID()); assertEquals(60496,s1.getRoot().getRight().getID()); assertEquals(20201,s1.getRoot().getLeft().getID()); assertEquals(19289,s1.getRoot().getLeft().getLeft().getID()); assertEquals(27904,s1.getRoot().getLeft().getRight().getID()); assertEquals(93209,s1.getRoot().getRight().getRight().getID()); assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID()); assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID()); assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID()); assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree()); //convert AVL tree to Splay tree s1.setType(TREETYPE.SPLAY); //no change assertEquals(TREETYPE.SPLAY,s1.getType()); assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree()); }}
I'm getting stack overflow on some of them for example void testInsertAVLNoRebalance() { is one of them how would i go about fixing this i still want to use arrayList for my implementation of everything since it seems to be the most efficent no? I also cannot modify anything in the test cases or inside of the custoemr class and I cant import any other java utils
- Assistant
The stack overflow you're experiencing is likely due to the
balancemethod being called twice during AVL insertions. Here's a detailed explanation and the steps to fix the issue:Root Cause: Double Balancing
-
Current Implementation:
- In the
insertmethod, for theAVLcase, you call bothinsertAVLandbalance:case AVL: m_root = insertAVL(m_root, aCustomer, tempNodes); balance(tempNodes); break; - Inside the
insertAVLmethod, you also callbalance:private Customer insertAVL(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) { // ... insertion logic ... return balance(tempNodes); }
- In the
-
Issue:
- When
insertAVLis called, it already performs balancing on the tree. - After
insertAVLreturns, theinsertmethod callsbalanceagain on the same nodes. - This redundant call can lead to an infinite loop of balancing, especially if the tree remains unbalanced after the first balancing attempt, causing a stack overflow.
- When
Solution: Remove Redundant Balancing
To fix the stack overflow, you need to ensure that
balanceis called only once during AVL insertions. Here's how you can do it:-
Modify the
insertMethod:- Remove the
balance(tempNodes);call from theAVLcase sinceinsertAVLalready handles balancing. - Ensure that balancing is not called for the
BSTcase, as standard BSTs do not require balancing.
public void insert(Customer aCustomer) { // ArrayList to keep track of nodes along the insertion path ArrayList<Customer> tempNodes = new ArrayList<>(); // Check for valid range of ID if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) { return; } // Check if tree is empty if (isEmpty()) { // Create a new customer node and set it as the root since tree is empty m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); return; } // Determine the type of tree and perform the appropriate insertion switch (getType()) { case BST: m_root = insertBST(m_root, aCustomer, tempNodes); break; case AVL: m_root = insertAVL(m_root, aCustomer, tempNodes); break; case SPLAY: m_root = splay(m_root, aCustomer); break; } } - Remove the
-
Ensure
insertBSTDoes Not Balance:- The
insertBSTmethod should remain unchanged, as standard BSTs do not perform balancing.
private Customer insertBST(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) { // Base case: If the current node is null, insert the new customer here if (node == null) { return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); } // Check for duplicate ID if (node.getID() == aCustomer.getID()) { return node; // Do not insert duplicates } // Add the current node to the path list tempNodes.add(node); // Recur down the tree if (aCustomer.getID() < node.getID()) { node.setLeft(insertBST(node.getLeft(), aCustomer, tempNodes)); } else { node.setRight(insertBST(node.getRight(), aCustomer, tempNodes)); } // Update the height of the current node updateHeight(node); return node; } - The
-
Verify
insertAVLHandles Balancing Correctly:- Ensure that
insertAVLcorrectly inserts the node and balances the tree using the passedtempNodes.
private Customer insertAVL(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) { // If the tree is empty, create a new node and return it if (node == null) { return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); } // If the key already exists, return the node (no duplicates) if (node.getID() == aCustomer.getID()) { return node; // Early return to prevent infinite recursion on duplicates } // Add the current node to the list tempNodes.add(node); // Traverse the tree and insert the new customer if (aCustomer.getID() < node.getID()) { node.setLeft(insertAVL(node.getLeft(), aCustomer, tempNodes)); } else { node.setRight(insertAVL(node.getRight(), aCustomer, tempNodes)); } // Update the height of the ancestor node updateHeight(node); // Balance the node and return the potentially new root of this subtree return balance(tempNodes); } - Ensure that
Additional Recommendations:
-
Ensure Proper Balancing Logic:
- Double-check your
balancemethod to ensure it correctly identifies imbalances and performs the necessary rotations without introducing cycles or infinite loops.
- Double-check your
-
Test Incrementally:
- After making the changes, run your tests incrementally to ensure that each part works as expected before moving on to more complex insertions.
-
Debugging:
- If you continue to encounter issues, consider adding debug statements inside your
insertAVLandbalancemethods to trace the execution flow and identify where the recursion may be going wrong.
- If you continue to encounter issues, consider adding debug statements inside your
Conclusion
By ensuring that the
balancemethod is called only once during AVL insertions, you should prevent the stack overflow caused by infinite recursion. This change respects the distinction betweenBSTandAVLinsertion behaviors and aligns the implementation with your test cases.Updated
insertMethod:public void insert(Customer aCustomer) { // ArrayList to keep track of nodes along the insertion path ArrayList<Customer> tempNodes = new ArrayList<>(); // Check for valid range of ID if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) { return; } // Check if tree is empty if (isEmpty()) { // Create a new customer node and set it as the root since tree is empty m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude()); return; } // Determine the type of tree and perform the appropriate insertion switch (getType()) { case BST: m_root = insertBST(m_root, aCustomer, tempNodes); break; case AVL: m_root = insertAVL(m_root, aCustomer, tempNodes); break; case SPLAY: m_root = splay(m_root, aCustomer); break; } }By removing the redundant
balance(tempNodes);call in theAVLcase, the tree should now handle insertions correctly without causing a stack overflow. -