File BinaryTree.h

↰ Parent directory (ADS/tree)

The binary TREE of the book: an ordered tree where each node has at most two children, told apart as the left and the right one, realized with pointers to the parent and to the two children.

Definition (ADS/tree/BinaryTree.h)

Detailed Description

Moving along the tree, reading, writing and inserting take O( 1 ) time, deleting a subtree time linear in its size. As for Tree, a node and its subtree are the same thing, a tree owns its subtrees (a tree whose insertion is refused stays the caller’s), and nil is nullptr.

The visit dfs() examines a node before its subtrees (previsit), between them (invisit, or symmetric visit) or after them (postvisit). An ordered tree T is represented by the binary tree B whose left child of a node is its first child in T and whose right child is its next sibling in T [see to_binary()]: the previsits of T and of B are the same, and the postvisit of T is the invisit of B.

detachLeft() and detachRight() cut a subtree off its parent without destroying it, in O( 1 ) time: the subtree becomes a root owned by the caller, ready to be inserted elsewhere, which moves subtrees around (a mirror, a rotation) with no copy.

copy() makes a deep copy of a subtree and join() a new root with the copies of two trees as children, in time linear in their size.

The ranges preorder(), inorder() and postorder() walk the nodes of a subtree by the links to the parents, with no stack and no recursion, in O( n ) time overall and O( 1 ) extra space: each node is left at most once from each of its three visits.

to_list() writes a binary tree as a parenthesized list, () for the empty tree and ( v L R ) for the root v with the subtrees L and R, e.g., ( 8 () ( 5 ( 27 () () ) ( 16 () () ) ) ), and from_list() reads it back; the values are written with << and read with >>, and must contain no space nor parenthesis.

A complete d-ary tree, whose internal nodes have d children, is stored in a vector, the root in the place 0 and the children of the node i in the places :math:` d i + 1 , ldots , d i + d ` [see dary_child()].

The contracts [see File Contract.h]: the tree inserted is a root other than the node itself and goes where no child is; the subtree detached is a root and its place is empty; the invariant is that each child has its parent as parent, down the subtree; the places of a d-ary tree need d >= 1, a child 1 <= j <= d and a place i > 0 to have a parent. The operations are defined in BinaryTree.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 5.5 and 5.6, 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