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

learn more… | top users | synonyms

2
votes
1answer
31 views

How append, prepend, and generally insertAt work in RRB-tree

I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient ...
0
votes
1answer
28 views

Depth of any node x in Weighted Quick-Union Algorithm

I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall ...
4
votes
0answers
53 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
1answer
83 views

Shortest-depth routing algorithm

This problem came up in a graph network routing context, it can be expressed as follows: Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k ...
0
votes
2answers
64 views

Maximum length path between any two nodes in a tree with possible negative edge weights

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a ...
1
vote
1answer
31 views

Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

This question is related to my previous question: Looking for a set implementation with small memory footprint I'm looking for information about combined data structures, which can efficiently ...
1
vote
1answer
185 views

Checking whether two paths are intersecting in a tree

The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint ...
3
votes
2answers
90 views

Are there any CS-trees named after flora-trees?

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real ...
-1
votes
1answer
48 views

Number of Different AVL Tree

I studying the related question. http://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node but it's not so general. In-fact, We want to know ...
-1
votes
1answer
156 views

Sum of all nodes from A to B in a Tree [closed]

Given a Tree and pointers to two of it's nodes A and B (a key value of each node is positive). Find an algorithm that sums up all the values on the path between A and B, when preproccessing is ...
3
votes
2answers
55 views

How do learn the most important nodes in a tree?

I have a list of 20000 words and how often they appeared in a set of 500 newspaper articles. I am trying to build a stemmer which chops off suffuxes from each words, so ...
0
votes
2answers
52 views

Reason for differences between ways of specifying trees

Might be an odd question but how is it that when you specify a tree using an adjacency list emphasizing leafs first you state only need state 0 or 1 parent for each node but when you define a tree in ...
0
votes
1answer
46 views

Red black tree partition to $\sqrt{n}$ trees

This is a question I have stumbled upon in an old Algorithms test I found online: A) Plan an algorithm that does the following: Input: Red-Black tree Output: $\sqrt{n}$ seperate trees, so that ...
-1
votes
1answer
32 views

Find MST based upon new definition

Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the ...
-2
votes
1answer
58 views

Automata Theory Questions: Rule Trees, Context-Free Grammar, Proving Ambiguity [closed]

I'm currently taking a class in Automata Theory and it's kicking my butt. I have an assignment that my teacher gave me that consists of three questions. I have no idea where to start. My teacher and I ...
-1
votes
1answer
46 views

Find a maximal subgraph on a tree with conditions

Given a tree, find a path on which every vertex has at most 4 leaves (can have 0 as well) and is the "biggest" (has the maximum amount of vertices possible - including the leaves). Time complexity: ...
1
vote
2answers
90 views

Tree data structure for fast merges [closed]

I need trees that have the following properties: Each node in the tree has two values associated with it - a key and an associated opaque data element. An internal node in the tree has unbounded ...
0
votes
0answers
18 views

Balanced multi-criteria trees

We have an n-ary tree used for searching that we'd like to keep balanced. It is currently mostly a B-tree without the balancing operations. The issue we have for implementing those is that each ...
3
votes
1answer
43 views

What is the common terminology to refer to the nth ancestor of a tree root?

Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a ...
0
votes
1answer
124 views

Find largest chromatic number of a full binary tree [closed]

This is a Discrete Math/Combinatorics Question from my hw…but I don't really understand the question. Find largest chromatic number of a full binary tree given the following depths: (Check all ...
2
votes
1answer
41 views

Merge-by-weight to solve reachability problems in trees and DAGs

Let $T = (V, E)$ be a tree with a designated root $r \in V$. The fact that the tree is rooted allows us to speak of "subtrees of $T$ rooted at some node $x \in V$". Let's say we have a (not ...
5
votes
1answer
177 views

What is the expected number of nodes at depth d of a tree after i random insertions

Suppose one wanted to build a tree at random. Let the first insertion at step $i = 1$ be the root node. From here, nodes are inserted into the tree at random one at a time. How would one go about ...
1
vote
1answer
21 views

Do the two huffman trees have the same corpus?

Consider the following Huffman trees: I was asked if those trees can have the same corpus. My answer was no, based on these calculations: For the right tree: $a_1 \le a_2$ $a_1 + a_2 \le a_5$ ...
-1
votes
2answers
93 views

Edge traversals of trees [closed]

I want to find a minimal vertex in a tree from which we can traverse some edges exactly twice then come back to that vertex then do it with the rest of edges. By minimal, I mean that the difference of ...
0
votes
0answers
11 views

Representative tree from sets of decision trees

I built a set of samples from an imbalanced dataset with two classes through the undersampling technique. Now, from that set of decision trees I would like to choose one representative tree. Is there ...
1
vote
1answer
21 views

Doubt in the correctness of decision tree models for constructing a lower bound

If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$. But with the decision tree model, the number of leafs is ...
0
votes
1answer
45 views

the height of a tree given n nodes and a condition [closed]

I came across a question on which I got totally stuck :( a sort of homework question) A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at ...
1
vote
0answers
32 views

Binary search tree with $n$ internal vertices [closed]

How can we prove a binary search tree with $n$ internal vertices has height $h = \lceil \log(n+1) \rceil$?
2
votes
0answers
51 views

What are applications of alphabetic trees?

Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as Alphabetic trees are Huffman ...
5
votes
0answers
124 views

Huffman tree and maximum depth

Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?
3
votes
0answers
48 views

How to go from a DAG model to bounded treewidth? [closed]

Given a Bayesian Network DAG $G$, we can transform it into a junction tree $T_G$ by performing two steps: moralisation (connect variables that have the same child, drop directions) triangulation ...
-1
votes
1answer
52 views

Satisfying condition to be in minimum spanning tree of an edge (maximum weight)

Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always ...
1
vote
1answer
60 views

What is this algorithm? Create a tree's equivalent hierarchical network

This question was originally posted here: http://stackoverflow.com/q/20735339/2305618 I am surely not the first to have implemented code to perform the following graph transformation. But try as I ...
1
vote
1answer
43 views

Doesn't post-order traversal require subtrees to be evaluated separately?

Consider this tree: If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in ...
-1
votes
1answer
86 views

Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around. I've been ...
8
votes
1answer
180 views

Data structure for map on intervals

Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers. Let $[a,b]$ denote the interval of integers $\{a,a+1,a+2,\dots,b\}$. I am looking for a data structure to represent a map ...
6
votes
3answers
1k views

Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar ...
3
votes
2answers
252 views

Priority queue with unique elements and sublinear time merge?

Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time. I am looking for a priority queue that merges in ...
3
votes
2answers
168 views

Algorithm to determine if recursion was breadth first or depth first

Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have ...
0
votes
0answers
127 views

Updating an AVL Tree Based On Balance Factors

I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it? Background: Let the balance factor ...
3
votes
1answer
54 views

Numbering of unlabelled trees

For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?
15
votes
0answers
342 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 ...
4
votes
1answer
94 views

Find equidistant triplets in a tree

Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between ...
2
votes
1answer
135 views

Number of Independent Sets in a tree

(I've been stuck on this homework assignment for far too long) I need to find the number of independent sets in a tree. For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are ...
0
votes
2answers
116 views

Why the height of the weight balanced tree is logarithmic

Could somebody explain to me why the height of a weight balanced binary tree in $O(\log n)$ in the worst case?
3
votes
1answer
810 views

Explanation of Heavy light decomposition

Can anyone explain heavy light decomposition of trees or give a resource to read it from? I have already gone through http://ipsc.ksp.sk/2009/real/solutions/l.html which is the best i could find but ...
2
votes
0answers
63 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 ...
3
votes
1answer
385 views

How to query and update ranges of arrays?

I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array. Decrease elements in range $[L,R]$ by $X$. Count the number of negative elements in range ...
2
votes
1answer
186 views

Queries on Tree

We have a tree with $N$ nodes. $N \le 10^5.$ Each node has a value $V$ associated with it. Now we have $Q$ $(\le 10^5)$ queries. There are two types of queries: Q X Y: in this type of query we have ...
5
votes
1answer
138 views

Origins of the Segment tree data structure

I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times ...