Part 4: Balanced tree The BSTSet does not keep the tree balanced, and we know th
ID: 3709553 • Letter: P
Question
Part 4: Balanced tree The BSTSet does not keep the tree balanced, and we know that an unbalanced tree can make contains/add/remove operations take O(N) in the worst case instead of O(log N). To improve your Set implementation, you will complete a second class that uses a balanced binary search tree, AVLTreeSet. Notice that this class extends BSTSet, borrowing most of the functionality. We've provided implementations of add and remove that call a balancing method to fix the balance property after an insertion or removal. Your job will be to complete the balancing functionality by implementing two methods AVLTreeSet.rotateLeft AVLTreeSet.rotateRight See the comments above these methods to see a detailed description of what each method should do. Notice that the AVLTreeSet.balance method uses rotateLeft and rotateRight in combination to do the double rotation cases, so you don't have to directly implement double rotations. Tips: as in the remove implementation, you should use the updateParent method to change what node is at the top of the subtree. It will greatly simplify your code. Note that the rotation changes the height of the tree, so make sure to call updateHeight at the end. (Do not call updateHeightWholeTree) . . All of the tests in AVLTreeSetTest.java should pass when the rotate methods work.Explanation / Answer
Note : please find avl tree class for insert ion to balance.....It might help ful.......
// Java program for insertion in AVL Tree
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
class AVLTree {
Node root;
// A utility function to get height of the tree
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
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;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
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;
}
// A utility function to print preorder traversal
// of the tree.
// The function also 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();
/* Constructing tree given in the above figure */
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);
/* The constructed AVL Tree would be
30
/
20 40
/
10 25 50
*/
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
}
}