# Questions tagged [trees]

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

564 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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 ...
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 ...
38 views

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 ...
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 ...
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, ...
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.
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 ...
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. ...
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 ...
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 ...
160 views

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 ...
182 views

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

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

### Inorder Traversal of the Ternary Tree

According to wikipedia , Definition of In-order Traversal on Binary Tree :- ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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], ...