# Questions tagged [tree]

A tree is a special type of graph which only allows for a hierarchical set of edges similar to a tree . Mathematically it is actually an arborescence. Trees have a root node and children nodes. In formal terms it is described as an acyclic connected graph.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
178 views

### What is the curve of "search vs. insert"

Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time. With this ...
534 views

### Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
• 566
375 views

### Applications of an access lemma for dynamic forests?

Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum ...
• 23.2k
99 views

### Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
• 181
285 views

### Number of ordinal trees with n nodes, of depth d, with l leaves

What is the number of ordinal trees (aka rose trees) with $n$ nodes, of depth $d$, with $l$ leaves? I thought that it was a known results but I could not find it, and neither did the various ...
• 2,776
200 views

### Tree search guided by a probabilistic oracle

I'm trying to find a solution for the following problem. I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be ...
• 249
362 views

### Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
• 679
166 views

### Complexity of a problem related to Friedman's TREE(k) function?

Background Given two rooted, vertex-colored trees $T_1, T_2$, $T_1$ is color-preserving inf-embeddle in $T_2$, which we'll denote $T_1 \leq T_2$, if there is an injective $f \colon V(T_1) \to V(T_2)$ ...
• 37.4k
166 views

### Height of AVL tree with random elements

I know that for an AVL tree of N nodes, the depth of the tree is bounded by $$\log_2(N + 1) -1 \leq height \leq c \log_2(N + 2) + b$$ where $c,b$ are taken from the golden ratio linked to the worst ...
• 171
163 views

### "Context" understanding in tree grammars

The Context-Free tree grammar has rules of the form: $A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$, where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ ...
317 views

### Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$. I'm now searching for an intuitive, or geometric, or visual proof of ...
• 281
170 views

### What is the exact communication complexity of subtree disjointness?

A classic textbook example for communication complexity is when A and B both receive a subtree of a an $n$-node tree (that they both know), and they need to output whether their subtrees are disjoint ...
• 14k
215 views

### Find a pair of nodes with maximum sum of distances in k given trees

For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
• 235
2k views

### Given a B-Tree, determine the order keys were inserted

Given a B-tree, determine what order the keys were inserted in. There may be multiple answers: I'd like to generate them all. Is there any known method for this? Or similar problems? Clarification:...
• 171
75 views

### Load-balancing; Alternate methods of keeping track of nodes?

Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network. One popular method uses virtual-...
• 131
38 views

### Homeomorphic subtree extraction in integer sorting time

Background Given a rooted, binary tree $T$ with leaves bijectively labeled by $\{1, \ldots, n\}$ (a "phylogenetic tree"). Let $L \subseteq \{1, \ldots, n\}$, and $|L| = k$. The homeomorphic ...
54 views

### The number of rooted ordered trees of max-out degree $k$

An ordered tree (also known as ordinal tree and plane tree) is a rooted tree in which the children of each node are ordered. It is known that the number of the ordered tree with $n$ edges is the $n$'...
74 views

### Regular Tree Languages are closed under quotient?

The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees,...
• 2,942
122 views

### How to find a merge tree for a set of words?

Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider ...
• 1,292
226 views

### Quadratic Binary Optimization formulation of Steiner Tree problem

can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization problem?...
431 views

1 vote
287 views

### Maximize the weight of MST + sum of vertex weights

I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is ...
• 19
1 vote
90 views

### Are there any polynomial cases of Balanced Minimum Evolution?

The BME problem has an interest in computational biology, for the reconstruction of phylogenetic trees from a distance matrix. Let me provide some context before defining the problem. Suppose that we ...
• 324
1 vote
58 views

### Repartitioning a binary tree

Suppose I have a binary tree $G = (V, E)$ (with undirected edges) that is partitioned into sets of k vertices, where each set of vertices is a connected subgraph of $G$. Additionally, if there are ...
• 393
1 vote
296 views

### How to quantify the tree-like-ness of a graph?

What are good measures of tree-like-ness of a graph and algorithms for calculating them?
• 119
36 views

### Why LOUDS is considered succinct coding?

LOUDS encoding is widely cited as succinct, e.g., in the papers, in Github repos, etc. It is straightforward that LOUDS takes 2n bits for encoding an ordered tree ...
• 113
69 views

### What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
• 228
65 views

### Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
• 228
116 views

### Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and edge disjoint $a_i$-$r$ paths $P_i$ for each $i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ ...
• 228
66 views

### Suffix tree and searching for longest subword that appears two times and two occurencies are not overlapping

I'm learning basics of text algorithms, so my question might seem simple. Let's have word $S$, i want to find longest subword $x$ such that it appears in $S$ two times and those two occurencies are ...
242 views

### Steiner Tree and minimum spanning tree

If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
• 11
75 views

### On a property of random rooted trees with $n$ nodes and of height $h$

I am working on a proof that require the result of the following problem: Let, $T$ be a rooted directed tree with height $h (\ge \lceil{log_d{n}}\rceil )$ and having $n$ nodes. Each internal node of \$...
• 101