AVL Tree
An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. This ensures worst-case O(log n) time for search, insert and delete.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class AVLNode {
int height;
int value;
AVLNode left;
AVLNode right;
}
// Rotation helpers
AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
x.right = y.left;
y.left = x;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| struct AVLNode {
int height;
int value;
AVLNode *left;
AVLNode *right;
};
// Get node height
int height(AVLNode* node) {
if (!node) {
return 0;
}
return node->height;
}
// Rebalance on insert
void rebalance(AVLNode* &node) {
int balance = height(node->left) - height(node->right);
if (balance > 1) {
// Left heavy - rotate
if (height(node->left->left) > height(node->left->right)) {
// Left Left
node = rightRotate(node);
} else {
// Left Right
node->left = leftRotate(node->left);
node = rightRotate(node);
}
}
}
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class AVLNode:
def __init__(self, value):
self.value = value
self.height = 1
self.left = None
self.right = None
# Update height
def update_height(node):
node.height = max(height(node.left), height(node.right)) + 1
# Rebalance
def rebalance(node):
# Left heavy
if height(node.left) - height(node.right) > 1:
# Left left case
if height(node.left.left) > height(node.left.right):
return right_rotate(node)
# Left right case
else:
node.left = left_rotate(node.left)
return right_rotate(node)
# Right heavy
elif height(node.right) - height(node.left) > 1:
# Code mirrors left heavy logic
return node
|
AVL trees provide guaranteed O(log n) times for dynamic operations by maintaining balance. Useful for time-critical applications like real-time systems.
An AVL tree is a height-balanced binary search tree. In an AVL tree, the difference between the heights of the right subtree and left subtree of every node is either -1, 0, or 1. The difference between the heights of the subtree is maintained by a factor named as balance factor. When inserting a new key in an AVL tree, you first compare the key with root. If the key is greater than root, then it is greater than all the nodes in left subtree of root. AVL trees remain balanced by four kinds of rotations during insertion or deletion. The rotation you choose is based on the position relationship of the unbalanced node and the inserted node. AVL trees have an advantage over binary search trees because they guarantee that the maximum time complexity for all the operations will never exceed O(logN).
AVL trees are a type of self-balancing binary search tree. They are often used for in-memory sorts of sets and dictionaries. They are also used in database applications where there are frequent data lookups.
Here are some LeetCode problems that can be solved using AVL trees:
Count of Smaller Numbers After Self
This problem can be solved using an AVL tree with a time complexity of O(nLogn).
Find Median from Data Stream
This problem can be solved using an AVL tree with a 93.1% faster and 100% less Java solution.
AVL trees are faster than BST trees because they are self-balancing and have a height that is as small as possible. The worst-case time complexity of all operations for an AVL tree is O(log N), while for a BST it is O(N).
AVL trees are a type of self-balancing binary search tree. They have the ability to rebalance themselves, which makes them faster in the worst case. AVL trees guarantee a performance of O(logN) in the worst case for all operations, including insertion, deletion, and searching. In a binary search tree (BST), the value of the left node must be smaller than the parent node, and the value of the right node must be greater than the parent node. If values are inserted in a decreasing or increasing order, the BST will be one sided and the search time will be O(n). However, if you use an AVL tree, the tree will balance itself using rotations. Insertion and deletion are complex in an AVL tree because it requires multiple rotations to balance the tree. In a BST, insertion and deletion are easy because no rotations are required.
AVL Tree
An AVL (Adelson-Velsky and Landis) tree is a type of binary search tree that self-balances. In an AVL tree, the heights of the two child subtrees of every node differ by at most one. If they differ by more than one at any time, rebalancing is done through rotations. This ensures that the tree remains approximately balanced, resulting in O(log n) time complexity for search, insert, and delete operations.
Java Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Node {
int key, height;
Node left, right;
Node(int key) {
this.key = key;
this.height = 1; // height of new node is set to 1
}
}
class AVLTree {
Node root;
int height(Node node) {
return (node == null) ? 0 : node.height;
}
int balanceFactor(Node node) {
return (node == null) ? 0 : height(node.left) - height(node.right);
}
Node rotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// Similar logic applies for rotateLeft
// ...
// Insert and balance tree
Node insert(Node node, int key) {
// Standard BST insert
// ...
// Update height and balance tree
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = balanceFactor(node);
// Perform rotations
if (balance > 1 && key < node.left.key)
return rotateRight(node);
// Other cases
// ...
return node;
}
}
|
In Java, we define an AVL tree using a Node class that holds the key, height, and left and right children. The main AVLTree class contains methods for rotations and balancing the tree.
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| struct Node {
int key, height;
Node *left, *right;
Node(int key) : key(key), height(1), left(nullptr), right(nullptr) {}
};
class AVLTree {
public:
Node* root;
int height(Node* node) {
return (node == nullptr) ? 0 : node->height;
}
int balanceFactor(Node* node) {
return (node == nullptr) ? 0 : height(node->left) - height(node->right);
}
Node* rotateRight(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
// Update heights and return new root
// ...
return x;
}
// Insert and balance tree
Node* insert(Node* node, int key) {
// Standard BST insert
// ...
// Update height and balance tree
// ...
}
};
|
In C++, we similarly define a Node struct and an AVLTree class. The class methods for rotations and balancing mirror the Java implementation.
Python Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Node:
def __init__(self, key):
self.key = key
self.height = 1
self.left = None
self.right = None
class AVLTree:
def __init__(self):
self.root = None
def height(self, node):
return 0 if node is None else node.height
def balance_factor(self, node):
return 0 if node is None else self.height(node.left) - self.height(node.right)
def rotate_right(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
# Update heights and return new root
# ...
def insert(self, root, key):
# Standard BST insert
# ...
# Update height and balance tree
# ...
|
In Python, the Node class and AVLTree class are quite straightforward. We define methods for rotations and balancing like in Java and C++.
AVL Trees are a crucial data structure for many applications where quick data retrieval is necessary. They optimize the tree balancing to ensure quick operations, and are used in databases, file systems, and other systems that require fast data access.