File Tree.h

↰ Parent directory (ADS/tree)

The ordered TREE of the book, realized with pointers to the parent, to the first child and to the next sibling, and its visits.

Definition (ADS/tree/Tree.h)

Detailed Description

A node and the subtree rooted in it are the same thing, a Tree: the constructor makes an isolated node, insertChild() and insertSibling() hang a whole tree under a node in O( 1 ) time, deleteChild() and deleteSibling() destroy a subtree in time linear in its size. A tree owns its subtrees: deleting the root of a tree destroys all of it; a tree whose insertion is refused (its contract is violated) stays the caller’s. As in the book, nil is nullptr.

The visits examine each node once, in :math:` Theta( n ) ` time: the previsit examines the root and then visits the subtrees :math:` T_0 , ldots , T_{k-1} ` of its children in order, the postvisit visits the subtrees and then examines the root, the invisit with index i visits the first i subtrees, examines the root and visits the others, and the visit by levels (bfs) examines all the nodes of level l before those of level l + 1, using a queue. copy() makes a deep copy of a subtree.

The contracts [see File Contract.h]: the tree inserted is a root (the precondition of the book, t.parent() = nil) other than the node itself, insertSibling() needs a node that is not a root, and the visits a node; the invariant is that each child of a node has that node as its parent, down the subtree. The operations are defined in Tree.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions