Amortized Complexity Analysis for Red-Black Trees and Splay Trees
Journal Title: International Journal of Innovative Research in Computer Science and Technology - Year 2018, Vol 6, Issue 6
Abstract
The basic conception behind the given problem definition is to discuss the working, operations and complexity analyses of some advanced data structures. The Data structures that we have discussed further are Red-Black trees and Splay trees.Red-Black trees are self-balancing trees having the properties of conventional tree data structures along with an added property of color of the node which can be either red or black. This inclusion of the property of color as a single bit property ensured maintenance of balance in the tree during operations such as insertion or deletion of nodes in Red-Black trees. Splay trees, on the other hand, reduce the complexity of operations such as insertion and deletion in trees by splayingor making the node as the root node thereby reducing the time complexity of insertion and deletions of a node. Furthermore, amortized analysis, which emerged from aggregate analysis, is an optimistic approach that can be used to calculate the amount of time and space required for the execution of various operations. Amortized analysis considers the number of operations required during the execution of an algorithm rather than the number of inputs required thus overlooking the worst case run time per operation, which can be too pessimistic.
Authors and Affiliations
Isha Ashish Bahendwar, RuchitPurshottam Bhardwaj, Prof. S. G. Mundada
Keywords
Related Articles
- EP ID EP748131
- DOI 10.21276/ijircst.2018.6.6.2
- Views 26
- Downloads 0
Platform Development for Online J.N.S.E
1. Jr. Newton Talent Search Exam is a scholarship examination for students from standard 3rd through 9th aimed at increasing the awareness amongst students regarding the necessity of competitive exams in the life of stud...
Innovations in Time Related Expression Recognition Using LSTM Networks
The proposed architecture leverages the strengths of both Convolutional Neural Network (CNN) and Bidirectional Long Short-Term (BLSTM) to create a robust model for temporal expression recognition in clinical texts. The C...
A Review on Speech Emotion Recognition Using Machine Learning
This paper focuses on the development of a robust speech emotion recognition system using a combination of different speech features with feature optimization techniques and speech de-noising technique to acquire improve...
Pseudo-Code Attack (PCA) in Software Engineering
Software development has been more important in recent technological advancements in both hardware and software. The creation of scripting languages is critical to the development of software. The development of programm...
Experimental Study of Quality of Plastic Details of the Oil-Field Equipment
In article quality of plastic details of the oil-field equipment depending on modes of production of their various constructions and composition of press materials was reviewed. By adjusting the operating parameters duri...