File PreorderArrayTree.h

↰ Parent directory (ADS/tree)

An ordered tree in a vector in preorder, beyond the book: the place i holds the value of the i-th node of the previsit and the place of its parent, NIL for the root in the place 0.

Definition (ADS/tree/PreorderArrayTree.h)

Detailed Description

The subtree of a node is the stretch of the vector that starts with it and ends before the first place whose parent precedes it, so that the first child of i, if any, is i + 1, and the next sibling is the place after its subtree. Reading and writing take O( 1 ) time, moving along the tree and inserting or removing a subtree O( n ), since the places after it shift and their parents are renumbered. It extends the vector of parents of section 5.4 [see File ParentTree.h] with the values and the order of the children.

The contracts [see File Contract.h]: a node is a place of the vector, and a sibling is inserted next to a node that is not the root; the invariant is that the root comes first and each other node after its parent. The operations are defined in PreorderArrayTree.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

  • ADS/Contract.h (File Contract.h)

  • ADS/tree/impl/PreorderArrayTree.tpp

  • ranges

  • stdexcept

  • vector

Namespaces

Classes