# Tagged Questions

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

13 views

### What's the intuition behind the update operation of the binary index tree? [duplicate]

There are many tutorials on binary index tree on the Internet, for the update operation, they all find the the next node of node i to update by ...
15 views

### FInding number of ancestors at given depth

I have a rooted tree with $n$ vertices. I want to be able to answer the given queries in logarithmic time after setting up some sort of data structure (preferably in time $n\log n$. The query is ...
83 views

### Time complexity of Depth First Search [on hold]

Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about. I ...
35 views

### What are the differences between parse and decision trees?

I have created a parse tree for the formula: a∧¬(b∨c)∨¬d∧(¬b) successfully. I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a ...
21 views

### Unsure about parse tree of PCFG

I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa. My solution would look like ...
36 views

### Are results after performing operations on AVL trees ambiguous?

After performing operations (e.g. insertion/deletion of a node - rotations) on an AVL tree, is the result fully determined by the order of insertion on the initial tree, or do multiple solutions ...
117 views

### Why hasn't functional programming researched dynamic trees?

By dynamic trees I am referring the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Since then, few efforts have been done in the functional programming ...
34 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 ...
44 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 ...
235 views

### 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 ...
55 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 ...
137 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 ...
191 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 ...
28 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, ...
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 ...
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)...
41 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$...
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 ...
42 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 ...
54 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 ...
24 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 ...
31 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 ...
43 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 ...
245 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" ...
146 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 ...
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, ...
78 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 ...
33 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 ...
115 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 ...
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 ...
41 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 ...
49 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 ...
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 ...
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 ...
68 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 ...
46 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 ...
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 ...
78 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 ...
68 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]$ ...
21 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 ...
116 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: ...
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 ...
48 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$ ...
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 ...
79 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 (...
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{...
134 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 ...
122 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 ...