Cecilia R. Aragon 2026-11-05
Cecilia R. Aragon coauthored the randomized search-tree construction with Raimund Seidel. Their treap combines binary search tree order on keys with heap order on random priorities. A key set and distinct priorities determine the tree; independent random priorities give expected logarithmic search and update costs. The analysis separates expected cost from the possibly linear height of a particular realization.[ref]
The construction makes balancing probabilistic without storing the explicit balance conditions used by AVL trees. Operations that split or join a tree preserve the two orderings, making the idea useful for both ordered dictionaries and sequence data structures.
Fibonacci heap 2026-11-05
A Fibonacci heap implements a meldable priority queue using a collection of heap-ordered trees and a pointer to a minimum. Insertion and melding defer consolidation. Removing the minimum promotes its children and repeatedly links roots with equal numbers of children, keeping the smaller key above the larger. Decreasing a key cuts a violating node; mark bits and cascading cuts control how much child loss a retained node may accumulate.
The potential method charges stored work using the number of tree roots plus twice the number of marked nodes. It yields constant amortized cost for insertion, melding and decrease-key, and for removing the minimum. These are sequence guarantees, not worst-case bounds for each operation. A node with children has at least a Fibonacci-sized subtree, bounding logarithmically in total heap size. The inexpensive decrease-key operation improves Dijkstra's algorithm to with adjacency lists.[ref]
False. In a Prüfer code, the degree of a label is one plus its number of occurrences. Here labels occur once and labels do not occur. Thus the former have degree two and the latter degree one. The decoded tree is the path
with the evident single-edge interpretation when . Independently, no vertex of a simple tree on vertices can have degree at all. The degree claim in the statement is therefore impossible.
True. Choose a root of the tree and color every vertex according to the parity of its graph distance from that root. The unique-path property implies that the endpoints of each edge have distances differing by one. Thus every edge crosses the two color classes, proving bipartite graph.
False. The four-cycle is bipartite, with alternating color classes, but contains a cycle and therefore is not a tree.
True. Each connected component of a forest is a tree. If the component sizes are , their edge counts are , including isolated vertices as size-one components. Summing gives , hence
Raimund Seidel 2026-11-05
Raimund Seidel coauthored Randomized Search Trees by Raimund Seidel and Cecilia R. Aragon with Cecilia R. Aragon. The paper analyzes search trees whose shape is governed by random priorities. Combining binary search tree order and heap order gives the treap, supporting searches, updates and split/join operations with expected bounds.[ref]
The key idea is to analyze the distribution of the whole tree instead of enforcing a fixed local balance ratio after every update. For example, the item with highest priority becomes the root, and the same construction applies recursively to the smaller and larger keys. This turns priority independence into an analyzable balancing mechanism.
Rational tree 2026-11-05
A rational tree is a possibly infinite tree with only finitely many distinct rooted subtrees. It therefore has a finite representation as a term graph, possibly with cycles. Here “rational” describes finite representability, not values in the rational numbers.
For example, the equation describes the infinite expression . A single node labeled with an edge back to itself represents it. There is no solution among finite first-order terms: the occurs check rejects binding a variable to a first-order term containing that variable. Unification over rational trees instead admits this cyclic representation, so implementations must specify which semantics they use. SWI-Prolog explicitly supports cyclic terms for many term operations.[ref]