Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
-1
votes
0answers
10 views

What is the “filling ratio” of a quad tree?

So I have a task at uni dividing some plane into a quad tree, so far so good. But one sentence of the task is screwing me over: "[Quad Tree] with a maximum filling ratio of 2" What does that ...
0
votes
0answers
17 views

Minimum unrooted binary spanning tree

Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints: tips have degree $1$ internal vertices ...
1
vote
1answer
42 views

More efficient way to parse array into binary search tree

Let's assume I have array which I need to parse into binary tree ...
0
votes
0answers
10 views

Dimensional reduction of quadtree influence on clustering with dbscan

Let's say we take a quadtree of 50 dimension and apply dimension reduction(Assume the dimension reduction works well). Why does the dimension reduction not influence the clustering with DBSCAN(Mintpts:...
0
votes
1answer
19 views

Children of internal node in a quadtree with high dimensionality

Let's say for example we have 1000 points and 50 dimensions. And we build a quadtree where each node represents a 50-dimensional box and is divided by splitting the box into smaller boxes that are ...
-3
votes
1answer
148 views

If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x

Statement: If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x. Hint: Begin by computing a DFS tree, and prove an upper bound on its height. I am supposed to prove the ...
4
votes
0answers
49 views

Collision detection with vary constraints

I have an edge-weighted tree, and for each leaf of the tree, there's a corresponding point on the 2D plane. For each pair of points $u$ and $v$, let $d_{uv}$ be the distance of the corresponding ...
2
votes
1answer
33 views

Optimal online algorithm to guess the tree

I have a tree on $n$ vertices. Your goal is to find the adjacency list for it. $n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the ...
0
votes
0answers
17 views

Partition in a tree shaped distributed network

We are given a synchronic undirected tree shaped network, with $n$ indexed nodes. We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given. We need to ...
0
votes
0answers
34 views

A claim regarding Huffman tree?

I saw the following claim: Given $Q=\{1,2,\dots,n\}$ and $f$ (positive function) such that: $$f(1)>f(2)>\dots>f(n)>f(1)/3$$ Then there are leafs at maximum 3 different levels of Huffman ...
3
votes
1answer
33 views

Algorithm to Compute High Water Mark

I saw this algorithm question which is as below. There is a server that receives request Ids that are positive integers. The High Water Mark (HWM) for the server at any instant of time is defined as ...
0
votes
0answers
12 views

Research on Tree Automata/Tree Transducers for implementing Tree Generators

I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically ...
0
votes
0answers
19 views

Alter Sankoff's Algorithm to give all optimal solutions

I'm trying to find a way to alter the Sankoff's Algorithm so it will trace back all the optimal solutions and not only one. Is it possible?
3
votes
1answer
33 views

Representing abstract syntax tree as a graph

Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code? The goal and application ...
3
votes
2answers
145 views

Edge exchange property of two Minimum Spanning Trees

Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T' Then I want to prove ...
0
votes
1answer
46 views

Constructing a crown graph given an independent set

A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold: (a) The set of neighbors of vertices in $C$ is ...
3
votes
1answer
37 views

Upper bound on the number of subgraphs in a tree

Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc. For example, consider the ...
1
vote
0answers
32 views

Why is converting a suffix tree to a suffix array not O(nklogk) time

Let's say that we have computed a suffix tree in O(n) time, and wish to use this to create a suffix array. According to wikipedia: A suffix tree can be built in $O(n)$ and can be converted into a ...
0
votes
0answers
37 views

Augment the tree data structure for disjoint sets to implement the PRINT operation

Consider the following new operation for disjoint sets PRINT(x): print every element in S_x the set containing x One Approach that I found but couldn't figure out completely : In addition to tree we ...
2
votes
1answer
86 views

A connected acyclic graph has $n-1$ edges

Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third: $G$ is connected $G$ is acyclic $G$ has $n-1$ edges Proving $1, 2 \implies 3$ A connected, ...
1
vote
1answer
48 views

How can I make my algorithm more efficient?

I came across an algorithmic problem. I do not know how to do it optimally. The problem is as follows: There is an increasing array $A$ of size $n_1$ There is an array $M$ of queries of size $n_2$ ...
3
votes
1answer
161 views

Changing a matrix to become an ancestry matrix

An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some ...
1
vote
0answers
20 views

Is there an official name for this tree merging algorithm?

Is there a standard name for an algorithm to handle this type of tree merge? Each node of the tree has a label. Nodes from the 2 trees should be combined if they have the same label, and their values ...
4
votes
2answers
96 views

Why does my code work: bijecting binary trees to Dyck paths

The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan ...
0
votes
1answer
53 views

How to calculate the average depth of a binary tree?

My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach ...
0
votes
1answer
74 views

Time complexity of insertion in binary search tree

Given a binary search tree $T$, we insert $n$ elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$...
0
votes
1answer
82 views

Find successor element in heap

Does finding the successor of an element in a heap take $O(\log n)$? An heap is not a binary search tree, so couldn't an element's successor be found in $O(n)$ time?
1
vote
0answers
31 views

Weight of lowest common ancestor satisfies strong triangle inequality

How do I prove that $d(x,y)$, defined as the weight of the lowest common ancestor of $x,y$, satisfies the strong triangle inequality: $$ d(x,y) \le \max(d(x,z), d(y,z)) $$ How do I even start such a ...
0
votes
0answers
9 views

2D segment tree update/modification step complexity

I am having trouble understanding the complexity of the "Modification query" in https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/. It states at the bottom of the ...
1
vote
0answers
34 views

Count number of intervals containing a point

There is a problem (10.6) in Computational Geometry: Algorithms and Applications 2.edition by de Berg et al. where you have to solve the problem of given $n$ intervals, $I$, on the real line, count ...
1
vote
2answers
97 views

Proving that a preorder traversal of a rooted tree can be performed in linear time

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
1
vote
0answers
16 views

Better version of heavy-light decomposition: always draw path to largest subtree

Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ). The problem: given any tree of size N, find a way to split it into ...
1
vote
0answers
25 views

Equally optimal nodes during minimax with alpha-beta pruning

Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (...
0
votes
1answer
60 views

AVL-tree insertion complexity proof

I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how. I also tried to find it somewhere on the Internet, but I could not find any good results. Do you ...
1
vote
1answer
37 views

Relation between mathematical functions and trees?

I try to express datastructures in a form of mathematical functions. For example an array or a dictionary is just a function to me. Is there a good way to model a tree in terms of functions?
1
vote
2answers
33 views

Efficiently enumerating all “good” strings given the ability to say whether a partial specification can be good

Suppose that I want to enumerate all English language words of length 5. If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. ...
1
vote
1answer
32 views

MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase?

Hello I am currently working on an implementation of MCTS and I ran into the problem that my tree traversal policy selects nodes with terminal game states. Furthermore how do I prevent selecting a ...
0
votes
0answers
21 views

How to find diffrenet ways to implement merge and delete_min operation in binomial heap?

I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says: ...
0
votes
1answer
46 views

2-3 tree: Sum of leaves in a given range

I am implementing a 2-3 tree, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which ...
1
vote
1answer
64 views

What is the Number of epochs with no improvement after which training will be stopped.?

I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check ...
0
votes
1answer
60 views

How does CNN deal with rotation invariant pictures?

I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply ...
4
votes
2answers
88 views

How to make efficient path minimum queries in a tree?

Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them? My ...
1
vote
1answer
36 views

minimum number of edges that should be added to an undirected graph to make it a tree

Basically, it's this rosalind problem. You're given a number of nodes and an adjacency list. My initial guess was that the answer was the number of connected components minus 1, since by joining every ...
0
votes
0answers
31 views

Some nodes in binary search had broken.how we can fix it in-place by swapping nodes?

Given a binary search tree(can have any height) .Some nodes its value changed and violate bst property how we can recover binary search tree property in-place by just swapping a node with its ...
0
votes
1answer
60 views

Two definitions of Safe Edge

I ran into an interview two days ago and came across one strange definition of safe edge. We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is ...
6
votes
1answer
185 views

Finding n farthest leaves in a tree

Given a tree $T$, I want to find a subset $N$ of $n$ leaves that are farthest apart. I.e., I want to find $N$ that maximizes function: $$f(N)=\sum\limits_{x_1,x_2 \in N, x_1 \neq x_2}{dist(x_1,x_2)}$$ ...
1
vote
1answer
50 views

Finding largest disjoint subtrees spanning nodes

I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found. Now for each department, I would ...
1
vote
1answer
71 views

facts on tree and MST

We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST. The following ...
0
votes
1answer
77 views

How to (Efficiently) Sort a List of Items with Parent/Child Relationship

I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member ...
1
vote
2answers
46 views

How to index a tree to allow efficient search for paths?

By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be ...

1
2 3 4 5
15