April 09, 2024
Understanding AVL Trees with TypeScript: A Balanced Approach to Efficient Data Structures
In the realm of data structures and algorithms, balance is key. When it comes to binary search trees, maintaining balance is crucial for efficient operations like insertion, deletion, and searching. One such balanced binary search tree is the AVL tree, named after its inventors Adelson-Velsky and Landis. In this blog, we'll delve into the world of AVL trees, exploring their structure, operations, and implementation using TypeScript.
What is an AVL Tree?
An AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees (known as the balance factor) of any node is at most 1. This balance factor ensures that the tree remains balanced, preventing it from degenerating into a linear data structure, which could result in poor performance for operations like searching, insertion, and deletion.
Structure of an AVL Tree
At its core, an AVL tree maintains the properties of a binary search tree, where each node has at most two children: a left child and a right child. Additionally, each node in an AVL tree stores a balance factor, which is calculated as the difference between the height of its left subtree and the height of its right subtree.
The balance factor of a node can be one of three values: -1, 0, or 1. If the balance factor of a node is -1, it indicates that the right subtree is taller by one level. Conversely, a balance factor of 1 indicates that the left subtree is taller by one level. A balance factor of 0 means that the heights of the left and right subtrees are equal.
Operations on AVL Trees
Insertion: When inserting a new node into an AVL tree, the tree may become unbalanced. To maintain balance, rotation operations are performed based on the balance factors of nodes. These rotations include single rotations (left or right) and double rotations (left-right or right-left) to restore balance while preserving the properties of a binary search tree.
Deletion: Similar to insertion, deletion in an AVL tree may result in an imbalance. After removing a node, rotations are performed to restore balance. These rotations ensure that the AVL tree remains balanced while preserving the order of its elements.
Searching: Searching in an AVL tree follows the principles of a binary search tree. Due to its balanced nature, searching in an AVL tree has an average time complexity of O(log n), making it efficient for retrieval operations.
Implementing AVL Trees in TypeScript
Let's dive into implementing an AVL tree in TypeScript. Below is a basic outline of the AVL tree class:
class TreeNode {
value: number;
left: TreeNode | null;
right: TreeNode | null;
height: number;
constructor(value: number) {
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
}
class AVLTree {
root: TreeNode | null;
constructor() {
this.root = null;
}
// Helper function to calculate height of a node
getHeight(node: TreeNode | null): number {
if (node === null) return 0;
return node.height;
}
// Helper function to update height of a node
updateHeight(node: TreeNode): void {
node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
}
// Perform right rotation
rotateRight(y: TreeNode): TreeNode {
const x = y.left!;
const T2 = x.right;
x.right = y;
y.left = T2;
this.updateHeight(y);
this.updateHeight(x);
return x;
}
// Perform left rotation
rotateLeft(x: TreeNode): TreeNode {
const y = x.right!;
const T2 = y.left;
y.left = x;
x.right = T2;
this.updateHeight(x);
this.updateHeight(y);
return y;
}
// Get balance factor of a node
getBalance(node: TreeNode | null): number {
if (node === null) return 0;
return this.getHeight(node.left) - this.getHeight(node.right);
}
// Insert a node into the AVL tree
insert(value: number): TreeNode {
this.root = this.insertNode(this.root, value);
return this.root!;
}
insertNode(node: TreeNode | null, value: number): TreeNode {
if (node === null) return new TreeNode(value);
if (value < node.value) {
node.left = this.insertNode(node.left, value);
} else if (value > node.value) {
node.right = this.insertNode(node.right, value);
} else {
// Duplicate values not allowed
return node;
}
// Update height and balance the tree
this.updateHeight(node);
const balance = this.getBalance(node);
// Left Left Case
if (balance > 1 && value < node.left!.value) {
return this.rotateRight(node);
}
// Right Right Case
if (balance < -1 && value > node.right!.value) {
return this.rotateLeft(node);
}
// Left Right Case
if (balance > 1 && value > node.left!.value) {
node.left = this.rotateLeft(node.left!);
return this.rotateRight(node);
}
// Right Left Case
if (balance < -1 && value < node.right!.value) {
node.right = this.rotateRight(node.right!);
return this.rotateLeft(node);
}
return node;
}
// Perform in-order traversal
inOrderTraversal(node: TreeNode | null): void {
if (node !== null) {
this.inOrderTraversal(node.left);
console.log(node.value);
this.inOrderTraversal(node.right);
}
}
}
// Example usage
const avlTree = new AVLTree();
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
avlTree.insert(25);
console.log("In-order traversal of AVL tree:");
avlTree.inOrderTraversal(avlTree.root);
Conclusion:
In this blog, we've explored the concept of AVL trees, their importance in maintaining balance in binary search trees, and their implementation in TypeScript. By leveraging rotations and balance factors, AVL trees ensure efficient data storage and retrieval, making them invaluable in various applications requiring dynamic datasets. Understanding AVL trees provides a strong foundation for tackling complex data structure and algorithm problems, making them a crucial topic for every aspiring software engineer to master.
256 views