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 131
- Downloads 0
PERFORMANCE IMPROVEMENT USING FUZZY BASED DYNAMIC BUFFER SCHEME FOR EFFICIENT RRM IN WIMAX 16M NETWORKS
The IEEE 802.16m standard for Advanced mobile broadband wireless access provides a seamless application connectivity to other mobile and IP networks like UMTS, LTE and WLAN. In order to meet the ubiquitous service delive...
Image Processing Techniques and Neural Networks for Automated Cancer Analysis from Breast Thermographs-A Review
Clinical Infrared Thermography is the best suited technique for early detection of breast cancer. Interpretation of breast thermographs helps in identifying the abnormality in the region. In recent years, computer Aided...
IMPROVING THE SOFTWARE ARCHITECTURE THROUGH FUZZY CLUSTERING TECHNIQUE.
Software Architecture Recovery is one of the finest parts of reverse engineering. Several different techniques have been adopted in vast literature to recover Software Architecture. One of the techniques is clustering, w...
STUDY OF QoS ISSUES FOR ROUTING PROTOCOLS in IEEE 802.11s
This paper focuses on the two routing protocols proposed by IEEE 802.11s for Wireless Mesh Networks. Towards this goal, this paper contributes in several areas of Routing and Quality-of-Service provisioning in IEEE 802.1...
COMPUTER SIMULATION OF BLOOD FLOW IN ARTERIES AFFECTED BY MULTIPLE ANEURYSM
The aim of this study is a numerical simulation of hemodynamics in blood vessels with multiple fusiform aneurysms. Dilation of 0.25 is considered. Using computational fluid dynamics, hemodynamic factors such as velocity...