data structures Disjoint Set A disjoint-set data structure maintains a collection \(\mathcal{S} = \{S_{1}, S_{2}, \dots, S_{k}\}\) of disjoint dynamic sets. A weighted-union heuristic Theorem 1 Using linked-list representation of disjoint sets and the weighted union heuristic, a sequence of \(m\) MAKE-SET, UNION, and FIND-SET

data structures Graph Breadth-first search Lemma 1 Let \(G = (V, E)\) be a directed or undirected graph, and let \(s \in V\) be an arbitrary vertex. Then for any edge \((u, v) \in E\),\( \delta (s, v) \leq \delta (s, u) + 1\). Lemma 2 Let \(G = (V,

data structures Tree Binary Tree A binary tree \(T\) is a structure defined on a finite set of nodes that either contains no nodes, or is composed of three disjoint set of nodes: a root node, a binary tree called its left subtree, and a binary tree