Amortized Complexity Analysis for Red-Black Trees and Splay Trees
Keywords:
Red-Black trees, Splay trees, Ammortization, Complexity, Insertion, DeletionAbstract
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.
Downloads
References
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (second ed.). MIT Press. pp. 273–301. ISBN 0-262-03293-7.
Rudolf Bayer (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms". Acta Informatica. 1 (4): 290–306. doi:10.1007/BF00289509.
Drozdek, Adam. Data Structures and Algorithms in Java (2 ed.). Sams Publishing. p. 323. ISBN 0534376681.
Leonidas J. Guibas and Robert Sedgewick (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual Symposium on Foundations of Computer Science. pp. 8–21. doi:10.1109/SFCS.1978.3.
"Red Black Trees". eternallyconfuzzled.com. Retrieved 2015-09-02.
Robert Sedgewick (2012). Red-Black BSTs. Coursera. A lot of people ask why did we use the name red– black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC which was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that’s why we picked the color red to distinguish red links, the types of links, in three nodes. So, that’s an answer to the question for people that have been asking.
"Where does the term "Red/Black Tree" come from?". programmers.stackexchange.com. Retrieved 2015-09- 02.
Andersson, Arne (1993-08-11). Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue, eds. "Balanced search trees made simple" (PDF). Algorithms and Data Structures (Proceedings). Lecture Notes in Computer Science. Springer-Verlag Berlin Heidelberg. 709: 60–71. doi:10.1007/3-540-57155- 8_236. ISBN 978-3-540-57155-1. Archived from the original on 2000-03-17.
Okasaki, Chris (1999-01-01). "Red-black trees in a functional setting" (PS). Journal of Functional Programming. 9 (4): 471–477. doi:10.1017/S0956796899003494. ISSN 1469-7653.
Sedgewick, Robert (1983). Algorithms (1st ed.). Addison-Wesley. ISBN 0-201-06672-6.
Sedgewick, Robert; Wayne, Kevin. "RedBlackBST.java". algs4.cs.princeton.edu. Retrieved 7 April 2018.
