Nodes, Trees, and Forests Flashcards
What is a node?
A single element in a data structure, typically with a value and a pointer to its parent.
What is a tree?
A hierarchical data structure of nodes with one root and no cycles; each node (except the root) has exactly one parent.
What is a forest?
A collection of disjoint trees; in Union-Find, it represents multiple disjoint sets.
How are trees used in Union-Find?
Each disjoint set is represented as a tree, with the root being the set’s representative.
How are forests used in Union-Find?
All disjoint sets together form a forest; each tree in the forest corresponds to one set.
What is the root of a tree in Union-Find?
The node that points to itself; it represents the entire set.
What does a node store in Union-Find?
Its value, a pointer to its parent, and optionally a rank (for balancing).
What does ‘no cycles’ mean in a tree?
It means there is no path that loops back to a previously visited node; paths always move toward the root.
What happens during UNION in terms of trees?
Two trees (sets) are merged into one by connecting one tree’s root under the other.
What happens to the forest when UNION is called?
The number of trees in the forest decreases, as sets are merged together.
