Code1 has a class implementing TreeVisitor and, when used, calculates and set th
ID: 3824059 • Letter: C
Question
Code1 has a class implementing TreeVisitor and, when used, calculates and set the depth of each Entry in a tree. (To set the AVLEntry instance's depth use the setDepth() method). Remember that a node's depth is one greater than the depth of its parent!
You will also need Code2 which has a class implementing TreeVisitor and, when used, calculates and returns the height of an Entry in a tree. (To set the AVLEntry instance's height use the setHeight() method). Remember that leaves always have a height of 0 and interior nodes have a height one greater than their taller child.
Code2:
Explanation / Answer
package apr17;
public class AvlTree {
Node root;
// to get height of the tree
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// to right rotate subtree rooted with y
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// to left rotate subtree rooted with x
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
Node insert(Node node, int key) {
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
// Duplicate keys not allowed
return node;
/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left), height(node.right));
/*
* 3. Get the balance factor of this ancestor node to check whether this
* node became unbalanced
*/
int balance = getBalance(node);
// If this node becomes unbalanced, then there
// are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// to print preorder traversal of the tree and prints height of every node
void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AvlTree tree = new AvlTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder traversal" + " of constructed tree is : ");
tree.preOrder(tree.root);
}
}
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}