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

learn more… | top users | synonyms

-4
votes
1answer
29 views

Constructing binary search tree from given data

The data are in alphabets. U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A. Perform pre, in and post order traversals. I'm confused as how to construct it in the 1st place. Only sense i ...
1
vote
1answer
41 views

Are there data structures that mix a tree structure with lists?

I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data. Something like this (I'll be ...
2
votes
0answers
99 views
+50

Large non-array data structure to describe order of elements

I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph ...
3
votes
0answers
51 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 ...
-1
votes
0answers
25 views

What's the time bound of an inorder traversal followed by a comparison?

I have the above question, and I plan on using an AVL tree to answer the question. The Insert(x) will be simple enough, simply using the default AVL tree insert. My question is for the $GreaterThan(x)...
2
votes
2answers
133 views

Computing maximum-cost subtree that uses at most k edges

I'm looking for an efficient algorithm for the following problem: Input: a binary, complete tree with a cost on each edge, an integer $k$ Output: the maximum-cost subtree containing $\le k$ edges ...
7
votes
1answer
190 views

Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
0
votes
1answer
22 views

Computing a subproduct tree

Consider the following description of a subproduct tree. We define a tree T for some points x[0] to x[n-1], and define m = log_2(n). Tree T is represented as a matrix where each row-column entry i, ...
2
votes
1answer
29 views

Perturbing trees

I have a collection of labelled directed trees, and from these input trees I would like to generate permuted trees that have the same node set but whose edges and labels have been permuted with some ...
1
vote
0answers
30 views

name perfect generalized sum tree with variable number children for each level

I was wondering if there is a name for the construct described below: Given $N$ integers $n_0, ..., n_{N-1}$ we construct a tree of height $N$ levels such that: each node of level $0$ (i.e the root)...
4
votes
0answers
39 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$...
1
vote
0answers
16 views

How to mitigate the hierarchical error propagation in tree-structured classification

Suppose we have a multi-class classification problem, where the number of classes $K \geq 3$ We use a tree structure of multiple SVMs to divide and conquer the problem, with one example in the figure ...
2
votes
1answer
41 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
47 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 ...
4
votes
0answers
22 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
1answer
23 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
36 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 ...
3
votes
1answer
229 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
132 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
91 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
66 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
31 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
102 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
49 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
40 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
47 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
94 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
53 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
61 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
45 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
51 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
77 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
61 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
19 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
101 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
45 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
47 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
34 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
70 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
54 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 \text{...
3
votes
2answers
125 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
2answers
117 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
77 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
122 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
22 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
67 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
129 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
52 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
71 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
40 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 ...