File ChildListTree.h

↰ Parent directory (ADS/tree)

An ordered tree realized with lists of children, beyond the book: the nodes in a vector, each with its value, the place of its parent and the List [see File List.h] of the places of its children, in their order.

Definition (ADS/tree/ChildListTree.h)

Detailed Description

A node also keeps the position of its own cell in the list of its parent, so that rightSibling() is the next cell and takes O( 1 ) time, as leftmostChild(), insertChild() and insertSibling(); the children of a node are scanned in O( 1 ) time each, which is what this realization is for, and a removed subtree returns its places to a free list. The operations and the visits are those of CursorTree [see File CursorTree.h].

The contracts [see File Contract.h]: a node is a used place, and a sibling is inserted next to a node that is not the root; the invariant is that the nodes reached from the root are used, are in the list of their parent at their own position, and are all the nodes. The operations are defined in ChildListTree.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 5.1-5.3, https://algoritmicamente.it/materiali/libro/capitoli/cap05.pdf

    1. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983, section 3.3 (the lists of children)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes