A Sorting based Algorithm for the Construction of Balanced Search Tree Automatically for smaller elements and with minimum of one Rotation for Greater Elements from BST
Journal Title: Indian Journal of Computer Science and Engineering - Year 2013, Vol 4, Issue 4
Abstract
Tree is a best data structure for data storage and retrieval of data whenever it could be accommodated in the memory. At the same time, this is true only when the tree is height-balanced and lesser depth from the root. In this paper, we propose a sorting based new algorithm to construct the Balanced search tree from Binary Search Tree with minimum of one rotation for the given elements n >14. If the given elements n < 14 then the algorithm automatically constructs the Balanced Search tree without needs any rotations. To maintain the tree in shape and depth, we apply two strategies in the input data. The first one is to apply sorting on the given input data. And the second one is to find the multiples of two positions on the sorted input data. Then, we compare the 3 positions of multiples of two and rewrite it by descending order and repeat this for the entire elements and the rest of the positions also on the sorted data. After, a new input data is formed. Then construct the Binary search tree on the given input data. At last, we will find the output as; a height balanced BST (AVL) with lesser depth from the root for the smaller data such as N < 14, for the greater element N >14 , it requires one rotation from the BST., and the search cost is minimum as possible. In this paper, few case studies have been carried out and analyzed in terms of height and space requirement. Hence, the height of the output BST, normally obtain by maximum height as N/2 or (N/2) – 3.
Authors and Affiliations
S. Muthusundari , Dr. R. M. Suresh
Keywords
Related Articles
- EP ID EP161941
- DOI -
- Views 124
- Downloads 0
QOS PARAMETER ANALYSIS ON AODV AND DSDV PROTOCOLS IN A WIRELESS NETWORK
Wireless networks are characterized by a lack of infrastructure, and by a random and quickly changing network topology; thus the need for a robust dynamic routing protocol that can accommodate such an environment. To imp...
Implementation of Calendar Chart in CICS Mainframes for Business Analysis
This paper provides a business solution to implement Calendar Chart in Mainframes for analysing the progress of a Bank by giving detailed report of number of new accounts created for the bank. A calendar chart is a visua...
VERIFICATION OF BEHAVIOR PRESERVATION IN UML SEQUENCE DIAGRAMS USING GRAPH MODELS
The verification of model transformations is gaining significant attention recent years. This paper presents an approach for verifying the behavioral preservance property of UML behavioral models that have been subjected...
PERFORMANCE EVALUATION OF DIFFERENT LINE CODES
The ability to communicate has differentiated mankind from other species. 20lh century has seen considerable emphasis on development of efficient communication techniques because how well one is able to communicate has b...
COMPARATIVE PERFORMANCE ANALYSIS OF MULTI-DYNAMIC TIME QUANTUM ROUND ROBIN (MDTQRR) ALGORITHM WITH ARRIVAL TIME
CPU being considered a primary computer resource, its scheduling is central to operating-system design. A thorough performance evaluation of various scheduling algorithms manifests that Round Robin Algorithm is considere...