Questions tagged [trees]

Questions about a special kind of graphs, namely connected and cycle-free ones.

154 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
38
votes
0answers
1k 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 ...
18
votes
1answer
703 views

Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
16
votes
0answers
312 views

Is finding a weight-balanced tree NP-hard?

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and ...
8
votes
0answers
140 views

What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?

Lets consider two node-labeled rooted trees Q and D. According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
5
votes
1answer
337 views

What is the minimum required storage for a sparse, depth-first octree?

For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree ...
5
votes
0answers
368 views

What are these tree transformations called?

I want to transform a general rooted, node-labeled tree into a related binary tree. I came up with four different schemes ("left shallow", "right shallow", "left deep" and "right deep" binarization) ...
5
votes
0answers
134 views

Assignment of coprime values to a tree

I recently saw this question somewhere and thought a lot on it but was unable to find an efficient solution for it. Asked on Stack Overflow but got no solution there. The Problem is as follows - ...
5
votes
0answers
128 views

Has this graph-theoretic problem got a known name? Is it NP-hard?

I am considering the following problem. We are given a Directed Acyclic Graph. In general, there would be some number of subgraphs that, contracted into one node, would make it a tree. For example, ...
5
votes
0answers
285 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
4
votes
0answers
41 views

How do 2-3 FingerTrees generalize to bigger branching factors?

FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
4
votes
0answers
53 views

Repeated nearest-neighbor queries

If I want to make N repeated (i.e. millions of) 2D nearest-neighbor queries on a pointset of size M, is traveling down into a KD-Tree most efficient or are there better ways to do this? (e.g. Voronoi?)...
4
votes
0answers
147 views

Weak equivalent tree grammar for Context-sensitive word grammar?

Consider arbitrary context-sensitive grammar on strings $G_s$. Is any known and described formalism (or type) for tree grammars, using which we can build weak-equivalent tree grammar $G_t$, which ...
4
votes
0answers
136 views

Data structure for a Rete in production rule system

Example of Data This is the data for one monkey. There are many similar but different monkeys. ...
4
votes
0answers
2k views

Maximizing pruned branches in an alpha-beta tree

Preliminary After doing some searches of similar questions posted here and elsewhere, i feel like this is the right place to inquire about, now let's get through some boring main notations... A ...
4
votes
0answers
129 views

MST that contains a shortest $s,t$-path

Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$...
4
votes
0answers
230 views

Minimal Steiner Tree in unweighted directed graph

I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
4
votes
0answers
525 views

Why does a first-child-next-sibling tree implementation have parent pointers?

Below is the code, ...
3
votes
0answers
39 views

Tree Automata Operators

I am trying to understand the Projection operation (linear tree homomorphism) and Cylindrification operation (inverse tree homomorphism) from the book. Linear Tree homomorphism is defined as follows: ...
3
votes
1answer
99 views

minimum and maximum nodes of MultiWay tree of height h

I know that it doesn’t have to be balanced so in theory given that the height of the tree is $h$, the minimal number of nodes is obtained when each node has 1 key and 1 child, and since the first ...
3
votes
0answers
338 views

How can we describe the similarity between trees?

For example, I have a program generates two ASTs, and I want to compare the two trees. I've tried to treat the trees as graphs, but I think it doesn't show the particularity of trees.
3
votes
0answers
864 views

Lowest single common ancestor in a Directed Acyclic Graph?

I was reading how to find the Lowest common ancestor in a DAG. A DAG can have scenarios where the LCA yields multiple solutions and I feel the accepted answer explains that pretty well. However, one ...
3
votes
0answers
350 views

B+tree implementation using single file on disk

I'm studying B+trees and I'm trying to understand how actual data can be stored in a physical file and still allow fast lookups. None of it would be in memory, all of the pointers would be "seeks" to ...
3
votes
0answers
1k views

What is the Big-Oh asymptotic complexity of learning in Random Forests?

Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right. CART (Classification and Regression Trees) uses the Gini index for ...
3
votes
0answers
726 views

Tree of Despair: Collecting Data from a Tree with Multiple Types of Branching

Provided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent. The objective of the ...
3
votes
0answers
74 views

What is the intuition behind the “edit sensitive parsing” tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...
3
votes
0answers
193 views

How to apply path compression to Multi-Bit Trie

Reading a bit about the subject of Multi-Bit tries and IP matching in: High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33 Network Routing: Algorithms, Protocols, and ...
3
votes
1answer
601 views

what is the name for the space between the leaves of a tree

I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree. In number theory (a part of math) this is known as a topograph does it have a name in CS?
2
votes
0answers
16 views

Nested dissection vs kd-tree

Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
2
votes
0answers
100 views

Join Order Optimization

Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? Based on the schema on the following picture: I am suppoused (and that's what I tried) to use ...
2
votes
0answers
26 views

Construct a lambda term from a Böhm tree

Given an acyclic graph, how can I build a lambda calculus term such that this graph is the term's Böhm tree? If the Böhm tree is a finite tree (so the result is a strongly normalizing term). If the ...
2
votes
0answers
33 views

Documentation of “bin number” trees

TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
2
votes
0answers
107 views

Algorithm to find nodes with given a distance

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
2
votes
0answers
195 views

Semi-automatic layout algorithms for a mind map

There're some existing tree layout algorithms such as Tidier Drawings of Trees and Drawing Non-layered Tidy Trees in Linear Time. I call them as automatic layout algorithms since positions of nodes ...
2
votes
0answers
144 views

K-ary tree that wrapped around

I'm not sure the best way to name this problem, but basically I need to construct a complete $k$-ary tree for $k \geq 2$ which has this nice property as $k=1$ tree that we can create a ring out of it. ...
2
votes
0answers
54 views

stacks in tree constructions

There are two nice tree constructions, that use a stack in a similar manner: Construct a binary search tree from a pre-order traversal (e.g. see http://www.geeksforgeeks.org/construct-bst-from-given-...
2
votes
0answers
69 views

How to cut a full binary tree evenly

Given a full binary tree of size $n$, I need to cut the tree into two by choosing an edge and removing it. I want the cutting to be as equal as possible (i.e. the two subtrees have as equal weight as ...
2
votes
0answers
18 views

How to avoid empty spots when inserting in a B+tree

When you insert a new item in a B+tree leaf node, and the node is full, two new nodes are created and they're both filled halfway and the values get re-distributed accordingly. Before the insertion: ...
2
votes
0answers
108 views

Coloring of a K-ary tree using minimum paint Buckets

I was recently asked this problem in an interview and I couldn't solve it. Need some help on how to solve this problem. Given a K-ary tree with N nodes (N <= 2000 and K <= 12) you need to ...
2
votes
0answers
76 views

Counting inversions with index constraint

I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$ $a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis. The question is how to find a algorithm that is ...
2
votes
0answers
447 views

Minimum cost edge in path between nodes (tree)

I'm working on a problem and I've managed to design an efficient algorithm, but I'm stuck at the last part. After some processing I'm left with a tree and I have to answer several queries of the ...
2
votes
1answer
550 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2
votes
0answers
54 views

Two flavors of red-black trees with different performance

I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors: 1) In the first tree, all the data is stored in the leaves. 2) In the second tree, the data is ...
2
votes
0answers
70 views

Which component sizes do we observe while randomly deconstructing a tree?

Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the ...
1
vote
1answer
33 views

How to merge a lot of trees into one single graph?

I have a few different trees, which resemble what the AST that compilers often deal with. For example: tree 1 ( (a, b), (c, d) ) Imagine that each tree split represents the function "add", then ...
1
vote
1answer
20 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
1
vote
1answer
49 views

Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
1
vote
0answers
50 views

Given a tree find path that maximizes the median of the costs of edges

We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path ...
1
vote
1answer
111 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
1
vote
0answers
31 views

How do I implement fixed block storage file system in database from typical file-level file system?

I've a typical parent ID based file system in database and files are physically stored on disks. What I want is to store files in blocks (4096K) of fixed size. Chunking can be used I found, but how ...
1
vote
0answers
32 views

Searching Algorithm on Connected Graph

This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math. Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...