File CursorBinaryTree.h

↰ Parent directory (ADS/tree)

A binary tree with cursors, beyond the book: the nodes in a vector, each with its value and the places of its parent and of its two children, NIL if missing, so that the links are indices instead of pointers and the tree can be copied, saved or moved as a whole.

Definition (ADS/tree/CursorBinaryTree.h)

Detailed Description

A removed subtree returns its places to a free list, which the next insertions reuse. Moving along the tree, reading, writing and inserting a node take O( 1 ) amortized time; removing or copying a subtree takes time linear in its size.

The contracts [see File Contract.h]: a node is a used place, setRoot() needs an empty tree, a child is inserted where none is, 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 CursorBinaryTree.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes