Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
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. ...
0
votes
1answer
84 views

What is the error when using Levenshtein distance on flattened binary trees?

I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive. The trees are stored as a flattened list of indices into node and terminal ...
0
votes
1answer
229 views

Fenwick Tree Traversal using Binary value of Index

Can someone explain me how do I execute sum query from Index 0 to Index I given the binary value of that Index I. There are some trivial question that I want to know : Do we have to remove last set ...
2
votes
4answers
2k views

Why is the running time for BFS $O(b^{d+1})$?

In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as ...
1
vote
1answer
489 views

Ternary decision tree for the lower bound of comparison sort with 3-way comparisons

All the proofs I've seen about the Ω(nlgn) lower-bound for comparison sorts use binary decision tress like this (from CLRS textbook) Now what if each comparison yields strictly 3 outcomes, i.e. ...
0
votes
1answer
112 views

Creating a decision tree?

So I'm trying to split on an attribute "Color" that has possible values (Blue,Green,Red,Orange,Pink). I'm splitting on entropy values, and the best split can either be Multi-Way 5, Multi-Way 4, ...
4
votes
1answer
297 views

Can a shortest-path tree be a also maximum spanning tree?

If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example! I ...
3
votes
2answers
405 views

Relationship between height and depth of a binary tree

The wikipedia says that the number of nodes n in a full binary tree, is at least $n=2^h-1$ and at most $n=2^{h+1}-1$, where h is the height of the tree. The following binary tree is full according to ...
1
vote
1answer
191 views

Comparison of Decision Trees: RTED vs MLE

I read two papers discussing how to compare between decision trees. One of them is RTED (that is specifically for trees and sub-case is decision trees) can be found here (RTED: A Robust Algorithm for ...
0
votes
2answers
1k views

Extract Tree from multi-edge undirected graph

I have the following multi-edge, undirected graph. I would like to extract the following tree from it, if I start from the node $A$. Do you know of any algorithm that I can use to achieve that ? ...
30
votes
2answers
17k views

What is the difference between radix trees and Patricia tries?

I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a ...
0
votes
2answers
189 views

Get mathematical relation of node IDs of a subtree based on a given tree

(I was not really sure in which "stackexchange" I should put this question. I hope CS is ok.) Let's say I have the following tree A. Every node has a unique ID, which will be counted up, beginning ...
3
votes
1answer
44 views

Sum of size of distinct set of descendants $d$ distance from a node $u$, over all $u$ and $d$ is $\mathcal{O}(n\sqrt{n})$

Let's consider a rooted tree $T$ of $n$ nodes. For any node $u$ of the tree, define $L(u,d)$ to be the list of descendants of $u$ that are distance $d$ away from $u$. Let $|L(u,d)|$ denote the number ...
1
vote
0answers
97 views

Why the update low value in Tarjan's for the ancestors is not it's low value instead of it's discovery value? [closed]

In Tarjan's algorithm for finding SCC/AP/Bridges, we update the value of the low[u] to be the min ( low[u], desc[v] ) given that v is a neighbor and has been discovered before, why it's not like this ...
1
vote
1answer
244 views

Distance query in trees with integer edge weights (Constant time, linear space)

Consider an unrooted tree with integer edge weights. I'm looking for a linear space data structure which allows for constant time distance queries (finding the distance, i.e. the sum of edge weights, ...
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?
0
votes
1answer
150 views

AVL Tree Height

What is the height of an AVL Tree? I keep finding contradicting definitions. I found these two on wiki: Height of node: The height of a node is the number of edges on the longest path between that ...
1
vote
1answer
52 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 ...
7
votes
1answer
20k views

Time complexity of Depth First Search [closed]

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 ...
1
vote
1answer
267 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 ...
0
votes
1answer
32 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 ...
1
vote
1answer
50 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 ...
18
votes
1answer
704 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 ...
-3
votes
1answer
3k 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
78 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 ...
1
vote
0answers
258 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 ...
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 ...
2
votes
2answers
2k 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
777 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
129 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
55 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
44 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
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$...
1
vote
0answers
62 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 ...
3
votes
1answer
172 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 ...
2
votes
1answer
551 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
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 ...
1
vote
1answer
743 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 ...
1
vote
1answer
2k 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 ...
5
votes
1answer
1k 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" in ...
8
votes
1answer
2k 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
127 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
728 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
112 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
7k 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
152 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
1answer
85 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
108 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
115 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 ...
2
votes
1answer
406 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 ...