O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

14

Randomized Dictionary Structures*

C. Pandu Rangan

Indian Institute of Technology, Madras

14.1Introduction

14.2Preliminaries

Randomized AlgorithmsBasics of Probability TheoryConditional ProbabilitySome Basic DistributionsTail Estimates

14.3Skip Lists

14.4Structural Properties of Skip Lists

Number of Levels in Skip ListSpace Complexity

14.5Dictionary Operations

14.6Analysis of Dictionary Operations

14.7Randomized Binary Search Trees

Insertion in RBSTDeletion in RBST

14.8Bibliographic Remarks

References

14.1Introduction

In the last couple of decades, there has been a tremendous growth in using randomness as a powerful source of computation. Incorporating randomness in computation often results in a much simpler and more easily implementable ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required