Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

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

Tree Examples (image): ...
• 576

### 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 ...
• 161
Accepted

• 30.7k
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: ...
• 1,807

### 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 ...
• 30.4k

### 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 ...

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 $... • 278k 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-... • 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 ... • 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 ... • 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 ... • 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 ... • 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 @... • 166 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 ... • 278k 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 ... • 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 ... • 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. • 278k 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 ... • 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 ... • 278k 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)$. ... • 278k 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 ... • 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 "... • 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 ... • 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 ... • 41 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 ... • 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\$, ...
• 156
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 ...