Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
642
questions
0
votes
1answer
22 views
Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?
I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree.
The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input ...
1
vote
0answers
34 views
Convert tree with recursive relationship to parent-child tree
Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good ...
0
votes
1answer
27 views
Find height of a ternary tree
Ternary heap is like a binary tree, just every node can have up to $3$ sons and not $2$.
I try to bound the number of nodes in the heap, $n$, using the height of the heap $h$.
The solutions get to:
...
0
votes
0answers
10 views
What is the insertion algorithm for an AVL tree with balance constraint of 2?
What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
0
votes
0answers
9 views
modifing CYK to compute the number of different parsing trees of a given sentence
Given a CFG in Chomsky Normal Form and a sentence s.
I want to count the number of different parsing trees that parses s.
assuming I know how to change the CYK algorithm so it would count the number ...
1
vote
0answers
29 views
Trees with duplicate nodes and path cancellations
I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see it is as a tree. A picture ...
1
vote
1answer
14 views
Is there an Interval Tree which supports O(1) dynamic space requirements for queries?
I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).
In general ...
0
votes
1answer
22 views
Enhance B-Tree with find(k) function
I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
0
votes
0answers
8 views
Minimal t needed in B tree for the lowest reading time
I've got an assignment, which I was asked to calculate the minimal t needed in a B tree, to have the optimal searching time.
So here it is:
We've been told that in a specific B tree, with unknown t, ...
2
votes
2answers
65 views
Distance queries on Tree with hotspots
We are given a tree with $n$ vertices and some of the vertices act as a "hotspot".
We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest ...
1
vote
2answers
105 views
What's the name of this tree-like data structure?
I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties:
It consists of nodes and leaves
It has a single root element
Both nodes ...
1
vote
1answer
23 views
Understanding recursion tree for withdrawal formula
$$
T(n) = T(n-a) + T(a) + cn
$$
Now the solution says that the height of the tree $(h)$ is:
$$
h = \left \lfloor n/a \right \rfloor
$$
And I don't understand why. Maybe I didn't understand the ...
0
votes
0answers
15 views
How to reconstruct an existing splay tree by insertion?
I'm trying to figure out the same problem as stated in this question.
In brief, I want to reconstruct an existing splay tree (printed on paper) on Splay Tree Visualization by inserting the values in ...
1
vote
1answer
34 views
Why $T(n)=6T(n-1) + n^3$ has such a mess solution?
I tried to solve the recurrence relation
$T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^...
3
votes
0answers
45 views
Is there a *natural* problem that is NP-hard on trees, but in P on non-trees?
It seems intuitive that any natural problem that is NP-hard on trees, should be hard on graphs that are not trees. But perhaps this is wrong?
Question: Is there some natural decision problem on ...
0
votes
1answer
24 views
Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$
I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it?
...
0
votes
0answers
27 views
creating a binomial heap with only pointer object references
I have a problem where I must make a binomial heap in Python. I have almost all of the methods working except for the bubbleUp method.
The problem I am having is ...
1
vote
2answers
134 views
Minimum-average-cost subtree that is not necessarily spanning
I'm looking for an efficient algorithm for the following problem:
Input: a rooted tree (undirected) with a cost on each edge. It could be considered directed away from the root (or towards the root)....
4
votes
2answers
134 views
Origin of using “>” to represent child in a tree
What are the earliest known uses of the "greater than"/"chevron" symbol (>) to denote a parent-child relationship in a tree structure? i.e. parent > child
e.g.
...
0
votes
1answer
19 views
How do I calculate the probability of a PCFG rule in a parser?
I'm quite struggling with calculating the probability of a rule for a PCFG.
I've been looking for examples online and more information, but I am none the wiser.
Here is an image of the slides. I ...
3
votes
2answers
40 views
When should we construct trees, graphs to analyse an algorithm?
In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to ...
0
votes
1answer
20 views
Computing all paths from root to the leaf nodes in a tree
I have a this tree, i want to print out all paths from root to all child nodes:
NOTE: I wanted to come up with a solution that does not involve passing state between recursive calls.
...
1
vote
1answer
83 views
Finding the longest path of sum $0$ in a weighted tree
How to find the longest path with the sum $0$ in a weighted tree (where each edge is labeled with an integer weight)?
In other words, I want to find a path so that the sum (sum of numbers on edges) ...
0
votes
0answers
29 views
Is it necessary that Minimum/Maximum Heap must be a Binary Heap?
I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data ...
1
vote
1answer
36 views
Least common ancestor relative to an arbitrary vertex as root
Consider following problem:
Given an undirected tree answer following type of queries. (No. of
queries and vertices can be as high as $10^5$)
$\text{LCA}(r, u, v)$: Find the Lowest Common ...
1
vote
1answer
29 views
How to generate tree variants of a tree using recursion?
I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion?
any help is ...
0
votes
1answer
134 views
Remove range of keys from Binary Search Tree in O(s+h)
I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h)
where s is the number of keys to remove and h is the height of the tree.
Attempted ...
8
votes
0answers
89 views
MST with possibly minimal diameter
I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
1
vote
0answers
21 views
Determining Range of Current Node in Segment Tree
I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
0
votes
0answers
17 views
Why do b*trees partition 2 nodes into 3?
I'm writing a b*tree library in Rust. I'm thinking it might be better to make the purposeful decision to only implement half of the b* optimizations. (And not because it is easier, although it is.)
...
1
vote
1answer
28 views
Complexity of “Subtree of Another Tree”
I wrote an algorithm for a leetcode question. The question asks:
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A ...
3
votes
1answer
73 views
Can one determinize finite automata over infinite trees?
I'm currently considering deterministic, nondeterministic, universal, and alternating automata over infinite words and trees, with BĆ¼chi, co-BĆ¼chi, Muller, Rabin, Streett, or parity acceptance ...
2
votes
2answers
324 views
Proving correctness and optimality of a greedy algorithm
Here is a (slightly abridged) problem from Kleinberg and Tardos:
Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated ...
3
votes
0answers
37 views
Random linear arrangement of a tree with constrained edge lengths
Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the ...
0
votes
2answers
111 views
How to convert a Complete Binary Tree to a Priority Search Tree in O(n)
There doesn't seem to be any resources on this.
I would like to know if there is a linear-time algorithm to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, ...
1
vote
0answers
13 views
Confusion with “every path from a given node to any of the leaves goes through the same number of black nodes” property of RB trees
One of the properties of Red Black trees is: "every path from a given node/vertex to any of the leaves goes through the same number of black nodes"
Two related questions about this property:
1) is ...
1
vote
2answers
192 views
Graph with exactly 2 Minimum Spanning Trees
Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs).
Given this condition stipulated, prove that any cycle formed by all
the edges in both the MSTs (i.e., the union of the edges in ...
1
vote
1answer
44 views
Performance of Recursive vs Iterative Solution to “Maximum Depth of a Binary Tree”
I am looking at this question from LeetCode.
There are two solutions to this question - the recursive solution and the iterative / breadth-first traversal solution.
My question is in regards to the ...
1
vote
1answer
112 views
Efficiently finding the min-cost path of an AVL tree
It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:
The min-cost path would be 8-6-5. ...
0
votes
0answers
17 views
Need explanation of Node Structure, Search, Insertion and Deletion operations in R-Trees?
I am finding it hard to visually understand the R-Tree concepts and its primitive operations, Search, Insert and Delete(which are applicable to any type of tree). I am unable to find good sources for ...
2
votes
3answers
222 views
Can the same node appear twice in a tree?
Can the same node appear twice in a tree?
I'm asking about the node object itself, not the node's value. For example, in the following code, a's left and right ...
0
votes
0answers
14 views
Evolving graph rewritings between trees (representing JSON) and graphs (representing relational database schemas)
I have in input different, say 100, types of trees with labeled nodes (representing JSON files). I need to transform the information contained in the trees into graphs with labeled nodes (representing ...
0
votes
0answers
17 views
Comparison tree to get a minimum number of comparisons for merging sorted lists
Suppose A is a sorted list of length n and B is a sorted list of length 2. I am asked to ...
0
votes
0answers
14 views
The height of a full binary tree with $n$ notes is $\log(n+1)$, right? And is there a general formula for a tree's height?
Is it true that for a full tree (a tree that has $2^{k+1}$ nodes on level $k$, where the root is on level $1$) the height of the tree is always $\log(n+1)$, where $n$ is the number of nodes in the ...
2
votes
1answer
50 views
minimizing the maximum between a degree of a tree and its height
I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$, i.e. minimizing $\max(k, \log_kn)$ asymptotically.
If I set $k = \frac {\...
0
votes
0answers
16 views
Is it possible to implement iterative pre/in/post-order traversal with only one stack?
All iterative algorithms I've seen for pre-order, in-order, and post-order traversals of trees have used two stacks. Is it possible to do it with one? I've been thinking about it for ever, I haven't ...
1
vote
0answers
25 views
Counting number of binary trees with given node values and root
I came across following problem:
Find number of binary trees possible with 2 as roots. Nodes={1,2,3,4,5}
There was no solution given. I knew number of binary trees for given preorder is given by ...
0
votes
0answers
21 views
How do I know which node to do rotation on?
I'm wondering which node do I perform a rotation for on an AVL tree?
I think in a single rotation it is always the grandparent of the node causing the imbalance (which could either be the root node ...
1
vote
1answer
37 views
Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$
I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement.
I know it's a proof by induction and that the ...
0
votes
1answer
104 views
Determine minimum and maximum number of leaves on a complete tree
I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$.
I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
