28
votes
Accepted
Can the pre-order traversal of two different trees be the same even though they are different?
Tree Examples (image):
...
- 576
14
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 ...
- 141
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}}(...
- 9,425
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 ...
- 275k
9
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,
...
- 366
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 $...
- 29.8k
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:
...
- 1,787
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 ...
- 28.3k
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 $...
- 275k
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-...
- 38.6k
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
Depth first or breadth first ordering in binary search trees?
Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so ...
- 9,037
5
votes
Accepted
Every AVL tree may be red black tree
Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:
Every path from a given node to any of its descendant NIL nodes contains the ...
- 275k
5
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 ...
- 484
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
Why not use large $k$ in a $k$-ary tree?
BTrees are used in practice - file systems, database with $k$ for example equal 1024 or 4096, so it seems to be bigger than binary.
Probably you have not encountered need yet.
For example ternary ...
- 9,425
5
votes
How the deletion takes place in B+ Tree
Okay I understood the issue.
Properties of B+ Tree.
All leaves should be at the same depth, and the mininum element in each leaf node should be equal to depth of the tree. See the example below:
...
- 213
5
votes
Accepted
Depth first or breadth first ordering in binary search trees?
There's a paper on this: Khuong and Morin. Array Layouts For Comparison-Based Searching
They compare the Eytzinger, B-Tree, Van Emde Boas, and sorted array layouts and conclude that Eytzinger works ...
- 1,274
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 ...
- 275k
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.♦
- 156k
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,425
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
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.♦
- 156k
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.
- 275k
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 ...
- 29.8k
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 ...
- 275k
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)$.
...
- 275k
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 "...
- 21.6k
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
Only top scored, non community-wiki answers of a minimum length are eligible