File ArrayBinaryTree.h

↰ Parent directory (ADS/tree)

A binary tree in a positional vector, beyond the book: the root in the place 0, the children of the place i in 2 i + 1 and 2 i + 2, its parent in :math:` lfloor ( i - 1 ) / 2 rfloor ` [see dary_child()], an empty place where no node is.

Definition (ADS/tree/ArrayBinaryTree.h)

Detailed Description

Moving along the tree, reading and writing take O( 1 ) time; the vector grows to the deepest place used, so that a tree of height h takes :math:` O( 2^h ) ` space, which suits the trees nearly complete. insertLeft() and insertRight() copy a whole tree under a node and remove() empties a subtree, in time linear in the places of the subtree. A node is a place, NIL if missing.

The contracts [see File Contract.h]: read() and write() need a node, setRoot() an empty tree, and a subtree is inserted under a node where no child is; the invariant is that each node but the root has its parent. The operations are defined in ArrayBinaryTree.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