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.
-3
votes
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 ...
6
votes
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 ...
4
votes
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 ...
6
votes
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 ...
0
votes
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 ...
2
votes
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 ...
0
votes
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?
3
votes
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 ...
10
votes
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)$ ...
2
votes
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 ...
0
votes
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' ...
4
votes
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 ...
14
votes
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 ...
6
votes
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 ...
1
vote
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, ...
-4
votes
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 ...
11
votes
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.
12
votes
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 ...
8
votes
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 ...
-2
votes
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 ...
-3
votes
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 ...
0
votes
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?
5
votes
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 ...
2
votes
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?
...
4
votes
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 ...
9
votes
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 ...
4
votes
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 ...
11
votes
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 ...
15
votes
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 - ...
11
votes
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$).
...
15
votes
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 ...
5
votes
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 ...
6
votes
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. ...
5
votes
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 ...
8
votes
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. ...
17
votes
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 ...
10
votes
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 ...
8
votes
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 ...
6
votes
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 ...
2
votes
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 ...
4
votes
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 ...
26
votes
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 ...
10
votes
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 ...
-6
votes
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?
