Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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/...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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) $ ...
user avatar
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$ ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
  • 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 &...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$. ...
user avatar
  • 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 : ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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\...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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....
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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? ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
16