File CursorTree.h

↰ Parent directory (ADS/tree)

An ordered tree with cursors, beyond the book: the nodes in a vector, each with its value and the places of its parent, of its first child and of its next sibling, NIL if missing, as the Tree with pointers [see File Tree.h] but with indices.

Definition (ADS/tree/CursorTree.h)

Detailed Description

A removed subtree returns its places to a free list. insertChild() and insertSibling() hang a new node, insertChildTree() and insertSiblingTree() a copy of a subtree of another tree, as first child or as next sibling; the visits are those of the book.

The contracts [see File Contract.h]: a node is a used place, a sibling is inserted next to a node that is not the root, and the subtree copied is a node of the other tree; the invariant is that the nodes reached from the root link back to their parent and are all the nodes. The operations are defined in CursorTree.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes