Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
895 questions
1 vote
1 answer
149 views
Given a tree, find a preorder-like ordering which satisfies additional ordering between nodes
Suppose you have this tree: 0 / \ 1 3 | | 2 4 / \ 5 6 With preorder-like ordering I mean the orderings where the father ...
- 11
0 votes
1 answer
77 views
Counting Number of Complete Binary Trees with n Nodes
I know that the number of different complete binary tree structures (unlabeled) for n nodes is basically 1, because the structure is fixed. Now I am trying to find the number of labeled complete ...
- 91
1 vote
1 answer
72 views
What do you call the two most common ways of selecting a random leaf node from a tree?
If you have a tree, there are two common ways to select a random leaf node from the tree: You can "flatten" out the tree, so that each leaf node gets selected with the same probability. ...
- 11
1 vote
1 answer
61 views
What does the Minimum Spanning Tree in a Relationship Graph represent?
Say that you have $n$ friends. They each have preference weights for each other. (e.g. the edge between Bob and Alice is 10 and the edge between Bob and Carl is 0.5, meaning that Bob likes/wants to ...
- 652
0 votes
0 answers
49 views
Understanding Gabow's Microsets
I'm trying to understand Gabow's LCA algorithm in (static) trees with $O(n)$ time preprocessing and $O(1)$ time queries (this is different from the popular Euler tour + RMQ approach). From what I ...
- 111
0 votes
1 answer
58 views
Can red-black tree augmentations depend on other augmentations and still be maintainable in O(logn)?
by "augmentation" i mean adding an additional field to each node. All sources i found say something that falls into one of two categories: "A field f in a red-black tree can be ...
- 3
2 votes
1 answer
130 views
Deleting Minimum Number of Nodes from Tree to Make Height Less than Limit
I found an algorithms/theory question that I'm having trouble with: Given a tree, delete nodes by compressing paths as follows: if node n is deleted, then the ...
- 21
1 vote
0 answers
39 views
Transforming undirected trees into rooted directed trees in Macaulay2
I'm working with the NautyGraphs package in Macaulay2, and I use it to generate all the undirected trees with a fixed number of vertices. For instance: i23 : g = generateGraphs(10, OnlyTriangleFree =&...
user181751
1 vote
1 answer
71 views
Number of cycles in a digraph (Resource Allocation Graph)
My understanding of directed cycles in a digraph $G$ is that it's is a non-empty trail $(v_1, v_2, ..., v_n)$ to some $v \in V$ to itself, where $V$ is the set of vertices. From this graph, I see 4 ...
- 11
1 vote
1 answer
88 views
Given a tree, for each node $U$ find the furthest node $V$ such that GCD of weights on path from $U$ to $V$ is above 1
Edit: This problem came to our national level informatics competition and I can't find the original source Say we have two functions $g(u, v)$ and $d(u, v)$ for a tree with $N$ nodes and $N - 1$ edges....
- 23
3 votes
0 answers
48 views
What is a minimal set of combinators capable of performing any tree permutation in a linear setup?
Let's define a Tree of Ints as: data Tree = Node Tree Tree | Leaf Int Let X be a source tree, and ...
- 4,219
1 vote
1 answer
78 views
Number of paths in a tree with a given sum S
Given a tree with $n$ vertices, with each vertex having sum number $a_i$, I want to find the number of pairs of vertices $1 \leq i < j \leq n$ where the path from vertex $i$ through vertex $j$ has ...
- 11
2 votes
0 answers
64 views
Is the Union-Find algorithm really based on trees?
In the Union-Find data structure (also known as the Disjoint-Set data structure), elements of a set have directed edges providing paths to the representative element, or root, of the set. Each set ...
- 1,592
0 votes
0 answers
74 views
Efficient deletion from Fenwick tree
I was reading a textbook (Competitive Programming 4 by Steven Halim) and it asked as an exercise to see if we could implement deletion on a Fenwick tree. The most clear solution (and easiest to ...
- 1
1 vote
0 answers
44 views
Upper bound on a tree containing sum nodes and choice nodes, requiring consistent choices across subtrees [closed]
I have a tree containing sum nodes, choice nodes and point nodes. I'd like to maximize the number of points at the root of the tree. The value you get for a point node is the number of points on that ...
- 111