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

learn more… | top users | synonyms

-4
votes
0answers
15 views

what are balanced tree , can some one please give some information with examples

A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1. A binary tree is ...
0
votes
1answer
47 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
46 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
54 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
37 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
72 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
30 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
21 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 ...
10
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
76 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
33 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
23 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
49 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
18 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
107 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
68 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
30 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 ...
0
votes
0answers
28 views

Looking for name of siblings-first-depth-second traversal order

I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name. The requirements of the algorithm are: it visits the parent before the children. it visits ...
3
votes
1answer
95 views

Finding Minimum Weight Subgraph Spanning Tree

Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1. Suppose we also have a subset ...
5
votes
1answer
77 views

Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space

Assuming you have a balanced tree, without parent-pointers, with $n$ nodes, and a height $H = \mathcal O(\log n)$. I know you can traverse the tree in level order in $\mathcal O(n)$ time using a ...
1
vote
2answers
20 views

What do you call a subtree covering a subset of contiguous leaves?

In the data structure field, what is the (best) term used to identify (designate) a subtree covering a subset of contiguous leaves?
3
votes
1answer
37 views

Shortest path in a dynamic tree with vertex updates

There is a tree with $n$ nodes. All edges are of equal weights. The vertices of the tree can be of two types: 0 or 1. There are two types of queries: Set(X): change the given vertex X from type 0 ...
1
vote
0answers
86 views

Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
3
votes
2answers
45 views

Counting the number of tree when the set of the subtrees is given

There are a set $A$ of trees. There is another set $B$ of trees that is the collection of all possible subtrees of the trees in $A$. I don't have $A$ but only have $B$, and I need to figure out the ...
3
votes
1answer
60 views

State of the art time complexity for getting (tree) descendants by type/attribute

Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only ...
1
vote
1answer
36 views

Proof that there are same number rotation moves in any binary tree with both children compulsory

I am working on this project where I am required to find the theoretical proof for following. I have a particular type of binary trees, where 1) each internal node will definitely have two children. ...
2
votes
0answers
44 views

Using the random forest algorithm to predict vectors [duplicate]

I know this might sound like a newbie question, but bear with me. I have read a paper where researchers use a random forest to predict species distribution, but in their study, they only predict a ...
0
votes
1answer
52 views

Why not use large $k$ in a $k$-ary tree?

Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case. To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, ...
1
vote
0answers
18 views

Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?

I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says: Furthermore, the element stored in min does not appear in any of the recursive $vEB( ...
2
votes
0answers
18 views

What's a data structure for organizing strings of adjacent differences in a signal? [closed]

My inputs will be strings of a fixed length k = 2^m that come from Forex rate data. So strings of real numbers [1.101, 1.102, 1.165, 1.133, ...], or lists or whatever you want to call them. So let ...
3
votes
0answers
92 views
1
vote
1answer
69 views

Cormen. Red-black trees. Why do we need to rotate the tree after fixing its properties?

I am reading about red-black trees in Introduction to Algorithms, Second Edition by Cormen. Pages 316, 317. I don't understand why we need to rotate the given tree. See (c) and (d) in the attached ...
2
votes
1answer
145 views

Maximum independent nodes subset algorithm with strong constraint

I've a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints: The selected nodes must be the optimal solution (maximal sum of weight). If one node is ...
0
votes
0answers
31 views

Sublinear search of variables in a term

Suppose we have a forest. The leaves have labels. Let's suppose all labels are natural numbers. We would like the forest to support two operations: rebasing that replaces a leaf on first tree with ...
1
vote
3answers
127 views

Term for most degenerate tree with two children on every inner node

I'm looking for the name of a binary tree which is almost degenerate: at least one child of every interior node in the tree is a leaf. (Image from Penn State course STAT 557, Data Mining, lesson ...
4
votes
2answers
116 views

Efficiently partition tree into clusters of similar diameter

I am looking for a way to split a tree into $k$ clusters so that the cluster with largest diameter is as small as possible. All edges have the same length. I'm hoping for an algorithm that can handle ...
1
vote
1answer
298 views

What does pre-, post- and in-order walk mean for a n-ary tree?

The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and ...
1
vote
2answers
57 views

Which all nodes will qualify as an ancestor?

I was going through the fundamentals of tree structure and the definition for ancestor is as follows: A node u is an ancestor of v if there is a path from u to v. Consider the node ...
1
vote
0answers
10 views

Saving a pointer to the n/4 node in AVL tree [duplicate]

I have an AVL Tree which every node has a filed with a key which is an integer. I need to save a pointer to the Minimum , Maximum and the $\left \lfloor \frac{n}{4} \right \rfloor $ nodes. the first ...
1
vote
1answer
84 views

Algorithm for finding the root element

I have the following interface: public interface TreeElement<T>{ public List<TreeElement<T>> getChildren(); } Now, suppose I have a ...
0
votes
2answers
71 views

For AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient?

I was listening to Eric Demaine's video lecture on AVL trees and there was a claim that comes up that keeping a trit on each node (to indicate whether the node is left heavy, right heavy or balanced) ...
2
votes
1answer
51 views

Tolerated use of the term topology

In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees : 1) The first one: Node ...
0
votes
1answer
34 views

What is the order of this traversal method?

Please see below pseudo-code for finding the max-height of a b-tree ...
0
votes
0answers
35 views

enumeration of all Maximal independent set on trees

what is the algorithm for enumerating all maximal independent set on trees (without the constaint of lexicographic order) . It 's very natural to find an algorithm faster than $ O(3^{n/3})$ on trees ...
0
votes
0answers
60 views

More about the ESP tree

In this previous question I had asked about the intuition behind looking at the ESP tree. One place where it is used is to construct an approximation of arbitrary distance functions $d : [m]^n ...
2
votes
0answers
36 views

What is the intuition behind the “edit sensitive parsing” tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...
0
votes
0answers
129 views

How to represent an improper binary tree by means of proper binary tree

By definition: a binary tree needs to fulfill 3 requirements: 1) Each node must have at most 2 children. 2) Each node must have a left and right child 3) Left children is written before the right ...
2
votes
0answers
32 views

Two flavors of red-black trees with different performance

I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors: 1) In the first tree, all the data is stored in the leaves. 2) In the second tree, the data is ...
2
votes
1answer
48 views

Represent an octree as a binary tree of thrice the depth?

In an octree, each node has up to eight child nodes. This can be implemented with eight pointers per node that are set to null pointers if the child is not used. Another implementation uses a byte as ...
2
votes
1answer
55 views

Correctness proof for finding weighted maximum independent set for a tree

The maximum weighted independent set for a tree can found out using the following dynamic programming approach. Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } ...