File SearchTree.h

↰ Parent directory (ADS/tree)

The binary search tree (ABR) and the Red-Black tree of the book, as a DICTIONARY [see File ADT.h] from keys to values.

Definition (ADS/tree/SearchTree.h)

Detailed Description

In a binary search tree the keys in the left subtree of a node u are smaller than the key of u, and those in the right subtree larger, so that the invisit examines the keys in increasing order; lookupNode(), insertNode() and removeNode() go down one path and take O( h ) time, h being the height of the tree, which is O( n ) in the worst case.

A Red-Black tree is a binary search tree whose nodes are red or black, with the constraints (V1) the root is black, (V2) the leaves are black, (V3) both children of a red node are black, (V4) all the paths from a node to the leaves below it have the same number of black nodes, its black height b( u ). The subtree of u has at least :math:` 2^{b(u)} - 1 ` internal nodes (Teorema 6.1), no path from the root to a leaf is longer than twice another one (Teorema 6.2), and the height is :math:`[

h leq 2 log_2( n + 1 )

` (Teorema 6.3). The procedures are those of the binary search tree, plus balanceInsert() after an insertion and balanceDelete() after the removal of a black node, which restore the constraints with O( log n ) changes of color and at most 3 rotations, in O( log n ) time.

The two trees are one class, SearchTree< K , V , RB >, the procedures of the book written once and the two balancing calls under if constexpr( RB ) where the book “highlights them in black”; BinarySearchTree< K , V > and RedBlackTree< K , V > are its two instances. The leaves are one sentinel node of the tree, black, which the book allows and which balanceDelete() needs: when the removed node had no children, the leaf t that replaces it must know its parent, which link() writes in the sentinel. Three points of the pseudocode are mended, each marked in the code: balanceDelete() stops when t is the root rather than when t is the old root T, which a rotation of the case (1) may have moved down; the case (4) climbs to the root instead of reading the old T; and the Red-Black insertNode() returns the root also when the key was there already.

The contracts [see File Contract.h]: after insert() the key is there and after remove() it is not; key(), value(), successorNode() and predecessorNode() need a node; the invariant is the order of the keys, the parents and, for a Red-Black tree, the constraints (V1)-(V4) [see valid()]. The operations are defined in SearchTree.tpp.

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

  1. Bayer, Symmetric binary B-trees: data structure and maintenance algorithms, Acta Informatica 1(4), 290-306, 1972, doi:10.1007/BF00289509

    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

Included By

Namespaces

Classes

Enums

Typedefs