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.
108
questions
52
votes
20
answers
9k
views
NP-hard problems on trees
Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
- 10.6k
44
votes
4
answers
42k
views
Why would one ever use an Octree over a KD-tree?
I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar ...
- 857
27
votes
1
answer
725
views
Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
- 431
21
votes
2
answers
874
views
maintaining a balanced spanning tree of a growing undirected graph
I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.
I have an undirected graph that starts as a single node, the "root".
At each ...
- 341
20
votes
2
answers
10k
views
efficient diff algorithm for trees and Levenshtein distance
I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem.
Also, suppose that between ...
- 303
20
votes
1
answer
3k
views
Finding the distance between two polynomials (represented as trees)
A colleague who works on genetic programming asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy ...
- 16.5k
17
votes
3
answers
5k
views
Merging Two Binary Search Trees
I'm looking for an algorithm to merge two binary search trees of arbitrary size and range. The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into ...
- 273
15
votes
2
answers
3k
views
What is a zipper, and how does it relate to a tree-like structure?
I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers ...
- 151
15
votes
3
answers
556
views
Bob's Sale (reordering of pairs with constraints to minimize sum of products)
I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well.
Someone has already asked a question related to this problem here - ...
14
votes
4
answers
2k
views
Subrange of a Red and Black Tree
While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual ...
- 242
14
votes
4
answers
736
views
P-complete problems on trees
This question is related to one of my previous questions, NP-hard problems on trees.
I am looking for problems that are P-complete on trees.
- 10.6k
13
votes
0
answers
177
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 ...
- 369
13
votes
0
answers
533
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
13
votes
0
answers
374
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.1k
11
votes
1
answer
327
views
Minimum weight subforest of given cardinality
This question was motivated by a question asked on stackoverflow.
Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$).
...
- 1,855
10
votes
2
answers
1k
views
How do I choose a functional dictionary data structure?
I've read a bit about the following data structures:
Bagwell's Ideal Hash Tries
Larson's Dynamic hash tables
Red-Black trees
Patricia trees
...and I'm sure there are a lot of others out there. I've ...
- 397
10
votes
6
answers
834
views
A data structure for sets of trees.
Tries allow for efficient storage of lists of elements. The prefixes are shared so it is space efficient.
I am looking for a similar way to efficiently store trees. I would like to be able to check ...
- 803
10
votes
2
answers
540
views
Exact formula for the number of spanning trees of a rectangle
This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for ...
- 568
10
votes
1
answer
339
views
Lower bound on the number of "short" paths in a rooted tree with polynomial size
Let $T$ be a rooted binary tree. Every path from the root of $T$ to a leaf has length $n$. Every node of $T$ has always a left and a right child node but it is possible that they are the same (So ...
- 1,338
9
votes
2
answers
1k
views
What is the optimal data structure for a tree of maps.
I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a ...
- 93
9
votes
2
answers
8k
views
How can I find the second cheapest spanning tree?
The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead.
Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly ...
- 207
9
votes
2
answers
373
views
O(n)-space, polylog-time subtree sums in incremental forests?
Consider a forest $G$ of $n$ vertices $v_1, \dots, v_n$ arranged left to right with edges from child to parent always going to the left, i.e. if the parent of vertex $v_i$ is $v_j$, then $j < i$.
...
- 393
9
votes
2
answers
432
views
Efficient algorithms for searching a collection of trees
I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset.
Are there ...
8
votes
1
answer
696
views
Minimum degree of the "tree graph"
Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a ...
- 91
8
votes
2
answers
836
views
What is the initialization time of a link-cut tree?
Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
- 7,638
7
votes
3
answers
8k
views
Split or merge Binary Search Trees in O(log n)
We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following.
The element with the largest value in $S_1$ is smaller than the ...
7
votes
1
answer
280
views
How fast can we find and disconnect roots in a forest?
Consider a forest of rooted trees. The problem is to support two operations:
disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
findroot(v): find root of the tree ...
7
votes
1
answer
392
views
Complexity of "destroying" the graph's minimum spanning tree weight
Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$.
Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\...
- 9,438
7
votes
1
answer
380
views
For a given binary-search tree obtain an isomorphic splay tree
I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en....
- 1,310
7
votes
1
answer
447
views
Minimum Spanning tree on a complete "random" graph
Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)...
- 771
7
votes
1
answer
282
views
Inexact labelled binary tree matching
Does anyone recognise the following problems? Do they have names? Are they hard?
If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard ...
- 11.5k
7
votes
0
answers
279
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,733
7
votes
0
answers
199
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
6
votes
2
answers
540
views
Caterpillar decomposition of trees
Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ caterpillars? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the ...
- 1,591
6
votes
2
answers
2k
views
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission.
Popular Bloom filter instead of marking just 1 hash ...
- 325
6
votes
1
answer
530
views
Searching nodes in semi-splay tree
If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations.
My course also says that if you search for a node and the ...
- 227
6
votes
1
answer
251
views
Complexity of reachability in directed rooted forests
I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $...
- 133
6
votes
1
answer
343
views
Optimal Self Balancing Trees with Canonical Form?
Are any efficient [O(log n)] self balancing trees that are canonical? By canonical I mean that for any set of data inserted into the tree, inserting it after any permutation results in the same tree. ...
- 250
6
votes
1
answer
3k
views
How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?
I'm having a difficult time understanding Camerini's algorithm because there are very few clear explanations online. The goal is to find a minimum-bottleneck spanning tree in linear time.
Camerini's ...
- 163
6
votes
3
answers
474
views
Chomsky hierarchy for tree structures
I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.
Is there a similar hierarchy for ...
- 283
6
votes
1
answer
165
views
Example of context-free tree language which can not be generated by monadic CFTG
Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (...
- 635
6
votes
0
answers
345
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
5
votes
1
answer
97
views
If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?
The homeomorphic embedding relation for trees as I understand it is a well-quasi-order (wqo) on trees when the label of a node determines the number of children of that node, and there are a finite ...
- 615
5
votes
1
answer
587
views
Dynamic Tree Marked Ancestor Queries
Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it ...
- 173
5
votes
3
answers
410
views
Storage system for large quantities of unique key value pairs optimized for insert
Background
I'm in the process of attempting to improve part of our data storage and analysis architecture. Without getting into a lot of details, at a certain part of our data analysis process we ...
Troy Howard
5
votes
1
answer
148
views
Regarding proper form of production rules of Context-free tree grammars
Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?
$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\...
- 635
5
votes
1
answer
1k
views
Trees that structure partially ordered data
Suppose we have a binary search tree $T$ built over keys from a totally ordered set, and we want to support the standard dictionary lookup $\mbox{Find}(x)$ which returns a pointer to the node ...
- 1,327
5
votes
0
answers
162
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)$ ...
- 36.9k
5
votes
0
answers
161
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
5
votes
0
answers
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)$ ...
- 635