On AVLTree.java, implement: ? rotateLeft ? rotateLeftRight ? getHeightDifference

Question

On AVLTree.java, implement:

? rotateLeft
? rotateLeftRight
? getHeightDifference
? Should return the difference in height between the subtrees of the incoming node.
A positive # if the left subtree is taller, negative # otherwise.

Explanation / Answer

import java.io.*; import java.util.*; public class AVLTree { public class Node { private Node left, right, parent; private int height = 1; private int value; private Node (int val) { this.value = val; } } private int height (Node N) { if (N == null) return 0; return N.height; } private Node insert(Node node, int value) { /* 1. Perform the normal BST rotation */ if (node == null) { return(new Node(value)); } if (value 1 && value node.right.value) return leftRotate(node); // Left Right Case if (balance > 1 && value > node.left.value) { node.left = leftRotate(node.left); return rightRotate(node); } // Right Left Case if (balance < -1 && value root.value ) root.right = deleteNode(root.right, value); // if value is same as root's value, then This is the node // to be deleted else { // node with only one child or no child if( (root.left == null) || (root.right == null) ) { Node temp; if (root.left != null) temp = root.left; else temp = root.right; // No child case if(temp == null) { temp = root; root = null; } else // One child case root = temp; // Copy the contents of the non-empty child temp = null; } else { // node with two children: Get the inorder successor (smallest // in the right subtree) Node temp = minValueNode(root.right); // Copy the inorder successor's data to this node root.value = temp.value; // Delete the inorder successor root.right = deleteNode(root.right, temp.value); } } // If the tree had only one node then return if (root == null) return root; // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE root.height = Math.max(height(root.left), height(root.right)) + 1; // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether // this node became unbalanced) int balance = getBalance(root); // If this node becomes unbalanced, then there are 4 cases // Left Left Case if (balance > 1 && getBalance(root.left) >= 0) return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root.left) < 0) { root.left = leftRotate(root.left); return rightRotate(root); } // Right Right Case if (balance < -1 && getBalance(root.right) 0) { root.right = rightRotate(root.right); return leftRotate(root); } return root; } public void print(Node root) { if(root == null) { System.out.println("(XXXXXX)"); return; } int height = root.height, width = (int)Math.pow(2, height-1); // Preparing variables for loop. List current = new ArrayList(1), next = new ArrayList(2); current.add(root); final int maxHalfLength = 4; int elements = 1; StringBuilder sb = new StringBuilder(maxHalfLength*width); for(int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.