We know that data structure in
computer science refers to the way in which we organize and store data such
that it can be used in an efficient manner. You must have heard of stacks,
queues, linked lists, trees to organize data. All these are examples of data
structures that have advantages and handles the basic operations insert, delete
and search at varying degrees of complexity. Tree is an abstract data
structure. Many kinds of tree data structures exist. To name a few, we have
binary search trees(BST), red black trees, B trees, B+ trees, AVL trees and so
on.
What are AVL trees?
Also known as
self-balancing binary search trees, these were the first data structure of this
kind to be invented. BST is the simplest tree data structure; however, some
data sets can make the tree unbalanced which increases the complexity of basic
operations. A balanced tree is one in which difference between the height of
left sub-tree and right sub-tree is not greater than one.
AVL trees follow the same rules
that apply to the binary search tree, hence it is simple too. However, AVL
trees require some additional operations that keep them balanced and these
operations are called tree rotations. The acceptable height difference between
the left and the right sub-tree at any point in the AVL tree should be -1, 0 or
1. Hence, after every Insertion and deletion operation on these trees we need
to handle these rotation operations to keep the tree balanced. Refer to this
if you want to learn how insertion, deletion and searching work. The image
shows how insertion can be performed.
Why people prefer these trees?
The time complexity of the AVL
tree for insertion, deletion and search is O(logn) which makes this one of the
most efficient trees for retrieving stored data.
References:
