Preliminaries Complete Homework 4, and download the driver As usual, do not modi
ID: 665054 • Letter: P
Question
Preliminaries
Complete Homework 4, and download the driver
As usual, do not modify the driver.
Description
From Homework 4, you should have a binary tree class that can perform tree rotations at a given node. For this assignment, we will expand the class to automatically balance itself upon insertion.
Objective
Modify the AvlTree class from Homework 4 to self-balance on inserting an element. This means your AvlNode class needs some way of keeping track of its 'balance factor'. The balance factor of an AVL tree node is defined to be:
balanceFactor = heightleft subtree + heightright subtree
The cases for rebalancing an AVL tree are given in the following diagram (taken from Wikipedia)
Hints
A good strategy in balancing the tree upon insertion is to first insert the node as usual. Then, work your way back up the tree, performing rotations if Math.abs(balanceFactor) >= 2
A convenient way to measure the balance factor is have every node store the longest path to a leaf. One way to calculate this is given in the following pseudocode:
In addition, it may be convenient to also update the balance factors within the rotate methods themselves. For example, here is the pseudocode in updating the balance factor after a left rotation:
The documentation for my AvlTree is available here. In particular, you should pay attention to the methods lookup, rotateLeft, rotateRight, and avlRotate
Homework 4(already done):
class AvlTree{
private AvlNode root;
private int size;
public AvlTree(){
root=null;
}
public int getSize(){
return size;
}
public void insert(int elem){
root = insert(root, elem);
}
public int lookup(int elem){
return lookup(root, elem);
}
public rotateLeft(Node n2){
Node n1 = n2.left;
n2.left = n1.right;
n1.right = n2;
return n1;
}
public rotateLeft(Node n1){
Node n2 = n1.right;
n1.right = n2.left;
n2.left = n1;
return n2;
}
private class AvlNode{
Node left;
Node right;
Node parent;
int val;
AlvNode(){
val=0;
parent=null;
}
}
Driver:
}
Example Dialog