An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. It was named after its inventors, Adelson-Velskii and Landis. The AVL tree was the first data structure to be invented for maintaining a balanced binary search tree.
Properties of AVL Trees
AVL trees have the following properties:
- The heights of the left and right subtrees of any node differ by at most one.
- Every subtree of an AVL tree is itself an AVL tree.
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
Insertion into AVL Trees
When a new node is inserted into an AVL tree, the tree may become unbalanced. To maintain the balance, the tree is rebalanced by performing rotations. There are four types of rotations: left rotation, right rotation, left-right rotation, and right-left rotation.
The following example shows the steps for inserting a node with key value 15 into an AVL tree:
10 10
/ \ / \
5 12 5 12
/ \ / \
3 8 3 8
\
9
10 10
/ \ / \
5 12 5 12
/ \ / \
3 8 3 8
\
9
8 8
/ \ / \
5 10 5 10
/ / \ \ / \
3 9 12 7 9 12
\
7
8 8
/ \ / \
5 10 5 10
/ / \ \ / \
3 9 12 7 9 12
/
7
Deletion from AVL Trees
When a node is deleted from an AVL tree, the tree may become unbalanced. The tree is rebalanced in the same way as for insertion.
Time Complexity of AVL Trees
The time complexity of basic operations on an AVL tree, such as searching, insertion, and deletion, is O(log n) on average, where n is the number of nodes in the tree.
Conclusion
In this article, we have discussed the AVL tree data structure, which is a self-balancing binary search tree. We have also provided examples of AVL tree operations, such as insertion and deletion, and discussed the time complexity of these operations. If used correctly, AVL trees can be a powerful tool for organizing and manipulating data.