File ParentTree.h

↰ Parent directory (ADS/tree)

The tree as a vector of parents: the nodes are 0 , … , n - 1, and p[ i ] is the parent of i, or -1 if i is a root.

Definition (ADS/tree/ParentTree.h)

Detailed Description

It answers parent() alone, in O( 1 ) time and with the least memory, which is all that is needed when a tree is built and walked towards the root, as the trees of the visits of a graph; the order among siblings is lost, unless it is the one of their numbers. Since setParent() may hang any node anywhere, the structure is a forest of n isolated nodes at the start.

The contracts [see File Contract.h]: the nodes are in [ 0 , n ), and a node is not its own parent. The operations are defined in ParentTree.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 5.4, https://algoritmicamente.it/materiali/libro/capitoli/cap05.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes