An AVL tree is a type of self-balancing binary search tree, in which the nodes are arranged such that the heights of the two child subtrees of any node differ by at most one. This balancing of the tree allows it to be more efficient when searching for values, as the tree is more likely to be closer to a balanced state.
The height of an AVL tree is the number of edges in the longest path from the root to a leaf. The height of an empty tree is defined to be −1. An AVL tree is said to be balanced if the height of the left and right subtrees of the root differ by at most 1, and the left and right subtrees are AVL trees.
The following is an example of how to insert a node into an AVL tree in JavaScript.
function insert(root, key) {
// Step 1 - Perform normal BST insertion
if (root == null)
return new Node(key);
if (key < root.key)
root.left = insert(root.left, key);
else if (key > root.key)
root.right = insert(root.right, key);
else // Equal keys are not allowed in BST
return root;
// Step 2 - Update the height of the
// ancestor node
root.height = 1 + Math.max(height(root.left),
height(root.right));
// Step 3 - Get the balance factor
let balance = getBalance(root);
// Step 4 - If the node is unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 && key < root.left.key)
return rightRotate(root);
// Right Right Case
if (balance < -1 && key > root.right.key)
return leftRotate(root);
// Left Right Case
if (balance > 1 && key > root.left.key) {
root.left = leftRotate(root.left);
return rightRotate(root);
}
// Right Left Case
if (balance < -1 && key < root.right.key) {
root.right = rightRotate(root.right);
return leftRotate(root);
}
/* return the (unchanged) node pointer */
return root;
}
Implement an AVL tree in JavaScript.
Given a list of numbers, create an AVL tree of those numbers.
Find the height of an AVL tree.
Find the minimum value in an AVL tree.
Find the maximum value in an AVL tree.
Find the predecessor of a given value in an AVL tree.
Find the successor of a given value in an AVL tree.
Delete a value from an AVL tree.
Perform a pre-order traversal of an AVL tree.
Perform an in-order traversal of an AVL tree.
Perform a post-order traversal of an AVL tree.