Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 "...