New answers tagged data-structures
1
vote
Accepted
Calculating number of inversions in array using AVL Finger Tree
I think there is something wrong with the definition of $TreeRank(x)$. Shouldn't it be define as the position of $x$ among the inserted items in the tree and not $A$ entirely? Otherwise, it will not ...
- 1,403
-1
votes
If inorder traversal of a tree is in ascending order will the tree definitely be a BST?
Yes, another way is to think about the In-order Traversal. You go Left-Root-Right. Well a property of BST is the left node is less than Root and right node is greater than Root. By going in the ...
6
votes
Accepted
n points in 2d plane and a method(a,b) that returns all points closer to 0 than (a,b)
This is equivalent to finding all the points in a query half-plane, which has a cute, non-obvious solution in terms of convex layers, using fractional cascading to speed up moving from layer to layer.
- 5,154
0
votes
Why does the formula floor((i-1)/2) find the parent node in a binary heap?
If you look at the indices of nodes in a binary heap, left child index is always an odd number, and right is always even.
e.g.
...
- 101
2
votes
Accepted
A nearest neighbor data structure for meshes
It suffices to store all of the triangles from all of the meshes in a nearest-neighbor data structure for triangles. Then, given a point P, find the nearest triangle, check which mesh that triangle ...
D.W.♦
- 141k
2
votes
Looking for the English name of algorithm using a precomputed array for interval sum computation
The correct term is Prefix Sum. See e.g. https://en.wikipedia.org/wiki/Prefix_sum
- 2,375
2
votes
Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?
I believe that no faster algorithm is known, at least if you are interested in computing both tableaux. Dan Romik shows in his paper The Number of Steps in the Robinson-Schensted Algorithm that on ...
- 270k
1
vote
Dictionary with sets as keys where lookup can be set intersection
My understanding: You might have three values in the table with keys (a, b), (a, c), (b, c). When you lookup (d, e, c) you want the values for the keys (a, c) and (b, c) containing a “c”.
First you ...
- 25.2k
1
vote
Dictionary with sets as keys where lookup can be set intersection
Unfortunately, no, this isn't achievable (at least not if you want to handle arbitrary sets as keys).
The reason is simple: if $N$ denotes the number of elements in a key set, then it takes $O(N)$ ...
D.W.♦
- 141k
2
votes
Why does the formula floor((i-1)/2) find the parent node in a binary heap?
Levels by levels, the indexes of a binary heap are
$$0\\1\ \ \ \ \ \ \ \ \ \ \ \ \ 2\\3\ \ \ \ \ \ 4\ \ \ \ \ \ 5\ \ \ \ \ \ 6\\7\ 8\ 9\ 10\,11\,12\,13\,14\\\cdots$$
and it is rather clear that the ...
- 3,910
0
votes
What is a good load factor for seperate chaining (closed addressing)?
When you look up a value in a hash table, the minimum
cost is: One calculation of the values hash code. One calculation of a location where the value would likely to be stored if it was present in the ...
- 25.2k
Top 50 recent answers are included