Questions tagged [trees]
Questions about a special kind of graphs, namely connected and cycle-free ones.
788
questions
0
votes
0
answers
8
views
Is possible to have a "pointer" to a tree node in a functional language?
Suppose I have the following structure definition in C:
struct node {
int value;
struct node *parent, *left, *right;
}
If I want to represent a specific ...
- 101
0
votes
0
answers
17
views
kth smallest in BST with updates
I am given a BST and have to find kth smallest element in which updates are also there. It means any value in tree can get updated and then I have to find kth smallest on updated tree. Some intuition/...
- 101
-1
votes
0
answers
21
views
Best Case of Red Black Tree Insertion and Deletion
Question: During the insertion and deletion operation of a Red Black Tree data structure, each operation, can result in $\Omega(\log{n})$ color inversions? True or False?
EDIT: Each operation ...
- 1
0
votes
0
answers
20
views
Worst Case for B Tree of order M with N Keys of Linear Search
Problem: Given a B tree with order M, having N keys, what is the total number of comparisons when applying a linear search.
Example: To perform a linear scan search for a single key on a set of one ...
- 1
5
votes
1
answer
122
views
Is there a solution to the following thought experiment / problem involving trees?
I am trying to find an algorithmic solution to a thought experiment that occurred to me recently. Please excuse me if the question is a bit naïve as I am not a CS expert.
Basically I have a tree with ...
- 1,100
3
votes
0
answers
30
views
Add an edge to a planar graph and preserving the planarity
I've already posted in the Math StackExchange section, but nobody answered.
I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if adding the ...
- 131
1
vote
1
answer
30
views
Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B
I've been given the question in the title:
Create a data structure that can insert a string S in O(|S|), string may belong to group A or B (or both). The structure should be able to return a string in ...
- 11
0
votes
1
answer
79
views
I think I have discovered a new sorting algorithm using binary search tree [closed]
If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
0
votes
0
answers
36
views
Special case of single vehicle routing
I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
- 2,871
0
votes
0
answers
25
views
Using an undirected graph to represent an ordered pair?
Set theory depends on a set membership function $\epsilon$ which is a class of ordered pairs. Is it possible to construct the ordered pair from an undirected graph of unordered pairs? Alternatively, ...
- 175
2
votes
1
answer
81
views
Proving that the number of leaves in a tree >= number of unmatched vertices
Consider a rooted tree $T$. A matching in $T$ is said to be proper if for every unmatched vertex $v$ it holds that the parent of $v$ is matched to one of the siblings of $v$. It is known that every ...
- 369
2
votes
2
answers
613
views
An α-good tree with n nodes has height O(log n)
Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by
$|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We
...
- 369
2
votes
2
answers
107
views
Decision tree for searching element in sorted-array
Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$?
The answer is $ \Omega(\log n) $ ...
- 221
1
vote
1
answer
137
views
Find a path with given weight and the minimum number of edges on a tree
Suppose given a positively-weighted tree $T=(V,E,w)$ and $k\in \mathbb{N}$, where $|V|=n$, the weight function $w:E\to\mathbb{N}$, and each node has degree at most $3$. How we can find a path on $T$ ...
- 1
2
votes
1
answer
55
views
Bounding the height of a tree in a variant of disjoint set union
Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $\ell_i$ = $⌊\log_2|T_i|⌋$ and, when merging $T_i$ ...
- 369
0
votes
0
answers
27
views
Algorithm for tracking the movement of nodes in a directed adjacency list
I have a directed adjacency list of node's. The structure of a node is
Node {
id: integer;
order: integer;
parentId: integer | null;
}
and the following ...
- 101
1
vote
1
answer
42
views
prove an inequality on binary tree
Let $\mathcal{T}_n$ be the set of ordered binary trees that have n leaves.
$d_T(v)$ means the node $v$'s depth in the tree T.
Prove: for any $T\in \mathcal{T}_n$ , for any $\{c_1,c_2,...c_n\}$ , $c_i &...
- 163
0
votes
2
answers
65
views
Find the largest MinHeap subtree in a given Tree
We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in ...
- 21
1
vote
0
answers
20
views
In a relaxed radix balanced (RRB) tree, how is the height determined in practice?
In a traditional radix-balanced tree, the height of the tree can be determined quickly by counting the leading zeros of the number of elements of the tree, and indexes to node children can be ...
- 111
2
votes
2
answers
65
views
How are a graph and a binary tree represented as data structures in CLRS' Introduction to Algorithms?
In CLRS' Introduction to Algorithms:
(1) In 22.1 Representations of graphs
The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V.
For ...
- 1
0
votes
0
answers
70
views
Is this greedy algorithm optimal?
Let $T=(V,E)$ be a tree and let $k$ be a natural number. The problem is to find the largest set of vertices $S \subseteq V$ such that $(*)$ every path in $T$ consists of at most $k$ vertices from $S$.
...
- 13
1
vote
2
answers
53
views
Find the spanning tree minimizing the backtracking in an unweighted graph
I am working with undirected unweighted graphs, and I am searching for an algorithm that gives me a spanning tree minimizing the number of moves to visit every nodes.
For example, given this graph :
...
- 121
1
vote
0
answers
20
views
Counting number of copies of a given tree T in a graph G. Looking for a randomised algorithm which is an FPRAS
I'm looking for a randomised algorithm (specifically an epsilon-delta approximation) which takes as input a graph G, a subgraph T (which is a tree), and outputs an approximation to the total number of ...
1
vote
1
answer
28
views
Why does this example of a Canonical Interval Decomposition contain keys and leaves that are outside of the interval?
I am reading Advanced Data Structures by Peter Brass for self-study, and was confused about the book's example of a Canonical Interval Decomposition for the Segment Tree section (section 4.2):
So, ...
6
votes
0
answers
82
views
Complexity of frog game on graphs is exponential, or can we do better?
Frog game initializes by placing one frog on every vertex of a simple connected graph $G$ with $n$ vertices. A move consists of moving all $x\gt 0$ frogs from one vertex to another non-empty vertex to ...
- 175
3
votes
1
answer
91
views
finding an algorithm for creating a priority search tree in linear time with presorting
A priority search tree is a binary tree satisfying the following:
every node $u$ stores a point $p_u = (x_u,y_u)$
every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate.
If $...
- 1
2
votes
1
answer
56
views
(Algorithm required) How to determine if a point is in one of many rectangles
What I want to achive ist the following: I have a 2D plane and on this plane I will have a potentially large amount of rectangles (these are specified with 2 coordinates spanning it)
Whats the most ...
- 23
1
vote
2
answers
46
views
Space-efficient way to prove that a data has been processed before
Suppose that I have a stream of data packets in the form of unsigned 64 bit integers.
And I want to make sure that I am not processing the same packet content more than once.
A way of doing this would ...
- 11
1
vote
0
answers
14
views
How exactly are non-leaves in Monte Carlo tree search chosen?
I play around with Monte Carlo tree search and tic-tac-toe. For now I have followed the Wikipedia article. There is one place, where I am stuck, the selection phase. The given procedure is the ...
- 171
0
votes
1
answer
32
views
What are other alternatives to version control on structured or large and highly volatile data?
Say you are editing a document like a 1000 page book. There are 20 authors all working furiously to edit the book. Every day they are merging their changes 2 or 3 times with the main branch. According ...
- 1,871
1
vote
1
answer
108
views
Find if an edge doesn't belong to any $MST$ with some edges of unknown weights
I've faced this problem with my homework.
We're given a weighted, undirected graph $G=(V,\ E,\ w)$ with weight function $w:E\rightarrow \mathbb{R_{\ge0}}$, someone deleted the weights of some edges $T\...
- 456
1
vote
0
answers
31
views
What are the interesting data structures to work with to manipulate mathematical expressions?
For learning purposes only, I would like to make a small, fairly basic computer algebra system (CAS) manipulating mathematical expressions, such as polynomials, logarithmic or trigonometric ...
- 255
1
vote
1
answer
59
views
When is a max heap tree invariant under a root removal, followed by a re-insertion of the root?
Let $T$ be a max heap tree with no duplicate values amongst the nodes. When does $T$ satisfy the following.
Remove the root, and restructure the tree to satisfy the heap property.
Reinsert the root, ...
- 11
0
votes
2
answers
154
views
Disjoint Set deletion
The wikipedia entry for disjoint set data structure includes the statement (in the "Applications" section)
Note that the implementation as disjoint-set forests does not allow
the deletion ...
- 115
0
votes
0
answers
43
views
Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?
In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state:
The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
- 1,871
0
votes
0
answers
30
views
How to count the number of nodes for a tree generated by context free grammar derivation?
Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language.
For example:
...
- 287
1
vote
1
answer
54
views
If the distance to a vertex is updated in the n-th relaxation of Bellman Ford, is that vertex on a negative-weight cycle?
Recently I asked a question Here about following topics:
after finishing bellman ford algorithm, if BF continue to update
distances and distance value related to one vertex v being
updated,then v is ...
0
votes
0
answers
31
views
Upper bound of sum of sub-tree depth difference on a complete binary tree with $n$ leaves
A complete binary tree with $n$ leaves has $n-1$ internal nodes. For every internal node $i$, I care about the difference between the maximum depth of the left sub-tree and the maximum depth of the ...
- 215
1
vote
1
answer
102
views
bellman ford and one surprizing fact
I ran into a very surprising local contest problem.
after finishing bellman ford algorithm, if we continue to updating
distance and distance of one vertex v being updated, then v is
on negative cycle....
0
votes
0
answers
30
views
Find set of vertices of max size under some restrictions [duplicate]
I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question.
Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
- 456
0
votes
1
answer
87
views
Bound the sum of leaf depth on a complete binary tree of $n$ leaves
A complete binary tree is defined as a tree where each node has either 2 or 0 children.
For a complete binary tree with $n$ leaves, there can be different arrangements of nodes, let's define the ...
- 215
0
votes
1
answer
81
views
Find most vertices in a directed tree where no path of length less than 3 connects any pair
Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of ...
- 456
0
votes
0
answers
38
views
what should we add to a 2-3 tree to be able to find a value with this time complexity?
I've got this question that asks me to make changes to the 2-3 trees that would make it possible to do a find(x) function that would find x with O(log(rank(x))) .
**rank(x) is x's index in a sorted ...
- 1
4
votes
1
answer
57
views
How can we process these types of queries on trees?
CAN SOMEONE FIND A BETTER (MORE DESCRIPTIVE) NAME FOR THIS QUESTION, THANKS
I recently thought of this interesting Tree problem:
Given a tree with $N$ nodes, let $val_i$ = the "value" for ...
- 425
1
vote
0
answers
33
views
Data structure for quickly obtaining all axis-aligned rectangles completely within rectangular region
I'm stuck on a homework assignment. There are $n$ axis aligned rectangles and we need to find a data structure of size $O(n \log^2 n)$ and query time $O(\log^3 n + k)$ that can give all rectangles ...
- 11
0
votes
0
answers
70
views
Efficient data structure supporting search query with contains
Suppose I have a table with millions strings in it as keys.
What data structure can I use in order to efficiently support only queries like that?
...
- 101
1
vote
1
answer
162
views
Algorithmic Problem on Trees
Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find ...
- 67
0
votes
0
answers
27
views
Treap use cases
I am trying to develop an appreciation for the treap data structure; my goal is not to implement one but use boost when the problem calls for this construct.
Some use cases, or small problems showing ...
- 125
1
vote
1
answer
311
views
How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time
This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani.
Specifically, the problem statement is:
Give a linear-time algorithm that ...
- 235
0
votes
0
answers
37
views
How do right contexts work in context-sensitive L-Systems?
I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
- 1