Questions tagged [binary-trees]

The tag has no usage guidance.

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

On the number of optimal prefix-free binary codes [closed]

Let $T$ be a text of length $L$ containing the symbols $$\mathcal{A}=\{a_1, a_2, \ldots, a_n\},$$ where each symbol appears at least once and no other symbol appears in $T$. Define the weights $$\...
Riccardo's user avatar
1 vote
0 answers
77 views

Prune length distribution of random binary tree

Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...
user152789811's user avatar
0 votes
0 answers
121 views

Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones

We have a sorted list of $n$ numbers and we shall create a BST for these numbers. We create a random sequence of zeroes and ones of length $n$. We shall make use of this random binary sequence to form ...
Vk1's user avatar
  • 137
2 votes
0 answers
88 views

When did self-balancing binary search trees become known outside the soviet union?

According to wikipedia, the AVL tree was first published in 1962 by Soviet scientists Adelson-Velsky and Landis. The earliest self-balancing binary search tree I can find by a non-soviet block ...
Mike Izbicki's user avatar
  • 1,073
2 votes
0 answers
140 views

Drawing rooted binary (search) trees

I am looking for an (elegant, fast, etc.) algorithm to draw a binary tree, where the root is distinguished, as well as the left and right children of each node. A typical example is a binary search ...
Bruno's user avatar
  • 4,504
0 votes
0 answers
122 views

Algorithms and approximations for optimal offline binary tree operations

Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted ...
Mario Carneiro's user avatar
5 votes
0 answers
164 views

Height of AVL tree with random elements

I know that for an AVL tree of N nodes, the depth of the tree is bounded by $$ \log_2(N + 1) -1 \leq height \leq c \log_2(N + 2) + b$$ where $c,b$ are taken from the golden ratio linked to the worst ...
Binou's user avatar
  • 171
6 votes
0 answers
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 ...
AmeerJ's user avatar
  • 679
-1 votes
1 answer
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' ...
Stephanus Tavilrond's user avatar
10 votes
1 answer
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 ...
Thomas's user avatar
  • 2,803
1 vote
1 answer
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") ...
Martin Hofmann's user avatar
2 votes
1 answer
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$ ...
Chris's user avatar
  • 79
10 votes
1 answer
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 ...
rbtrht's user avatar
  • 303
1 vote
0 answers
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 ...
Esantin's user avatar
  • 11
7 votes
1 answer
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 ...
Jukka Suomela's user avatar
2 votes
0 answers
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 ...
Mario's user avatar
  • 121
3 votes
1 answer
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 ...
Mario Carneiro's user avatar
1 vote
1 answer
92 views

Are there published algorithms for on-line creation of AVL trees from ordered streams?

Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time. More specifically this is possible using only O(log n) additional ...
David C's user avatar
  • 31
0 votes
2 answers
1k views

Pre order traversal of an array [closed]

I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time? I am facing a problem where I have about 8 million elements in a file that ...
David Carpenter's user avatar