Questions tagged [trees]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
810 views

What is the height of avl tree with n nodes [closed]

what is the height of avl tree with n nodes ? Can you explain it with formula ? I couldn't find any formula to solve this problem.
0
votes
0answers
24 views

How to find the maximum element in a multi-tree under logN time?

Here N represents the number of elements in the multi-tree. Please state the algorithm that you have used to do so. It would be great if you can implement this in Java/C++ too and post the code as ...
0
votes
1answer
508 views

Code to count number of leaves of a tree? [closed]

I've just started learning C. Can anyone tell me whether my code is correct or not, if not what's the correct version? This is code for counting number of leaf nodes. Is this efficient one if this is ...
1
vote
1answer
992 views

Rotations in a treap

I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done. Image 1 Image 2
4
votes
2answers
1k views

Have I invented a new data structure?

EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th ...
0
votes
1answer
246 views

Link-cut trees: how to code cut(u,v)

In most bibliography, only cut(v) is defined. More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree. The pseudo-code and code for this is: ...
4
votes
3answers
4k views

how is data in a tree stored in memory?

I am not so familiar with trees. How is a tree stored in memory? what is the data structure type used for storing it? As a string?linked list? stack (!)? Or is there some kind of data storage model ...
1
vote
1answer
395 views

Trie traversal to maximise XOR in a tree but with a condition

Input:I am provided with x and y. x is a 32 bit non negative integer and y is some node-id of the tree. So, I built a trie with 32-bit non negative integer values which are the keys associated with ...
3
votes
1answer
434 views

Link-cut trees: using access() and link()

I am having some trouble on understanding link-cut trees, so I need some help. Suppose that we have nodes $A, B, C, D$ and we want to do the following operations: Link(A,B) Link(B,C) Link(C,...
1
vote
1answer
66 views

Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)

I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials) ...
0
votes
0answers
53 views

Tree algorithm to calculate greatest k

Given a tree, where each node holds a unique number, each of these numbers is represented in $O(log\,n)$ bits. Describe an algorithm to calculate the greatest number $K$ there is. I would like to ...
-1
votes
1answer
138 views

The longest path in a tree

Help me demonstrate this or there is a counterexample? Let $T(V,E)$ be a tree with $|T| \geq 2$ and a path $P{(u_0,u_1,u_2,...,u_n)}$. The longest path in a tree has $d(u_0) = d(u_n) = 1$.
0
votes
1answer
32 views

R-Tree multipath search - remember the path?

R-Trees can take several paths to retrieve an item because of overlaps in data being indexed or index structure. However, if we run the same search many times on the same unmodified structure, can we ...
2
votes
1answer
1k views

Efficient Algorithm to compute radius of tree

Given an acyclic undirected graph alike to this one : (Here the center is the node '2', and the radius is 5) What is the most efficient (ideally in O(n)) way to ...
0
votes
1answer
231 views

How important is balance of a tree?

I am exploring variations of trees. I know that a quality which is sometimes desired is balance in the tree so that tree depth is reduced. But I am imagining that in situations in which several paths ...
1
vote
0answers
142 views

Edge coloring optimization using dynamic programming

The problem is to find an algorithm that colors all the edges in any arbitrary tree T with a root r, let's say in blue and red, such that the number of blue edges is maximal and there isn't more than ...
0
votes
2answers
765 views

Algorithm to find path with max sum of degrees in a tree structure

Is there an efficient way to find a path from root to a leaf such that it has the maximum sum of degrees of nodes from all the paths possible in the tree. For example if a tree is defined as the one ...
1
vote
1answer
1k views

Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
0
votes
0answers
35 views

Number of possible balanced binary trees [duplicate]

A tree is balanced if the subtrees of each node differ in height by at most one. How many balanced binary trees can we create from $n$ nodes?
3
votes
0answers
1k views

Lowest single common ancestor in a Directed Acyclic Graph?

I was reading how to find the Lowest common ancestor in a DAG. A DAG can have scenarios where the LCA yields multiple solutions and I feel the accepted answer explains that pretty well. However, one ...
1
vote
1answer
98 views

A closed form expression for # of inputs of a binary tree and its number of nodes

Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes? In case that the binary tree is a full tree, it is ...
0
votes
1answer
427 views

Strict-Binary Tree - Same Post-order & Pre-order sequences?

I'm going through some past exam papers for my course and I'm having trouble completing this one question. It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order ...
0
votes
1answer
161 views

Cost of find operation on a tree data-structure

I implement my data sets with a tree data-structure. The tree data-structure has a method named MakeSet which creates a set with one node. The tree data-structure ...
0
votes
1answer
40 views

Are there any efficient algorithems to find packets similarities in a list?

I would like to make a program which finds similar packets (there might be more then one class of similarity) in packet list (which is updated all the time). Are there any efficient algorithems to ...
0
votes
0answers
52 views

Can't reach a balance in a DFS search?

Below is a question based on CLRS, about using an algorithm to reach a balance between a group of friends. I figured the best way to do this, is through the use of a DFS algorithm. Below the question ...
0
votes
1answer
64 views

Computing tree alignment distance

I am implementing the dynamic programming algorithm for computing tree alignment distance as described in "Alignment of trees — an alternative to tree edit". But I got stuck in lemma 3 on page 141 (...
1
vote
0answers
81 views

Conceptualizing a balance in a DFS traversal [closed]

I'm trying to use the concept of DFS traversal to go through a cycle, and attempt to get a balance of 0 in the end. Each student either owes or is owed some money, so I'm trying to go through all of ...
0
votes
0answers
254 views

How to efficiently find a minimum spanning tree?

I found this question from CSLR that I'm trying to figure out before my final. You are given a weighted, connected, undirected graph G = (V, E) and one of its minimum spanning trees T ⊆ E. Now ...
2
votes
0answers
81 views

How to cut a full binary tree evenly

Given a full binary tree of size $n$, I need to cut the tree into two by choosing an edge and removing it. I want the cutting to be as equal as possible (i.e. the two subtrees have as equal weight as ...
0
votes
1answer
470 views

Longest possible path from root to a leaf of a red black tree

For the worst case of a red-black tree, what would a tree with 10 nodes look like?Since there can not be 2 consecutive red nodes and there is rotation is it safe to say that it balances out the trees ...
2
votes
0answers
18 views

How to avoid empty spots when inserting in a B+tree

When you insert a new item in a B+tree leaf node, and the node is full, two new nodes are created and they're both filled halfway and the values get re-distributed accordingly. Before the insertion: ...
2
votes
0answers
116 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
392 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
130 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
89 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
65 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
348 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
135 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
162 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
803 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
718 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
145 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
206 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
768 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
331 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
197 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
350 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
159 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
67 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 ...