Amortized Complexity Analysis for Red-Black Trees and Splay Trees

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.