Calling the rotateWithLeftChild() and rotateWithRightChild() methods given in th
ID: 3847241 • Letter: C
Question
Calling the rotateWithLeftChild() and rotateWithRightChild() methods given in the Class Notes for 06-06-2017 write the leftRightRotate and rightLeftRotate methods using the following headings and descriptions:
protected AVL_Node<E> doubleWithLeftChild(
AVL_Node<E> k3 )
/* do a single "left rotation" passing k3's left child, then return the result of calling rotateWithLeftChild passing the parameter, remembering that the rotateWithRightChild does a "left rotation" and vice versa */
protected AVL_Node<E> doubleWithRightChild(
AVL_Node<E> k3 )
/* do a single "right rotation" passing k3's right child, then return the result of calling rotateWithRightChild passing the parameter, remembering that the rotateWithLeftChild does a "right rotation" and vice versa*/
// THIS IS WHAT I CALLED Right Rotation at k2
protected AVL_Node<E> rotateWithLeftChild(
AVL_Node<E> k2 )
{
AVL_Node<E> k1 = k2.getLeftChild();
k2.setLeftChild(k1.getRightChild());
k1.setRightChild(k2);
k2.setHeight( Math.max( heightOf(k2.getLeftChild()), heightOf(k2.getRightChild()) ) + 1 );
k1.setHeight( Math.max( heightOf(k1.getLeftChild()), k2.getHeight() ) + 1 );
return k1;
}
// What I called Left Rotation at k2
protected AVL_Node<E> rotateWithRightChild(
AVL_Node<E> k2 )
{
AVL_Node<E> k1 = k2.getRightChild());
k2.setRightChild(k1.getLeftChild());
k1. setLeftChild(k2);
k2.setHeight( Math.max( heightOf(k2.getLeftChild()), heightOf(k2.getRightChild()) ) + 1 );
k1.setHeight( Math.max( heightOf(k1.getRightChild()), k2.getHeight() ) + 1 );
return k1;
}
Explanation / Answer
import java.util.Scanner;
/* Class AVL_Node */
class AVL_Node
{
AVL_Node left, right;
int data;
int height;
/* Constructor */
public AVL_Node()
{
left = null;
right = null;
data = 0;
height = 0;
}
/* Constructor */
public AVL_Node(int n)
{
left = null;
right = null;
data = n;
height = 0;
}
}
/* Class AVL_Tree */
class AVL_Tree
{
private AVL_Node root;
/* Constructor */
public AVL_Tree()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Make the tree logically empty */
public void makeEmpty()
{
root = null;
}
/* Function to insert data */
public void insert(int data)
{
root = insert(data, root);
}
/* Function to get height of node */
private int height(AVL_Node t )
{
return t == null ? -1 : t.height;
}
/* Function to max of left/right node */
private int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}
/* Function to insert data recursively */
private AVL_Node insert(int x, AVL_Node t)
{
if (t == null)
t = new AVL_Node(x);
else if (x < t.data)
{
t.left = insert( x, t.left );
if( height( t.left ) - height( t.right ) == 2 )
if( x < t.left.data )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( x > t.data )
{
t.right = insert( x, t.right );
if( height( t.right ) - height( t.left ) == 2 )
if( x > t.right.data)
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}
/* Rotate binary tree node with left child */
private AVL_Node rotateWithLeftChild(AVL_Node k2)
{
AVL_Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = max( height( k1.left ), k2.height ) + 1;
return k1;
}
/* Rotate binary tree node with right child */
private AVL_Node rotateWithRightChild(AVL_Node k1)
{
AVL_Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = max( height( k2.right ), k1.height ) + 1;
return k2;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child */
private AVL_Node doubleWithLeftChild(AVL_Node k3)
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child */
private AVL_Node doubleWithRightChild(AVL_Node k1)
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}
/* Functions to count number of nodes */
public int countNodes()
{
return countNodes(root);
}
private int countNodes(AVL_Node r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
/* Functions to search for an element */
public boolean search(int val)
{
return search(root, val);
}
private boolean search(AVL_Node r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.data;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(AVL_Node r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data +" ");
inorder(r.right);
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(AVL_Node r)
{
if (r != null)
{
System.out.print(r.data +" ");
preorder(r.left);
preorder(r.right);
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(AVL_Node r)
{
if (r != null)
{
postorder(r.left);
postorder(r.right);
System.out.print(r.data +" ");
}
}
}
/* Class AVL Tree Test */
public class AVL_TreeTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of AVLTree */
AVL_Tree avlt = new AVL_Tree();
System.out.println("AVLTree Tree Test ");
char ch;
/* Perform tree operations */
do
{
System.out.println(" AVLTree Operations ");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
System.out.println("5. clear tree");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
avlt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ avlt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ avlt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ avlt.isEmpty());
break;
case 5 :
System.out.println(" Tree Cleared");
avlt.makeEmpty();
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
avlt.postorder();
System.out.print(" Pre order : ");
avlt.preorder();
System.out.print(" In order : ");
avlt.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
import java.util.Scanner;
/* Class AVLNode */
class AVL_Node
{
AVL_Node left, right;
int data;
int height;
/* Constructor */
public AVL_Node()
{
left = null;
right = null;
data = 0;
height = 0;
}
/* Constructor */
public AVL_Node(int n)
{
left = null;
right = null;
data = n;
height = 0;
}
}
/* Class AVL_Tree */
class AVL_Tree
{
private AVL_Node root;
/* Constructor */
public AVL_Tree()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Make the tree logically empty */
public void makeEmpty()
{
root = null;
}
/* Function to insert data */
public void insert(int data)
{
root = insert(data, root);
}
/* Function to get height of node */
private int height(AVL_Node t )
{
return t == null ? -1 : t.height;
}
/* Function to max of left/right node */
private int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}
/* Function to insert data recursively */
private AVL_Node insert(int x, AVL_Node t)
{
if (t == null)
t = new AVL_Node(x);
else if (x < t.data)
{
t.left = insert( x, t.left );
if( height( t.left ) - height( t.right ) == 2 )
if( x < t.left.data )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( x > t.data )
{
t.right = insert( x, t.right );
if( height( t.right ) - height( t.left ) == 2 )
if( x > t.right.data)
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}
/* Rotate binary tree node with left child */
private AVL_Node rotateWithLeftChild(AVL_Node k2)
{
AVL_Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = max( height( k1.left ), k2.height ) + 1;
return k1;
}
/* Rotate binary tree node with right child */
private AVL_Node rotateWithRightChild(AVL_Node k1)
{
AVL_Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = max( height( k2.right ), k1.height ) + 1;
return k2;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child */
private AVL_Node doubleWithLeftChild(AVL_Node k3)
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child */
private AVLN_ode doubleWithRightChild(AVL_Node k1)
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}
/* Functions to count number of nodes */
public int countNodes()
{
return countNodes(root);
}
private int countNodes(AVLNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
/* Functions to search for an element */
public boolean search(int val)
{
return search(root, val);
}
private boolean search(AVL_Node r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.data;
if (val < rval)
r = r.left;
else if (val > rval)
r = r.right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(AVLNode r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data +" ");
inorder(r.right);
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(AVLNode r)
{
if (r != null)
{
System.out.print(r.data +" ");
preorder(r.left);
preorder(r.right);
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(AVLNode r)
{
if (r != null)
{
postorder(r.left);
postorder(r.right);
System.out.print(r.data +" ");
}
}
}
/* Class AVL Tree Test */
public class AVL_TreeTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of AVLTree */
AVL_Tree avlt = new AVL_Tree();
System.out.println("AVLTree Tree Test ");
char ch;
/* Perform tree operations */
do
{
System.out.println(" AVLTree Operations ");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. count nodes");
System.out.println("4. check empty");
System.out.println("5. clear tree");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
avlt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ avlt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Nodes = "+ avlt.countNodes());
break;
case 4 :
System.out.println("Empty status = "+ avlt.isEmpty());
break;
case 5 :
System.out.println(" Tree Cleared");
avlt.makeEmpty();
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
avlt.postorder();
System.out.print(" Pre order : ");
avlt.preorder();
System.out.print(" In order : ");
avlt.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.