Research Article
Article:Balancing of AVL tree using virtual node
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 7 - Issue 14 |
| Published: October 2010 |
| Authors: Rajeev R. Kumar Tripathi |
10.5120/1331-1695
|
Rajeev R. Kumar Tripathi . Article:Balancing of AVL tree using virtual node. International Journal of Computer Applications. 7, 14 (October 2010), 12-15. DOI=10.5120/1331-1695
@article{ 10.5120/1331-1695,
author = { Rajeev R. Kumar Tripathi },
title = { Article:Balancing of AVL tree using virtual node },
journal = { International Journal of Computer Applications },
year = { 2010 },
volume = { 7 },
number = { 14 },
pages = { 12-15 },
doi = { 10.5120/1331-1695 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2010
%A Rajeev R. Kumar Tripathi
%T Article:Balancing of AVL tree using virtual node%T
%J International Journal of Computer Applications
%V 7
%N 14
%P 12-15
%R 10.5120/1331-1695
%I Foundation of Computer Science (FCS), NY, USA
Abstract
AVL tree is the first dynamic tree in data structure which minimizes its height during insertion and deletion operations. This is because searching time is directly proportional to the height of binary search tree (BST) [1-9].When insertion operation is performed it may result into increasing the height of the tree and when deletion is performed it may result into decreasing the height. To make the BST a height balance tree (AVL tree) creators of the AVL tree proposed various rotations. This paper proposes the balancing of the AVL tree using the concept of virtual node. This virtual node is a hypothetical node which is inserted into the inorder traversal of the BST and by doing the inorder traversal (left, root, right) we make a BST. Ultimately this virtual node is deleted to get an AVL tree.
References
- R.R.K.Tripathi, Concepts of Data Structure Using C, Katson Publication, 1st edition.
- Ellis Horowitz & Sartaj Sahni, Fundamentals of Data Structures, Galgotia Book Source, 1st edition.
- Trembley & Sorenson, An Introduction to Data Structures with Applications, TMH, 2nd edition.
- Robert L. Kruse, Data Structure and Program Design, PHI, 3rd edition.
- Yedidyah Langsam, Moshe J. Augenstein and Aaron M. Tenenbaum. Data Structures Using C and C++, PHI, 2nd edition.
- Seymour Lipschutz, Data Structures, McGraw-Hill,1st edition.
- Adam Drozdek, Data Structures & Algorithms in Java, Vikas Publication, 1st edition.
- Bhagat Singh and Thomas L. Naps, Introduction to Data Structures, Galgotia Book Source, 1st edition.
- Marry E.S. Loomis, Data Management & File Structures, PHI, 2nd edition.
Index Terms
Keywords