# Tagged Questions

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 a acyclic connected graph.

0answers
51 views

### How many Trees are Possible? [closed]

We are given Two Integers P and Q. We have to find how many different T-Trees are possible. Definition of T-Tree It is a tree with Q * P Nodes. Nodes are Numbered from 0 to Q * P - 1 The Nodes a ...
2answers
192 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 ...
1answer
219 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 ...
1answer
259 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 ...
1answer
101 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 ...
1answer
158 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 ...
0answers
153 views

### Is there a typo in this paper? [closed]

I'm studying Andrew W. Moore's tutorial on Kd-Trees. On page 6-7 there is a formular (6.6) and I wonder if there is an error in it. Shouldn't there be hri^max in the bottom case?
0answers
109 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 ...
0answers
259 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)$ ...
0answers
63 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 ...
1answer
223 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' ...
1answer
253 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 ...
3answers
1k 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 ...
2answers
1k 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 ...
1answer
209 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, ...
1answer
2k 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 ...
2answers
355 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.
4answers
3k 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 ...
1answer
266 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 ...
1answer
90 views

### Is this the right strategy to convert an in-level order binary tree to a doubly linked list? [closed]

So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question. This is the strategy I ...
3answers
121 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 ...
0answers
174 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?
0answers
270 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 ...
1answer
390 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? ...
3answers
168 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 ...
6answers
597 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 ...
1answer
284 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 ...
0answers
180 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 ...
3answers
408 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 - ...
1answer
225 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$). ...
2answers
773 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 ...
1answer
230 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 ...
1answer
228 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. ...
0answers
287 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 ...
2answers
620 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. ...
2answers
445 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 ...
1answer
269 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 ...
2answers
416 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 ...
2answers
433 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 ...
0answers
256 views

### Notation for drawing rooted trees with isomorphic subtrees and recursive parts

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 ...
3answers
2k 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 ...
11answers
2k 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 ...
4answers
1k 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 ...
1answer
1k 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?
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 42, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9333709478378296, "perplexity_flag": "middle"}