# Questions tagged [binary-trees]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
182 views

• 171
355 views

### Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
• 679
52 views

### Hash-containing Binary Tree?

I saw the question somewhere "Binary tree vs hash table, which one is better?" And then I thought - "Why not both? Why not combine the two and create a binary tree where each node contains a 'number' ...
533 views

### Find an approximate argmax using only approximate max queries

Consider the following problem. There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query ...
• 2,803
1 vote
911 views

### Amortized analysis of red-black trees

Is there an analysis of red-black trees using amortized analysis? I saw it mentioned somewhere as an example of amortized analysis but all the proofs that I know use a global approach ("black height") ...
144 views

### Treewidth of two complete binary trees joined at their leaves

Let $T$ be a complete binary trees on $n$ nodes. Let $G'$ be the graph that consists of two disjoint copies of $T$. For a leaf $x \in T$, let $x_1, x_2$ be the two copies of it in $G'$. Then, let $G$ ...
• 79
296 views

### What are the must-read search trees paper?

I would like to ask a help from researchers who conduct a research in an area of search trees. Could you please write the list of the must-read papers and most recent papers which are important to ...
• 303
1 vote
191 views

### Is "Binary Interval Tree" NP-hard? [closed]

The input is set of (disjoint) intervals $I$. The output should be the following rooted binary tree. Each leaf node corresponds to an interval from $I$. Each interior node contains an interval which ...
• 11
282 views

### Inexact labelled binary tree matching

Does anyone recognise the following problems? Do they have names? Are they hard? If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard ...
• 11.5k
957 views

### Binary Search for optimisation problems

This maybe is either a question out of place or it is a very elementary one. I wonder what kind of optimization problems can be solved by Binary Search. Looking around some coding competitions, there ...
• 121
224 views

### Algorithms for tree rotation

What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest ...
1 vote