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

learn more… | top users | synonyms

0
votes
0answers
9 views

How to construct a running kd-tree?

I have a stream of 3-tuples of type (x,y,t) where x and y are in the range ...
1
vote
0answers
27 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 ...
3
votes
0answers
11 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 ...
0
votes
0answers
7 views

Should all internal node keys in B+ tree also be in the leaves?

I was reading about B+ tree insertion. The algorithm takes following form: Insert the new node as the leaf node. If the leaf node overflows, split the node and copy the middle element to the ...
0
votes
1answer
29 views

Facts about internal and external path lengths of binary tree

While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some ...
1
vote
0answers
126 views

What is the difference between a R-tree and a BVH?

I've just read about R-Trees: The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" ...
6
votes
1answer
105 views

What are the applications of Rose trees?

I recently found out about the Rose tree data structure, but just going off of a Haskell data definition and the tiny Wikipedia description of it, I've got some ...
-1
votes
3answers
89 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
3
votes
0answers
48 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 ...
1
vote
1answer
24 views

Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
3
votes
1answer
80 views

How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...
0
votes
2answers
43 views

Induced subgraph problem in trees

Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u_1, v_1), \dots, (u_n, v_n)$. I need to construct a smallest subgraph of original tree such that for ...
5
votes
0answers
34 views

Coercing a list of nodes into the most probable tree

Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document ...
6
votes
2answers
44 views

A key-value datastructure with fast (on average) member move and nearest neighbors search?

I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
10
votes
1answer
92 views

What is the chance that this code terminates?

I wrote this Python code, and wondered if it sometimes simply doesn't terminate (assuming we had infinite memory/time and no recursion depth limit). Intuitively you'd think it terminates, since at ...
1
vote
1answer
47 views

Question on the properties of red black trees

Problem statement Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the ...
3
votes
1answer
42 views

Binary Search Tree Traversal output validity and unique BST construction

I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals : Given x-order traversal output of BST, can we state if it is valid or invalid output? (For ...
0
votes
1answer
42 views

Checking whether a node is expandable

I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable. A node is said to be expandable ...
4
votes
1answer
45 views

UCT1 Algorithm: What does “total number of simulations” mean?

When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula. $$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$ Wikipedia, this guy, and this guy all ...
5
votes
0answers
74 views

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

I'm considering the following problem. Consider a Directed Acyclic Graph. In general, there would be some number of subgraphs that, collapsed into one node, would make it a tree. For example, in this ...
5
votes
1answer
44 views

Persistent random-access queue

I need a queue $[x_0, ..., x_n]$ that supports the following operations: $\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$ $\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$ ...
-1
votes
1answer
16 views

Which tree decomposition of a graph is preferrable?

In this page, there are two examples of tree decomposition of a graph $G$. Could there be another decomposition such as: $\{A,B\}, \{C,E,F\}, \{D,F,G\}$ or did I get the rules of decomposition ...
-2
votes
1answer
73 views

Is a balanced binary tree a complete binary tree?

Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees. All I know is this: ...
2
votes
1answer
44 views

How do I go about constructing a game tree that does not duplicate any states?

Many games have states that can be reached via multiple paths in their gametree. For concreteness, consider the game of tinychess (with the obvious(I hope) rules inherited from chess), which looks ...
1
vote
1answer
44 views

Check if a tree is formed by 3 subtrees with given number of nodes

I have run into a contest problem (ACM like) that sounds like this: Input: a tree of $N$ nodes; integers $X,Y,Z$ such that $X+Y+Z=N$ Question: Can the tree be partitioned into three trees of $X,Y,Z$ ...
0
votes
1answer
32 views

Total number of calls during insertion into binary tree

The problem: Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree ...
1
vote
1answer
55 views

How do multiple branches from one node occur with the Monte Carlo Tree Search?

I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes ...
7
votes
1answer
53 views

Proving that a (tree) language is not Buchi recognizable

I'm reviewing some notes about tree automata and I'm trying to conclude a proof that the professor left incomplete. The statement is: Let $A = \{a,b\}$ and $T = \{t \in T_A^{\omega} \mid ...
3
votes
2answers
81 views

Minimax algorithm when all the options are the same

tl;dr What does the Minimax algorithm do when all its options are the same? Consider this Minimax tree: (Green means the ends, orange minimize, blue maximize) (Source: Myself) Imagine this is the ...
0
votes
1answer
95 views

Countability of a binary tree

Problem: We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable. My attempt: A set is countable if it is ...
2
votes
1answer
72 views

Variation on Bellman-Ford Algorithms?

We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this ...
4
votes
1answer
116 views

Huffman Coding and Depth Calculation?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ...
1
vote
1answer
20 views

(a,b)-tree vs B-tree

I would like to know what are the differences between (a,b)-tree and a B-tree. It has been a few days I am studying different papers and I am seeing different definitions that make me confused. For ...
4
votes
1answer
66 views

A Shortest Path Strange Formulation, or new modeling?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. For ...
1
vote
1answer
62 views

How do I find the number of inversions using a red black tree?

I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node ...
1
vote
0answers
50 views

Minimize the depth of a tree of computation

Assume you have a binary tree of additions, where each two nodes are added together until the root is the sum of all the nodes. For example: ...
2
votes
1answer
63 views

Connecting an unconnected forest of subtrees in a graph?

If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other. What is the best way to connect these three trees such that ...
4
votes
1answer
39 views

Expected number of common edges for a given tree with any other tree

So I am working on a problem where I have a set of (labeled) nodes and I have a tree structure (rooted) over that set of nodes. The goal for me is to automatically generate that tree structure. To ...
2
votes
1answer
88 views

Algorithm to find the shortest walk with k leaf nodes on a tree

Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root? Passing through a ...
3
votes
1answer
40 views

Is it possible to use a copy-on-write strategy to modify a B+ tree?

Alright, I'm not sure if this is more of a stack overflow question, but I'm going to try here because you folks seem more suited. CouchDB makes an interesting claim about using an "append only" B+ ...
0
votes
0answers
22 views

Joining k 2-3 trees

I was given the following question, and would like your help with it: Let $T_1, T_2, T_3, ..., T_k$ be a collection of k 2-3 trees. The height of tree $T_i$ is marked $h_i$. Assumptions: 1) every key ...
11
votes
5answers
1k views

What is the earliest use of “trees” in computer science?

I have a little history question, namely, as the title says, I am looking for early uses of trees (as a data structure, search tree, whatever) in computer science.
1
vote
1answer
89 views

Update labels of a tree depending on ancestors of nodes in linear time

You are given a tree $T=(V,E)$ along with a designated root node $r \in V$.The parent of any node $v \ne r$, denoted $p(v)$, is defined to be the node adjacent to $v$ in the path from $r$ to $v$. ...
0
votes
1answer
41 views

Two red children in a red-black tree

My data structures exam contains the following question: Which of the statements below about red-black trees is true? (select one or more) Every path from the root to a leaf has the same ...
0
votes
0answers
25 views

two connected graph - find linear spanning subgrap such that subgraph is still connected

Graph $G$ is 2-connected. It means that for each two edges there are exists at least to disjont (in terms of edges) paths. Graph $G$ is not directed. Our task is to find spanning subgraph $H$ of ...
1
vote
0answers
53 views

How to formalize a tree problem?

Considering a network of $n$ IT centers $1,...,n$ we can connect by lines which heve different characteristics. Among these charateristics, we take an interrest in the reliability of a line. Thus, ...
0
votes
2answers
19 views

Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?

I am studying the algorithm of Sollin and we recently studied a lemma: Let be G a graph which values are diffferent on the edges. We sort the edges $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$ ...
0
votes
2answers
123 views

non-binary self balancing tree

I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible). I mean, suppose a tree where: each node has a parameter k that is the maximum number ...
5
votes
2answers
77 views

Help with proof involving weighted full binary tree

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the ...
1
vote
1answer
42 views

What is the difference between regular trees and phylogenetic trees in terms of graph theory?

If I am not mistaken, a tree is any graph that does not contain cycles. However, I am currently taking a bioinformatics course where we deal a lot with algorithms on phylogenetic trees. Usually you ...