File BinaryTreeAlgorithms.h

↰ Parent directory (ADS/tree)

The classic problems on binary trees and on binary search trees, written once for any representation of the nodes: a node is reached by a pointer, nil is nullptr, and its links and its key are read either by the member functions left(), right(), parent() and read() of BinaryTree [see File BinaryTree.h] or by the fields left, right, parent and key of a plain struct, as in the pseudocode of the book.

Definition (ADS/tree/BinaryTreeAlgorithms.h)

Detailed Description

The functions that build a tree return a BinaryTree, or take a callable make( v , l , r ) that makes a node of value v over the subtrees l and r, for any other representation.

  • lowestCommonAncestor( u , v ) walks up the links to the parents: the deeper node climbs to the depth of the other, then both climb together until they meet, O( h ) time and O( 1 ) space for a tree of height h. The usual alternative pushes the two paths on two stacks and pops them while their tops agree, O( h ) space; with many queries on a fixed tree the reduction of Bender and Farach-Colton to the range minimum on the Euler tour answers in O( 1 ) after O( n ) preprocessing [see File RangeMinimum.h], as the structure of Harel and Tarjan did first.

  • equalTrees( t , s ) tells whether two trees have the same shape and equal keys in the same places, by a simultaneous visit, O( n ) time and O( h ) space; with a comparison always true it compares the shapes only.

  • isSearchTree( t ) checks the order of a binary search tree: each key must lie in the open interval that its ancestors leave to it, and comparing a node with its children only is not enough. The visit carries the two ends down, O( n ) time and O( h ) space, the same as checking that the invisit is strictly increasing.

  • isRedBlackTree( t , red ) checks the constraints of a Red-Black colouring (the root black, no red node with a red child, the same number of black nodes on every path down to a leaf nil) by a postvisit that returns the black height of each subtree, O( n ) time.

  • searchTreeRange( t , lo , hi , f ) reports in increasing order the nodes of a binary search tree whose keys are in [ lo , hi ], a visit pruned where the key leaves the range: O( h + k ) time for k keys reported, since the nodes examined outside the range lie on the two paths that search for lo and for hi.

  • minimumHeightSearchTree( A ) builds the binary search tree of the sorted keys of A of the least height, :math:` lceil log_2( n + 1 ) rceil - 1 , by putting the middle key at the root and the two halves below, recursively: :math: T( n ) = 2 T( n / 2 ) + O( 1 ) = O( n ) ` time and :math:` O( log n ) ` stack. The same tree comes from the sorted list in O( n ) by building the subtrees in symmetric order, and any tree is rebalanced in place, in O( n ) time and O( 1 ) space, by the algorithm of Day, Stout and Warren.

  • fromPreorderInorder( pre , in ) rebuilds the binary tree of distinct values whose previsit is pre and whose invisit is in. The first value of pre is the root and splits in into the two subtrees; rather than looking the root up in in, the algorithm keeps a stack of the nodes whose right subtree is still open: the next value of pre is the left child of the top, unless the top is the next value of in, in which case the nodes are popped while they match in and the value becomes the right child of the last one. Each node is pushed and popped once, O( n ) time, with no table of the places and only the equality of the values.

  • cartesianBinaryTree( A ) is the Cartesian tree of Vuillemin as a BinaryTree: its root is the leftmost minimum of A and its subtrees the Cartesian trees of the parts before and after it, i.e., the binary tree whose invisit is A and which is a heap; with std::greater it is the maximal tree, with the maximum at the root. The parents come from cartesianTree() of File RangeMinimum.h, which builds them with a stack of the right spine in O( n ) time, against the :math:` O( n^2 ) ` of the recursion of the definition on a sorted A.

The contracts [see File Contract.h]: lowestCommonAncestor() needs two nodes of the same tree and returns a common ancestor none of whose children is one (a postcondition); searchTreeRange() needs lo <= hi; minimumHeightSearchTree() needs the keys strictly increasing and returns a tree of the least height (an audit); fromPreorderInorder() needs two visits of the same length and checks that the invisit of the tree built is in, which fails exactly when no tree of distinct values has those two visits; cartesianBinaryTree() returns a tree whose invisit is A (an audit). The functions are defined in BinaryTreeAlgorithms.tpp.

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

  1. Vuillemin, A unifying look at data structures, Communications of the ACM 23(4), 229-239, 1980, doi:10.1145/358841.358852

  1. Harel, R. E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing 13(2), 338-355, 1984, doi:10.1137/0213024

    1. Bender, M. Farach-Colton, The LCA problem revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN), LNCS 1776, 88-94, 2000, doi:10.1007/10719839_9

    1. Stout, B. L. Warren, Tree rebalancing in optimal time and space, Communications of the ACM 29(9), 902-908, 1986, doi:10.1145/6592.6599

    1. Guibas, R. Sedgewick, A dichromatic framework for balanced trees, Proceedings of the 19th FOCS, 8-21, 1978, doi:10.1109/SFCS.1978.3

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions