Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
108 views

Coloring of a K-ary tree using minimum paint Buckets

I was recently asked this problem in an interview and I couldn't solve it. Need some help on how to solve this problem. Given a K-ary tree with N nodes (N <= 2000 and K <= 12) you need to ...
3
votes
0answers
350 views

B+tree implementation using single file on disk

I'm studying B+trees and I'm trying to understand how actual data can be stored in a physical file and still allow fast lookups. None of it would be in memory, all of the pointers would be "seeks" to ...
2
votes
2answers
120 views

How can I get all representations of an n-ary tree that completely “cover” the tree?

I have an n-ary tree and I want to get all possible representations of the tree that "cover" (for lack of a better term) the tree. Here's what I mean by cover: Suppose we have the following tree <...
2
votes
0answers
76 views

Counting inversions with index constraint

I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$ $a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis. The question is how to find a algorithm that is ...
1
vote
0answers
61 views

a variant of Fitch's algorithm when it is known that one path has cost 0?

Fitch's algorithm solves the small parsimony problem - given tree topology and leaf labels, but not internal node labels, find best internal node labels (i.e. best score) for that tree. The score is ...
1
vote
1answer
335 views

Number of nodes of height $h$ in a heap or almost complete binary tree

I came up with the following statement: If there are $X$ nodes of height $h$ in an almost complete binary tree, there can be at most 1 node of height $h$ that is not full. That is to say, $X-1$ ...
2
votes
1answer
123 views

When an ISAM index is built, how is the number of leaf nodes per index node (the “fan-out”) calculated?

I asked this question on DB.SE but it didn't get any traction, so I'll ask it here... The following statement is in the Ramakrishnan text (2nd ed. page 252): (emphasis in bold is mine) The non-...
1
vote
0answers
155 views

Unranked trees grammars?

Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function $ar : \Sigma\rightarrow\mathcal{...
2
votes
1answer
655 views

Insertion of n consecutive keys in an initially empty B-Tree

Consider this question ( 18.2-4 of CLRS) which states that: Suppose that we insert the keys ${1,2,...,n}$ into an empty B-Tree with minimum degree 2. How many nodes does the final B-tree have? ...
1
vote
1answer
670 views

For AVL trees, how do we know if a RL or a LR rotation is needed?

Suppose I am trying to construct a simple AVL tree: Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses? From what I ...
2
votes
1answer
118 views

Infix vs postfix vs prefix - which has the smallest processing time

Infix, prefix (polish notation) and postfix (reverse polish notation) are all forms of arithmetic operations. As I understand it, infix is what we use in maths where the rules of BODMAS (Bracket, ...
0
votes
2answers
202 views

Interesting problem on tree

You are given a tree of $N$ nodes with colors assigned to each node. You need to find for each node $X$, a value $AR[X]$. $AR[X]$ = The sum of values of $CALC(X , i)$ for each $i$ from $1$ to $N$. $...
3
votes
1answer
654 views

Red-Black tree height from CLRS

The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is $$h(n) \leq 2\log_2(n+1)$$ There's a subtle step I don't understand. The property 4 reported at the beginning of ...
0
votes
1answer
244 views

Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean?

There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-...
1
vote
1answer
188 views

What is the literature on a sparse matrix encoding of rose trees?

I have 'discovered' a way to encode rose trees (see e.g. What are the applications of Rose trees? ) as a sparse matrix: if you have a node n with ID i and parent ID p, then you place n in the matrix ...
1
vote
1answer
327 views

Algorithm: How to find the number of independent sets in a tree?

I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent ...
4
votes
0answers
149 views

Weak equivalent tree grammar for Context-sensitive word grammar?

Consider arbitrary context-sensitive grammar on strings $G_s$. Is any known and described formalism (or type) for tree grammars, using which we can build weak-equivalent tree grammar $G_t$, which ...
0
votes
0answers
64 views

Analysis on comparisons in a heap-like sorting algorithm

I've stumbled a heap-like sorting algorithm on the Internet as followed: $\\$ For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly. Step 1: From ...
0
votes
1answer
34 views

Evaluating tree data iteratively

Community, I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these: In order to be able to evaluate the final value of a tree given only leafes with ...
4
votes
2answers
1k views

Minimum-weight shortest-path tree

How can we compute the shortest-path tree of minimum total weight for a given connected graph? I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one ...
3
votes
1answer
2k views

Find longest overlapping interval

Given a set $S$ of $n$ overlapping intervals, where each interval is in the range of [1..O(n)], preprocess $S$ so we can efficiently answer the following query: Given an interval [i,j] output the ...
3
votes
1answer
147 views

Is there any graph problem that, when restricted to trees, has $\Omega(n^2)$ time complexity?

Trees are pretty linear in nature, since the number of edges is always one less than the number of vertices. Furthermore, the absence of cycles can sometimes drastically reduce the computational ...
3
votes
1answer
310 views

Best way to merge different trees to single data structure?

I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast ...
5
votes
0answers
368 views

What are these tree transformations called?

I want to transform a general rooted, node-labeled tree into a related binary tree. I came up with four different schemes ("left shallow", "right shallow", "left deep" and "right deep" binarization) ...
1
vote
1answer
255 views

Efficient algorithm to find all distances to a specific node in a tree

I wish to calculate the number of nodes within a certain distance of a particular node in a tree such as the one below: Let's assume I'm looking for all the distances to node 2. What would be the ...
3
votes
1answer
35 views

Why divide by $b-1$ when computing size of a tree

In one of the lectures I went to, my professor stated that in order to determine the size of a search tree, we use the following formula: $$\frac{b^{d+1}-1}{b-1},$$ whee $b$ is the branching factor ...
2
votes
1answer
356 views

Binary Search Tree Stability Data Structure

After constructing a binary search tree, you can read off the key values in ascending order by performing an in-order traversal. Will the resulting sorted order be stable? If so, how would the ...
3
votes
1answer
325 views

Admissibility of heuristic in the $A^*$ algorithm

The CS188 course from Berkeley goes to great length in explaining why the optimality of $A^*$ algorithm is conditioned by the admissibility of heuristic. Note: admissibility of heuristic means that: ...
0
votes
1answer
354 views

What is a Huffman tree for a Block-Code?

We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ". I have created a Huffman tree for the string w. We get the following table: Now I want to create a Huffman tree for a Block-Code ...
1
vote
0answers
112 views

Given a digraph and a root, find a tree that minimizes the sum of edges

Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$. Solution: A directed tree with root $v$. Objective: Minimize total weight. My formulation: ...
0
votes
0answers
86 views

What is a good metric to choose the degree of a B-Tree?

What is a good metric to pick the degree of a B-Tree? I assume this depends on the number of expected elements? Degree 2 gives us a 2-3-4 tree (each node contains 1-3 items and 2-4 children). How can ...
1
vote
1answer
110 views

optimal lifted phylogenetic alignment - how to improve time complexity?

optimal lifted alignment - is a dynamic programming algorithm. Its input is a tree $T$ with $k$ strings assigned to its leaf nodes (their length is $n$). The algorithm then assigns strings to the ...
0
votes
1answer
169 views

Merging two binary search tress

You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$ nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys in tree B. ...
1
vote
1answer
838 views

weight balanced binary tree vs height balanced binary tree [closed]

What are advantages and disadvantages of weight balanced binary tree over the height balanced binary tree?
0
votes
1answer
789 views

Merging two complete heaps

Suppose you have two heaps each containing $2^k - 1$ elements. Design an efficient algorithm for merging these two heaps into a single heap. My approach was to assume two heaps are maxheap. Create ...
2
votes
0answers
448 views

Minimum cost edge in path between nodes (tree)

I'm working on a problem and I've managed to design an efficient algorithm, but I'm stuck at the last part. After some processing I'm left with a tree and I have to answer several queries of the ...
5
votes
2answers
176 views

Is there a Tree with deterministic traversal, but which nodes can vary?

I have a dynamic closest-pair problem. In my problem though, the points never move, but instead disappear and reappear. That is, I would like to find for a point $p$ (where $p\in\mathbb{R}^3$)* in a ...
5
votes
0answers
134 views

Assignment of coprime values to a tree

I recently saw this question somewhere and thought a lot on it but was unable to find an efficient solution for it. Asked on Stack Overflow but got no solution there. The Problem is as follows - ...
3
votes
0answers
1k views

What is the Big-Oh asymptotic complexity of learning in Random Forests?

Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right. CART (Classification and Regression Trees) uses the Gini index for ...
3
votes
1answer
355 views

Expected distance between tree nodes

I have been given a tree with n nodes and n-1 edges with it's weight. There are two people A and B. I have been given a list of nodes of size k. A will pick a random node x from this list and B will ...
0
votes
0answers
51 views

Tree - how much elements have the subtree got?

It's the continuation of the exercise: https://cs.stackexchange.com/questions/65384/tree-elements-influence-on-another-elements-searching-for-specific-elements I need to say how many elements do I ...
0
votes
0answers
104 views

Expected distance between two random nodes in weighted tree [duplicate]

Given an undirected connected graph with N nodes and N-1 edges. Out of N nodes, 1...k nodes are selected, out of which 2 nodes are selected randomly (uniformly). How do I calculate the expected ...
1
vote
1answer
114 views

Assigning all nodes in a tree a parent and children

If one was given a tree in the form of a list of $A,B$ (not implying which one is the parent) pairs implying that node $A$ and $B$ were connected by an edge, how could a root node be determined and ...
-1
votes
1answer
120 views

Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3? if the maximum distance ...
3
votes
2answers
573 views

What is the “Chairman Tree”?

My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs ...
1
vote
1answer
978 views

Why do so many 8-Puzzle solving algorithms use DFS instead of BFS?

I see so many 8 Puzzle Solvers use a stack instead of a queue. Why is that? If you are looking for the solution with the fewest number of moves, wouldn't the solution be at a shallower point in the ...
8
votes
0answers
140 views

What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?

Lets consider two node-labeled rooted trees Q and D. According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
-1
votes
1answer
179 views

What makes is the difference between a tree and a graph?

I have seen in some text books that they have started talking about a tree and then they use the terms such as vertices and edges and treat is as a graph. What makes a graph a graph and what makes a ...
1
vote
1answer
148 views

Making mathematical expressions as balanced trees as possible

I am having some trouble with turning the following mathematical expressions into as balanced binary trees as possible. This is what I have done so far, but is there a way to make them even more ...
1
vote
0answers
122 views

Algorithm to compare hierarchical data

The task is to compare two trees and determine what are the changes. Both trees are represented as an adjacency list (ID, ParentID). Base tree: A (ID: 1, ParentID: 1) B1 (ID: 2, ParentID: 1) C1 (...