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:
Hi Santrupti,
ReplyDeleteIn this blog you provide a good description about a specific data structure as AVL tree. I love the way you present data structure with the algorithms together, since we cannot tell the advantage or disadvantage of a give data structure alone without talking about the required operations on it. I do learn more knowledge with this blog. The blog is organized in good structure with clear label of citation.
Regards,
Hi Santrupti, good job!! You describe the AVL tree very well. It is one of the very important data structure, effective and yet simple enough to implement and use. Sadly there are still many students do not understand the AVL tree and how to use it. Your entry is informative and it could be used as a guideline for those students. The picture is very helpful as it shows how AVL rotates in branches. I hope that will be a useful resource for other students
ReplyDelete