Tree Data Structures & Algorithms

← Back to Domain-Specific Families

Abstractions about recursive and spatial trees, rotations, ancestor queries, traversal methods, pointer analysis, and abstract tree representations.

9 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Aronszajn tree — A tree of height ω₁ whose levels and branches are all countable, generalized to κ-trees with levels and branches smaller than κ.
• Euler tour technique — A tree representation that replaces each undirected edge with two directed arcs and linearizes the resulting Euler tour for efficient queries and updates.
• Exponential tree — A search-tree structure whose branching factors shrink doubly exponentially with depth, storing keys at leaves and auxiliary predecessor structures at internal nodes.
• Level ancestor problem — A rooted-tree query problem asking for a node’s ancestor at a specified depth after preprocessing the tree.
• Quadtree — A hierarchical spatial data structure whose internal nodes recursively divide a two-dimensional region into four child regions.
• Recursive tree — A rooted labeled non-plane tree whose labels increase strictly along every path away from the root, often generated by attaching each new label to an earlier vertex.
• Steensgaard's algorithm — A near-linear, flow-insensitive pointer analysis that models assignments as equality constraints and merges points-to equivalence classes with union–find.
• Tree (abstract data type) — A hierarchical abstract data type of nodes linked by parent–child relations, with one root and a unique parent for every other node.
• Tree rotation — A local binary-tree restructuring that preserves in-order key order while changing parent-child shape.