# Untitled

unknown
java
7 months ago
3.3 kB
0
Indexable
Never
```package LAB8;

public class AVLTree {

Node rootNode;

// Returns the height of the given treeNode
int getHeight(Node treeNode) {
if (treeNode == null)
return 0;
return treeNode.height;
}

// Returns the maximum of two integer values, firstValue and secondValue
int getMax(int firstValue, int secondValue) {
return (firstValue > secondValue) ? firstValue : secondValue;
}

// Performs a right rotation on the subtree rooted at the parent node
// and returns the new root of the subtree
Node rotateRight(Node parent) {
Node child = parent.left;
Node subtree = child.right;

child.right = parent;
parent.left = subtree;

parent.height = getMax(getHeight(parent.left), getHeight(parent.right)) + 1;
child.height = getMax(getHeight(child.left), getHeight(child.right)) + 1;

return child;
}

// Performs a left rotation on the subtree rooted at the parent node
// and returns the new root of the subtree
Node rotateLeft(Node parent) {
Node child = parent.right;
Node subtree = child.left;

child.left = parent;
parent.right = subtree;

parent.height = getMax(getHeight(parent.left), getHeight(parent.right)) + 1;
child.height = getMax(getHeight(child.left), getHeight(child.right)) + 1;

return child;
}

// Returns the balance factor of the given treeNode (difference between the
// height of the left subtree and the height of the right subtree)
int getBalance(Node treeNode) {
if (treeNode == null)
return 0;
return getHeight(treeNode.left) - getHeight(treeNode.right);
}

// Inserts a new node with the given key into the AVL tree rooted at the currentNode,
// balances the tree, and returns the new root of the subtree
Node insert(Node currentNode, int key) {
if (currentNode == null)
return (new Node(key));

if (key < currentNode.key)
currentNode.left = insert(currentNode.left, key);
else if (key > currentNode.key)
currentNode.right = insert(currentNode.right, key);
else
return currentNode;

currentNode.height = 1 + getMax(getHeight(currentNode.left), getHeight(currentNode.right));

int balance = getBalance(currentNode);

if (balance > 1 && key < currentNode.left.key)
return rotateRight(currentNode);

if (balance < -1 && key > currentNode.right.key)
return rotateLeft(currentNode);

if (balance > 1 && key > currentNode.left.key) {
currentNode.left = rotateLeft(currentNode.left);
return rotateRight(currentNode);
}

if (balance < -1 && key < currentNode.right.key) {
currentNode.right = rotateRight(currentNode.right);
return rotateLeft(currentNode);
}

return currentNode;
}

// Performs a pre-order traversal of the AVL tree rooted at the treeNode
// and prints the keys of the nodes
void preOrderTraversal(Node treeNode) {
if (treeNode != null) {
System.out.print(treeNode.key + " ");
preOrderTraversal(treeNode.left);
preOrderTraversal(treeNode.right);
}
}
}
```