Literature

Material

Amortized Analysis [CLRS01]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms, 2nd ed.
The MIT Press, 2001, 405-430.
ISBN 0-262-03293-7.

Leftists Heaps [T83]

Robert Endre Tarjan.
Data Structures and Network Algorithms.
Society for Industrial and Applied Mathematics, 1983, 38-43.
ISBN 0-89871-187-8.

Skew Heaps [W95]

Mark Allen Weiss.
Data Structures and Algorithm Analysis, 2nd ed.
The Benjamin/Cummings Publishing Company, Inc., 1995, 195-197, 425-427.
ISBN 0-8053-9057-X.

Skip Lists [P89]

William Pugh.
Skip Lists: A Probabilistic Alternative to Balanced Trees.
Lecture Notes in Computer Science 382.
Springer-Verlag, 1989, 437-449.
ISBN 3-540-51542-9.

Scapegoat Trees [GR93]

Igal Galperin, Ronald L. Rivest.
Scapegoat Trees.
Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms.
ACM Press, 1993, 165-174.
ISBN 0-89871-313-7.

Universal and Perfect Hashing [CLRS01]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms, 2nd ed.
The MIT Press, 2001, 221-252.
ISBN 0-262-03293-7.

Disjoint Sets [K90]

Jeffrey H. Kingston.
Algorithms and Data Structures - Design, Correctness, Analysis.
Addison Wesley, 1990, 202-218.
ISBN 0-201-41705-7.

Disjoint Sets with Backtracking [WT89]

Jeffrey Westbrook, Robert E. Tarjan.
Amortized Analysis of Algorithms for Set Union with Backtracking.
SIAM Journal on Computing 18(1).
Society for Industrial and Applied Mathematics, 1989, 1-11.
ISBN 0097-5397.

Persistent Data Structures [DSST89]

James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan.
Making Data Structures Persistent.
Journal of Computer and System Sciences 38.
Academic Press, Inc., 1989, 86-97.
ISBN 022-0000.

Van Emde Boas Trees [F03]

Gudmund Frandsen.
Van Emde Boas Trees.
Aarhus, 2003, 1-5.

Dynamization [W93]

Derick Wood.
Data Structures, Algorithms, and Performance.
Addison-Wesley, 1993, 540-546, 558-563.
ISBN 0-201-52148-2.

Balanced Trees and AVL-trees [AFL05]

Arne Andersson, Rolf Fagerberg, Kim S. Larsen.
Balanced Binary Search Trees.
Chapter 10 of Handbook of Data Structures and Applications, Dinesh P. Mehta, Sartaj Sahni (eds.),
Chapman & Hall/CRC Computer & Information Science Series, pages 10-4 - 10-8.
CRC Press, 2005.
ISBN 1-58488-435-5.

AVL-Tree Operations [AVL]

1 page.

Self-Adjusting Lists and Splay Trees [K90]

Jeffrey H. Kingston.
Algorithms and Data Structures - design, correctness, analysis.
Addison-Wesley, 1990, 98-102, 110-116.
ISBN 0-201-41705-7.

Randomized Search Trees [AS89]

Cecilia R. Aragon, Raimund Seidel.
Proceedings of the 30th Annual Symposium on Foundations of Computer Science.
IEEE Computer Society Press, 1989, 540-545.

Sub-Logaritmic Searching [A95]

Arne Andersson.
Sublogarithmic Searching without Multiplications.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science.
IEEE Computer Society Press, 1995, 655-663.
ISBN 0-8186-7183-1.