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

112 questions
Filter by
Sorted by
Tagged with
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
43k 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
727 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
881 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 ...
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
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
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
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
557 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 - ...
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 ...
740 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
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.1k
329 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
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
842 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
546 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
342 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
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
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
380 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
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 ...
708 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
840 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,648
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 ...
282 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 ...
393 views

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
94 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
282 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
551 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
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
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
260 views

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
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.3k
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 ...