# 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.

100 questions
Filter by
Sorted by
Tagged with
88 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 ...
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 ...
714 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.
255 views

### Extensions of Matrix-Tree Theorem

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) ...
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 ...
514 views

### minimum distance r-dominating set on tree

Given a graph G = (V,E) with edge and vertex weights. The minimum distance r-dominating set problem for a graph G = (V,E) requires to find a set S $\in$ V of smallest vertex-weight such that every ...
162 views

### Representation suitable for reconstruction of a tree with bounded degree

I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number ...
7k 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 ...
1k views

### Steiner tree problem for unweighted graphs

Steiner tree problem for weighted graphs is NP-hard. How about unweighted graphs? That is, given a graph $G=(V,E)$ and a subset $C$ of $V$, find a subtree of $G$ with the least number ...
97 views

### Has anyone ever mixed strings in a language with position?

Let the alphabet $\Sigma$ be extended to include $\bullet$, the concatenation point character. Define concatenation of such strings to be: (by example):  s\cdot t = (\omega \bullet \gamma ) \cdot ...
221 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?...
793 views

### Spell Checker with BK tree and edit distance that accounts for transpositions

I want to try and write code for a BK tree using a certain edit distance that accounts for transpositions for a spell corrector. I've looked into Damerau-Levenshtein distance, but the triangle ...
226 views

### A non-trivial combinatorial optimization

So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be ...
94 views

### Linear time algorithm for computing the labels of leaves in a recursively defined tree [closed]

The original copy of the question on MSE. Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows: The root has label $S$, for each ...
425 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 ...
375 views

### Multidimensional B+ tree

I've got an idea for indexing multidimensional data. I haven't been able to find anything equivalent and am wondering if it is indeed a novel approach. The idea is a 'stacked' B+ tree implementation ...
484 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 ...
9k 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 ...
5k views

### What is the advantage of red/black trees in comparison with unbalanced trees? [closed]

In which situations would I use a red/black tree instead of an unbalanced tree?
158 views

### Cubic (3-regular) graph spanning tree

Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes)： Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 ...
280 views

### Is there a characteristic function of a tree?

Consider a set of trees $T=\{T_{\alpha}\}$, and for any $T_{\alpha}\in T$, $T_{\alpha}$ has $n$ nodes. Can we find a ‘characteristic’ function $f:T\longmapsto{\mathbb{R}}$ describing trees' ...
346 views

### Does the order of insertion affect the topology of an R-Tree

Say I have 2 permutations of the the same set of elements. I create 2 R-Trees, one for each permutation. Do I end up with 2 structurally identical R-Trees or not? PS: My elements are rectangles on a ...
6k views

### unique binary tree from preorder and postorder traversals of a full binary tree [closed]

If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T. If so.. could ...
188 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 ...
524 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)$ ...
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 ...
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-...
33k 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 ...
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 ...
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 ...
1k 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:...
405 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 ...
562 views

### Remove specific edge from ST (link-cut) tree

ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time: CUT(v) Deletes the edge from v to its parent JOIN(v, w)...
797 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 ...
552 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 ...
473 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 ...
154 views

### Working with all leaves on a certain level of a b-tree

I want to work with a b-tree of any size. I want to do something with all leaves of the lowest depth $d$. Then if a certain condition holds, I want to recursively consider the same condition for the ...
266 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?
804 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 ...
329 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 ...
531 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 - ...
308 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$). ...
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 ...
492 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 ...
770 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 ...
326 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. ...
309 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 ...
332 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 ...
I need to specify small rooted trees with a lot of repeated parts and some recursive definitions. To illustrate the need, let's use $s(T_1, T_2, ..., T_k)$ to denote a tree that consists of a degree-\$...