# Questions tagged [trees]

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

564 questions
Filter by
Sorted by
Tagged with
0answers
100 views

### Join Order Optimization

Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? Based on the schema on the following picture: I am suppoused (and that's what I tried) to use ...
1answer
30 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 ...
2answers
42 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 ...
2answers
584 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 ...
1answer
89 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$. ...
0answers
28 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 ...
0answers
107 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 ...
0answers
26 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 ...
0answers
47 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 ...
0answers
23 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 ...
1answer
38 views

0answers
17 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 ...
1answer
70 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 ...
1answer
55 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, ...
1answer
43 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.
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 ...
1answer
37 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. ...
3answers
156 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 ...
1answer
36 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 ...
2answers
160 views

0answers
41 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 ...
2answers
182 views

### Is there a name for this graph search strategy?

The standard implementation of breadth-first search looks like ...
0answers
189 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 ...
1answer
948 views

### Inorder Traversal of the Ternary Tree

According to wikipedia , Definition of In-order Traversal on Binary Tree :- ...
0answers
14 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 ...
2answers
40 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 ...
1answer
118 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 ...
1answer
297 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?
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 ...
2answers
149 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 ...
0answers
45 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 ...
1answer
93 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 ...
1answer
19 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], ...
2answers
104 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 "...
1answer
67 views

### Could a Van Emde Boas tree be used for storing matrices?

I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix. I was wondering if ...