For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

learn more… | top users | synonyms

0
votes
1answer
53 views

Minimal Red-Black tree with depth 3

I'd like to ask what is minimal RBT with black depth 3. Is this following RBT ? Values are not important. And that tree can't have depth 2 or 1.
0
votes
0answers
21 views

Simplification of a dervived binary tree with n nodes [duplicate]

hi I need help with this problem how do simplify this equation and what are the steps and approaches to this problem
0
votes
0answers
291 views

What is the algorithm to sort 5 elements in 7 binary comparisons?

I'm tasked with finding the algo that sorts 5 elements in 7 binary comparisons. (The 7 is derived from ceilingFunction(log 5!), which our text states is the minimum number of comparisons required for ...
0
votes
1answer
41 views

Identify Type of Recursive Sequence?

I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ ...
0
votes
0answers
106 views

Nilpotency of the adjacency matrix of a directed tree network

Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
0
votes
0answers
89 views

Straight skeleton is a tree

Can anybody give me a hint on how to prove that the straight skeleton of every polygon is a tree. Here is the definition of the straight skeleton (taken from Wikipedia): The straight skeleton of a ...
0
votes
1answer
324 views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
0
votes
1answer
182 views

has deleting node in a binary search tree Displacement feature?

I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to ...
0
votes
1answer
593 views

M-ary tree problem

A full $m$-ary tree $T$ has 81 leaves and height 4 1) Give the upper and lower bounds for $m$ 2) What is $m$ if T is also balanced? [with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 ...
0
votes
1answer
321 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
0
votes
0answers
287 views

Depth-first spanning tree?

I am going to identify tree edges and back edges in an undirected graph. The graph consists of $5$ nodes, the edges between these nodes are as shown below: Suppose starting with $v_1$, after a ...
0
votes
0answers
48 views

An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...
0
votes
1answer
316 views

Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

What is an example of a direct bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves?
0
votes
0answers
127 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem, unfortunately I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
-2
votes
1answer
207 views

Parse tree parenthesis notation [closed]

Can anyone help me understand this in a tree format? What the indentation means? How do I represent this in a tree? ...