/** *Performs single rotation with the left child *@param k2 the root node to be

Question

/**
*Performs single rotation with the left child
*@param k2 the root node to be rotated.
*@return the new root after rotation
*/
abstract protected TreeNode<T> rotateWithLeftChild(TreeNode<T> k2);


/**
* Performs single rotation with the right child
* @param k1 the root node to be rotated.
* @return the new root after rotation
*/
abstract protected TreeNode<T> rotateWithRightChild(TreeNode<T> k1);

/**
* Performs double rotation with the left child and its child.
* @param k3 the root node to be rotated
* @return the new root after rotation
*/
abstract protected TreeNode<T> rotateDoubleWithLeftChild(TreeNode<T> k3);



/**
* Performs double rotation with the left child and its child.
* @param k1 the root node to be rotated
* @return the new root after rotation
*/
abstract protected TreeNode<T> rotateDoubleWithRightChild(TreeNode<T> k1);



/**
* Inserts a new value into the tree, under a specified node.
* Hint: use the rotation methods.
* @param node the root node to insert the value under.
* @param value the value to be inserted.
* @return the new root node after insertion is completed.
*/
abstract protected TreeNode<T> insert(TreeNode<T> node, T value);



/**
* Computes the height of a node in the tree.
* Leaf-nodes have height = 1. *
* @param node specified node.
* @return the height of the node.
*/
abstract protected int height(TreeNode<T> node);




2.3 Evaluate your code...

You need to implement an executable class to test AVL tree.
public class TestAVLTree {
public static void main(String[] args) { ... } }

Just like before, it accepts an integer N as an argument.
It needs to generate N random numbers in the range of [0, 99], and store the random numbers in an array.
It inserts all the random numbers into an AVLTree object.
It records the time it takes to insert the N integers into the tree.
If N< 20, your program displays the tree.

Explanation / Answer

Dear.... /** *Performs single rotation with the left child *@param k2 the root node to be rotated. *@return the new root after rotation */ abstract protected TreeNode rotateWithLeftChild(TreeNode k2 ) { TreeNode k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1; k1.height = Math.max( height( k1.left ), k2.height ) + 1; return k1; } /** * Performs single rotation with the right child * @param k1 the root node to be rotated. * @return the new root after rotation */ abstract protected TreeNode rotateWithRightChild(TreeNode k1 ) { AVLNode k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1; k2.height = Math.max( height( k2.right ), k1.height ) + 1; return k2; } /** * Performs double rotation with the left child and its child. * @param k3 the root node to be rotated * @return the new root after rotation */ abstract protected TreeNode doubleWithLeftChild(TreeNode k3 ) { k3.left = rotateWithRightChild( k3.left ); return rotateWithLeftChild( k3 ); } /** * Performs double rotation with the left child and its child. * @param k1 the root node to be rotated * @return the new root after rotation */ abstract protected TreeNode doubleWithRightChild( TreeNode k1 ) { k1.right = rotateWithLeftChild( k1.right ); return rotateWithRightChild( k1 ); } /** * Inserts a new value into the tree, under a specified node. * Hint: use the rotation methods. * @param node the root node to insert the value under. * @param value the value to be inserted. * @return the new root node after insertion is completed. */ public static void main(String[] args) throws Exception { Tree avl = new Tree(); FileReader fFile = null; BufferedReader bFile = null; try { fFile = new FileReader("avldata.in"); bFile = new BufferedReader(fFile); } catch(Exception ex) { System.out.println(" File not found"); System.exit(0); } String string = new String(""); /** * Caling insert/remove function for each number read from specified file **/ while((string = bFile.readLine()) != null) { /** * Converting string to integer **/ int num=Integer.parseInt(string); if(num>=0) { /** * Insert a nuk in to AVL Tree **/ System.out.println(" Insert "+num); avl.insert(num); } else { /** * -ve number found, remove the absolute value of num **/ System.out.println(" Remove "+Math.abs(num)); avl.remove(Math.abs(num)); } } System.out.println(" Inorder traversal: "); avl.inorder(root); System.out.println(" Preorder traversal: "); avl.preorder(root); System.out.println(" Postorder traversal: "); avl.postorder(root); } }

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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