Skip to main content
Share Your Experience: Take the 2024 Developer Survey
28 votes
Accepted

Can the pre-order traversal of two different trees be the same even though they are different?

Tree Examples (image): ...
royashcenazi's user avatar
16 votes

Why are Red-Black trees so popular?

I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures! There are some cases where you can't use B-trees at all. One ...
matklad's user avatar
  • 161
12 votes
Accepted

Why is b-tree search O(log n)?

You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$. Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(...
Evil's user avatar
  • 9,465
10 votes

Can the pre-order traversal of two different trees be the same even though they are different?

Counting argument The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes, ...
CR Drost's user avatar
  • 376
9 votes

Time Complexity to find height of a BST

Your algorithm runs in linear time on all inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number ...
Yuval Filmus's user avatar
8 votes

Can the pre-order traversal of two different trees be the same even though they are different?

Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $...
Hendrik Jan's user avatar
  • 30.7k
7 votes
Accepted

Can we do better than $O(n\log n)$ building a balanced binary tree?

If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode: ...
aelguindy's user avatar
  • 1,807
7 votes

Can we do better than $O(n\log n)$ building a balanced binary tree?

Adding to aelguindy's answer: You just can't put n unsorted items into any kind of data structure, and then enumerate them in sorted order, in better than O (n log n) total time - because if you ...
gnasher729's user avatar
  • 30.4k
6 votes

Why are Red-Black trees so popular?

Well, this is not an authoritative answer, but whenever I have to code a balanced binary search tree, it's a red-black tree. There are a few reasons for this: 1) Average insertion cost is constant ...
Matt Timmermans's user avatar
6 votes

Are Huffman trees and optimal binary search trees for solving the same problems?

Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $...
Yuval Filmus's user avatar
6 votes
Accepted

How to count in linear time worst-case?

This is a nice question. In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-...
John L.'s user avatar
  • 39k
6 votes
Accepted

Improving a ranking system with "best rank"

Each query can be implemented to run in $O(\log n)$ time by lazily propagating appropriate operators on the binary search tree. The lazy propagation technique *1, is that it is possible to perform ...
pcpthm's user avatar
  • 2,428
5 votes
Accepted

Why is this not a valid Red-Black tree?

If you go to the empty leaf from the root in the pattern [Right, Left], you get to an empty leaf encountering 1 black node. If you go [Right, Right, Left] or [Right, Right, Right], you get to an empty ...
Cricket's user avatar
  • 66
5 votes
Accepted

KD-Tree implementation with lat/lon coordinates

Short answer: No, you will not get the same results. It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into ...
Evil's user avatar
  • 9,465
5 votes

Are degree and order the same thing when referring to a B-Tree?

I have seen three ways to characterize B-tree so far: With degree of the B-tree $t$ (either minimum, as in CLRS Algorithms book, or maximum as in B-tree Visualizer). The simplest B-tree occurs ...
Mr. Tao's user avatar
  • 163
5 votes
Accepted

Balance factor changes after local rotations in AVL tree

EDIT: @Maxym's answer is correct after all and is actually equivalent. I had simply misinterpreted the notation. Leaving this answer anyway as the cited link provides a useful explanation. While @...
Gil Hamilton's user avatar
5 votes
Accepted

UCT1 Algorithm: What does "total number of simulations" mean?

The UCT1 algorithm is actually an algorithm for a multi-armed bandit. There is a machine with several arms. At each round you pull one of the arms and get some reward. Your goal is to maximize your ...
Yuval Filmus's user avatar
5 votes
Accepted

Data structure for efficient searching, when insertions and removals are only one-sided

Store the elements as a sequence, sorted by increasing timestamp. Use binary search to find the location where $\tilde{t}$ would occur if it were in the array; then you can easily find the two ...
D.W.'s user avatar
  • 161k
5 votes

Memoization without array

There are probably better examples, but here is one, off the top of my head: Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit ...
D.W.'s user avatar
  • 161k
5 votes
Accepted

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

There are $b^i$ nodes at depth $i$, and so the total number of nodes is $$ 1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}, $$ using the formula for the sum of a geometric progression.
Yuval Filmus's user avatar
5 votes
Accepted

How many rotations after AVL insertion and deletion

The obvious resource, Wikipedia, I did not find very helpful. When inserting an element at most one (single or double) rotation is needed, at the lowest point where the tree is out of balance. After ...
Hendrik Jan's user avatar
  • 30.7k
5 votes

How to find sum of maximum K elements in range in array

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices. Without preprocessing: You can extract all elements in ...
Yuval Filmus's user avatar
5 votes

How to find sum of maximum K elements in range in array

This answer refers to the version of the question in which the range $[l,r]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qn\log n)$. ...
Yuval Filmus's user avatar
5 votes
Accepted

Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$

(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly ...
integrator's user avatar
  • 1,110
5 votes

what are good data structure algorithm for fast 3D coordinates search?

There are lots of standard ones, such as: Octrees k-d trees Binary space partitioning R-trees and their variants Which one you choose would depend on the properties of your data (e.g. how "...
Pseudonym's user avatar
  • 22.2k
4 votes

Compute height of AVL tree as efficiently as possible

No. There's a $\Omega(\lg n)$ lower bound. You can't do better than $O(\lg n)$ time. In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree. Let $T_1$ be a ...
D.W.'s user avatar
  • 161k
4 votes

Delete a range of keys in a binary search tree in better than $O(n\lg n)$?

You might be interested in a data structure called TeardownTree. It supports delete_range operation that works in $O(k + \log n)$ time, where $n$ is the initial ...
kirillkh's user avatar
4 votes

improving java 8's implement to hash map using avl tree

This page on Oracle's website says: The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins ...
tsleyson's user avatar
  • 3,128
4 votes
Accepted

Question on the properties of red black trees

The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties. In the worst case scenario, the left subtree is a minimal black binary tree of height $\log n$, ...
alonkol's user avatar
  • 156
4 votes
Accepted

Number of different binary search trees storing n distinct keys?

The solution to your recurrence is $$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$ also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the ...
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible