Handbook of Data Structures and Applications, 2nd Edition

14

Randomized Dictionary Structures^*

C. Pandu Rangan

Indian Institute of Technology, Madras

14.1Introduction

14.2Preliminaries

Randomized Algorithms•Basics of Probability Theory•Conditional Probability•Some Basic Distributions•Tail Estimates

14.3Skip Lists

14.4Structural Properties of Skip Lists

Number of Levels in Skip List•Space Complexity

14.5Dictionary Operations

14.6Analysis of Dictionary Operations

14.7Randomized Binary Search Trees

Insertion in RBST•Deletion 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 ...