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

learn more… | top users | synonyms

-3
votes
0answers
18 views

Use structural induction to prove the following binary tree [on hold]

Recursive def for Set X (there are two): (1)a single node is in X and (2) if x1 and x2 are in X, then the bigger tree with root r connected to the roots of x1 and x2 is in X use struc induction to ...
1
vote
1answer
39 views

Determining on whether topology is a tree or a hypercube

Assume that the nodes know that the topology G is either a hypercube or a tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to ...
3
votes
1answer
50 views

Data structure for counting bits set on a table

I have a table that contains only bits. I would like to be able to do the following two queries: SET any bit to 0 or 1; GET the number of bits that are set to 1 from the beginning of the table up to ...
-1
votes
0answers
22 views

transform one tree to another using 2(n-1) rotation

Let T1 T2 be two trees each having n unlabeled nodes. Show that it is possible to tranform from tree T1 to tree T2 by applying at most 2(n-1) rotations. Now what I came up with is that since there ...
-2
votes
1answer
39 views

Inequality to be disproved

Suppose that a search for a key in a binary search tree ends up in a leaf. Consider three sets : A,the keys to the left of the search path B,the keys on the search path C, the keys to the right of the ...
1
vote
2answers
52 views

For each vertex of a tree count vertices closer than a specified value

We have a weighted tree of $n\leq 10^5$ nodes, and for every node $v$, value $L(v)$. The goal is to calculate, for every vertex $v$, number of vertices $u$ such that ...
0
votes
1answer
44 views

Propagating node labels upwards in a tree

I am trying to think of an efficient way to synchronize a tree's nodes with the following rules. Consider for instance this tree: so the top of the heap is always ...
0
votes
1answer
55 views

Binary tree traversals reversed

Am I correct in saying that traverse(node): if node is null, return print node traverse(node's right subtree) traverse(node's left subtree) would ...
2
votes
1answer
26 views

Check whether it is possible to turn one BST into another using only right-rotations

Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, ...
0
votes
2answers
56 views

Can we construct a binary tree with width and height Θ(n)?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
0answers
37 views

Implementing BTrees without pointers

I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in ...
2
votes
1answer
44 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
52 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 ...
5
votes
0answers
61 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
87 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
132 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
39 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
196 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
54 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
166 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
58 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
57 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
55 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
36 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
77 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
48 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
104 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
19 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
47 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
135 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
44 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
186 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
24 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
98 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
12 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
25 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
56 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
52 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 ...
6
votes
0answers
138 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
55 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
69 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
44 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
93 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
196 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
275 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
173 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 ...