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

36

Dynamic Trees*

Camil Demetrescu

Sapienza University of Rome

Irene Finocchi

Sapienza University of Rome

Giuseppe F. Italiano

University of Rome Tor Vergata

36.1Introduction

36.2Linking and Cutting Trees

Using Operations on Vertex-Disjoint PathsImplementing Operations on Vertex-Disjoint Paths

36.3Topology Trees

ConstructionUpdatesApplications

36.4Top Trees

UpdatesRepresentation and Applications

36.5ET Trees

UpdatesApplications

36.6Reachability Trees

36.7Conclusions

Acknowledgments

References

36.1Introduction

In this chapter we consider the problem of maintaining properties of a collection of vertex-disjoint trees that change over time as edges are added or deleted. The trees can be rooted or free, and vertices and edges may be associated ...

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