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

33

Persistent Data Structures*

Haim Kaplan

Tel Aviv University

33.1Introduction

33.2Algorithmic Applications of Persistent Data Structures

33.3General Techniques for Making Data Structures Persistent

The Fat Node MethodNode Copying and Node SplittingHandling ArraysMaking Data Structures Confluently Persistent

33.4Making Specific Data Structures More Efficient

Redundant Binary CountersPersistent Deques

33.5Concluding Remarks and Open Questions

Acknowledgments

References

33.1Introduction

Think of the initial configuration of a data structure as version zero, and of every subsequent update operation as generating a new version of the data structure. Then a data structure is called persistent if it supports access to all versions and it is called ...

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