Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
1
vote
0answers
22 views
Join Order Optimization
Based on the schema on the following picture:
Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player
What is the optimal join order?
I am suppoused (and that's what I tried) to use ...
1
vote
1answer
22 views
A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher
Referring to these notes regarding DFS - Click Here
They refer to the following claim that follows Definition 0.2. as observation:
A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and ...
1
vote
2answers
39 views
Term for the tree of all paths starting from a given vertex in a graph
What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?
This is the tree that is implicitly or explicitly constructed when ...
4
votes
2answers
521 views
Prove that the total distance is minimised (when travelling across the longest path)
Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have ...
1
vote
1answer
34 views
Rooted Tree Isomorphism Algorithm
I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:
Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$.
...
0
votes
0answers
62 views
Describe an algorithm, as efficient as possible, that computes the maximum mass of any set of independent stars in the given tree T [closed]
A star, in a tree, is a vertex together with all the edges adjacent to it. A collection of stars is
independent if no two stars shares a vertex. The mass of an independent set of stars S is the
total ...
0
votes
0answers
16 views
How does a binary tree waste memory when stored as nodes and references?
I'm researching binary trees and came across this section describing storage methods.
It states that:
In a language with records and references, binary trees are typically constructed by having a ...
0
votes
0answers
61 views
How many maximum height AVL trees given height?
I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that ...
2
votes
0answers
18 views
Construct a lambda term from a Böhm tree
Given an acyclic graph, how can I build a lambda calculus term such that this graph is the term's Böhm tree?
If the Böhm tree is a finite tree (so the result is a strongly normalizing term).
If the ...
0
votes
0answers
28 views
Storing binary tree with arbitrarily sized nodes without linked-list or large 32-bit pointers
So you can store a binary tree without pointers using a 1-D array:
Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :
The values of ...
1
vote
0answers
20 views
Elegant or readable way to store tree by user [closed]
Sorry if my title or question is unclear. I lack the vocabulary to formulate it properly.
I've got a classical tree structure with several layers.
I have to manage authorization for each user, as not ...
1
vote
1answer
32 views
Uniformly random iteration of subtrees
I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $...
0
votes
0answers
14 views
Trie or no Trie for 1,000 page document or searchable BigInt dataset
Tries seem to be good at storing and querying small strings, like keys to a dictionary.
What I would like to know is if there is anything better for storing large strings such as a 1,000 page ...
0
votes
1answer
45 views
Dynamic Programming Problem on Tree
Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had ...
0
votes
0answers
8 views
Converting a cyclic digraph to an approximated tree
I have a digraph that represents a taxonomy of sorts, where nodes are "concepts" (i.e., person, animal, plant, etc) and the edges represent an is-a relationship. Hence, we can have ...
1
vote
0answers
27 views
Searching Algorithm on Connected Graph
This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math.
Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...
1
vote
0answers
25 views
Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$
I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:
Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a ...
0
votes
0answers
20 views
Dynamic perfect hashing, FKS Scheme
The FKS scheme uses a 2-level hash function. The first hash function is to partition the elements of the universe $\mathcal{U}$ into the dictionary $\mathcal{S}$. Obviously many elements of $\mathcal{...
1
vote
0answers
16 views
Does keeping underflowed nodes unbalance the R-tree?
When deleting nodes from an R-tree, if a branch underflows, then it's meant to be dissolved and its children are meant to be reinserted into the tree. But most R-tree implementations that I've seen ...
8
votes
1answer
65 views
Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?
As an example, here are all possible trees for the case $k=3$:
On each node written is its arity (= the number of children).
While this should be solvable by dynamic programming, I think there was a ...
2
votes
1answer
42 views
Algorithm to find the two closest elements in a BST
For example, consider an AVL tree:
Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, ...
2
votes
1answer
40 views
What, if any, is the term for a node whose children are all leaf nodes?
More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions:
- It has >= one child
- Any children that it has are all leaf nodes.
0
votes
0answers
16 views
Is there a specific search paradigm for finding pairs in a set?
I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
1
vote
1answer
33 views
Polynomial time algorithm - Matching pairs of vertices
Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. ...
2
votes
3answers
106 views
Finding number of edges with weight less than k on the path between two nodes in a tree
You are given a tree with $n$ nodes and $n-1$ edges. Each edge has a weight. There are $m$ queries. In each query you have to answer the following question:
How many edges are there in the path ...
1
vote
1answer
30 views
Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex
How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?
UPD:
Example for n = 4:
insert 60
insert 10
insert 20
insert 50
...
2
votes
2answers
77 views
Finding the k-th smallest ternary sum of elements from three different arrays
The problem goes like this:
Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+...
2
votes
0answers
32 views
Documentation of “bin number” trees
TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
5
votes
2answers
157 views
What is the point of traversing a binary tree in preoder, inorder or postorder?
Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
0
votes
0answers
15 views
How would I optimize a tree-like graph with a significant number of redundant nodes?
Recently, I was looking at the underlying data/implementation of a survey application created using a RPA tool. As a user progresses through the survey, the "decisions" reveal a predominantly tree-...
3
votes
1answer
96 views
How to calculate the minimum number of groups, by grouping groups with capacity together?
I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem.
If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
2
votes
1answer
44 views
Data Structures - Segment Trees
I was learning about segment trees and came across this:
We have an array arr[0 . . . n-1]. We should be able to
1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1
...
1
vote
1answer
114 views
Greedy algorithm to find Minimum Dominating Set in a tree
Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
1
vote
3answers
42 views
Intuitive proof for a tree with n nodes, has n-1 edges
I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.
1
vote
1answer
22 views
Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it
Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the ...
1
vote
1answer
53 views
Checking if the graph provided by a distance matrix is a tree
I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily ...
1
vote
0answers
38 views
Intuition behind balancing of link/cut data structure
My question concerns link/cut tree structure after an access operation. I am assuming an implementation with splay trees. As far as I can tell, once you access a node v and splay it to the root, it no ...
1
vote
2answers
173 views
Is there a name for this graph search strategy?
The standard implementation of breadth-first search looks like
...
1
vote
0answers
72 views
Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))
So this is a question within a bigger question for which I've reduced to this so far:
If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
0
votes
1answer
515 views
Inorder Traversal of the Ternary Tree
According to wikipedia , Definition of In-order Traversal on Binary Tree :-
...
0
votes
0answers
12 views
Alternative technologies/theories for a “Git for Structured Graph Databases”
Along the lines of detect differences between tree structures, I'm wondering if there are any general techniques or tools (e.g. the techniques behind the tools) that can essentially do what Git does ...
0
votes
2answers
33 views
Tree with alternating types of nodes
Suppose that I have a tree where each node is either of type A or type B.
Nodes of type A ...
0
votes
1answer
64 views
Can a node of Radix tree which represents a valid key have one child?
Wikipedia says:
a radix tree is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.
Now they are situations ...
0
votes
1answer
108 views
Time Complexity of the Kruskal Algorithm after sorting
In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
1
vote
0answers
21 views
Extracting room voids in a house
I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house.
In order to do this, all I have is the raw geometry of all the elements that encapsulate ...
0
votes
2answers
77 views
In Breadth-first search and depth-first search what is the purpose of visited flag
In Breadth-first search and depth-first search, in this source code https://gist.github.com/gennad/791932
...
0
votes
0answers
40 views
Form a Tree having minimum diameter
I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter.
However, I looked for the solution, and the solution goes like this.
If the diameter of ...
0
votes
1answer
81 views
Understanding SLDNF-forest
I am trying to understand this program and the respective forest. This is from the book Logic,Programming and Prolog by Ulf Nilsson.
Question:
In the main tree, why from ←off_gound(a) can you ...
2
votes
1answer
17 views
Array of overlaping ranges
Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.
Example:
Ranges:
[red: [1,11], black: [15,16],yellow: [5,9], ...
4
votes
2answers
103 views
Data structure for a tree of points moving in space
I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "...
