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 123
- Downloads 0
INTEGRATION OF ICT AND E-GOVERNANCE IN RAJASTHAN
IT (Information Technology) is a term which is basically used to actions and technologies allied with the use of computer and communication resources. It was treated as an electronic technique to storage, retrieval and p...
INTERNET2: A COMPARATIVE STUDY AND TECHNOLOGICAL SOLUTION TO ACHIEVE HIGH SPEED NETWORKS
In current Indian scenario whenever it is required to access very large amount of data such as games or some commercial applications through commodity internet (internet1), speed becomes hurdle. It becomes tolerable for...
An Analysis on Density Based Clustering of Multi Dimensional Spatial Data
Mining knowledge from large amounts of spatial data is known as spatial data mining. It becomes a highly demanding field because huge amounts of spatial data have been collected in various applications ranging from geo-s...
GIRD COMPUTING- A TOOL FOR ENHANCING THE COMPUTING POWER
With the enormous increase in the demand for computing capacities, solutions with least investment have to found out. In this direction Grid technology is finding its way out of the academic incubator and entering into c...
ENGLISH ALPHABET RECOGNITION USING CHAIN CODE AND LCS
Since several decades OCR system is getting more and more useful in daily life for various purposes. Many researches have been done on many types of characters by using different approaches. However very little investiga...