Insert Into an AVL Tree and Rebalance

Finish a self-balancing AVL tree: complete rotateRight, rotateLeft and the rebalancing step at the end of insert, so the tree is balanced again after every insert.

Reminder: how an AVL tree stays balanced. Every node stores its height (a leaf is 1, an empty child is 0), and its balance factor, height(left) - height(right), must stay between -1 and 1. An insert can push a node on the path to 2 or -2. Right after insert updates that node's height, the balance factor and the side of the tall child where the new value landed tell you which of four cases you are in:

balance  the new value went       fix
  +2     left of node.left  (LL)  rotate node right
  -2     right of node.right (RR) rotate node left
  +2     right of node.left (LR)  rotate node.left left, then node right
  -2     left of node.right (RL)  rotate node.right right, then node left

A rotation lifts a child into its parent's place. rotateRight lifts y's left child x, hands x's right subtree to y as its new left, and makes y the right child of x; rotateLeft is the mirror image. After relinking, update the lower node's height first, then the new top's. Done right, inserting 1 to 7 in order builds a perfect tree of height 3 instead of a chain of height 7.

Requirements: 1. rotateRight(Node y) and rotateLeft(Node x) return the new top of the subtree and update both heights with updateHeight(Node), lower node first. 2. In insert, after updateHeight(node), read balanceFactor(node) and handle the four cases above. Compare value with node.left.value or node.right.value to tell a straight case from a zig-zag case. 3. In a zig-zag case, store the result of the first rotation back in node.left or node.right before rotating node itself. 4. Return the new top from every case, or node when no rotation is needed. Duplicate values are still ignored.

The provided preOrder() lists every node in pre-order as its value followed by its height, for example 30(h2).

The Node class is provided - do not rename it and do not add public to it, because a Java source file may contain only one public class.

Do NOT write a main method.