28
votes
Accepted
Can the pre-order traversal of two different trees be the same even though they are different?
Tree Examples (image):
...
- 586
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,
...
- 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 ...
- 281k
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 $...
- 31.5k
6
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 ...
- 31.5k
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-...
- 39.2k
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 ...
- 281k
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)$.
...
- 281k
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 "...
- 24.9k
5
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,962
4
votes
Accepted
How many node does the final B-tree have?
Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children.
If we imagine to construct a ...
4
votes
how does rotation works in AVL trees and what is a good way to understand it?
One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other.
The operation can be seen as a associative property: $T_1\...
- 31.5k
3
votes
Infix search in millions of strings
Let $\$$ be a symbol not in the alphabet, and let $\{ w_i \}_{i \in \mathbb{N}}$ be the strings you are searching from. Construct the string $S = w_1 \circ \$ \circ w_2 \circ \$ \circ \dots \circ w_n$ ...
- 4,272
3
votes
Average depth of a Binary Search Tree and AVL Tree
Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, ...
3
votes
Searching and inserting in $O(n)$ when $n$ is the size of the key
I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it).
What you describe is called a trie. For practical implementation you might take more than one bit at ...
- 2,102
3
votes
Accepted
Deletion from 2,3,4 tree
The problem you're encountering is that a deletion is cascading and triggering another deletion. In particular, you're deleting from a node with only one key. Rather than working from the bottom up, ...
- 1,168
3
votes
Accepted
Optimal data structure for sorted list
Yes, B-trees and B+ trees can be used to create a sorted array or other ordered data structure.
There is no one data structure that we can call "optimal". There are a variety of data structures that ...
D.W.♦
- 169k
3
votes
Accepted
Height of AVL Tree
The AVL invariant does not guarantee that, given any two tree paths, their length differs at most by one unit. They can differ by more than one unit, as shown by the following tree (Fibonacci AVL tree ...
- 14.7k
2
votes
Why do some search trees store all the elements in leaves, while others don't?
There are a lot of questions in here, and I'm going to pick out a few that may help answer your questions.
Why do some search trees store all elements in the leaves, while other search trees don't?
...
- 24.9k
2
votes
Why do some search trees store all the elements in leaves, while others don't?
The point is that often data is bulky and moreover of variable size (i.e., a full student record) while the keys needed to locate the data (name, enrollment number) is small and fixed size. Different ...
- 14.3k
2
votes
What do we benefit from using ternary search trees rather than binary search trees?
I'd challenge you to write the code which queries your data structure. For example, how could you determine that "SARAS" is in your tree, but "KSARAS" is not?
The problem with your data structure is ...
- 630
2
votes
Accepted
Is it possible to obtain dynamic tree with two dimensions in big matrix
Yes. Use a persistent data structure. Build a tree data structure to answer queries of the form $q(i,0)$. Then, advance $j$, updating the persistent tree data structure as you do. This will build ...
D.W.♦
- 169k
2
votes
Accepted
How is the data stored in AVL tree in a memory?
If I wanted to be really pedantic, the question would be unanswerable, as it depends on the particular implementation.
In most cases, however, the individual nodes of the tree are stored in one ...
2
votes
Accepted
Maximum depth of a B+ tree
Since you're not sure where you read it, is it possible you are misremembering slightly what the result was?
In a B+ tree, we require that every node has between $n/2$ and $n$ children. In other ...
D.W.♦
- 169k
2
votes
Can ropes (AVL trees) be interned?
I'll present two candidate solutions.
Solution #1: Associative hashing
Yes. You can associate a hash value with the contents of any binary tree data structure (including a rope). The basic idea is ...
D.W.♦
- 169k
2
votes
Efficient way to find matching date ranges?
Your question is not clear.
I am assuming you have 1000 date intervals in some set $A$ and another 1000 in set $B$ and you wish to find which intervals in $B$ lie completely inside some interval in $...
- 118
2
votes
Accepted
Two Minimax AIs playing against each other
First of all, note that in chess, white players plays first and it is a quite complicated game to build a AI for. The fact it exists several "draw" situations makes the evaluation function even more ...
- 1,788
2
votes
Accepted
Nodes in a binary search tree that span a range
I'm assuming you have parent pointers, you can probably avoid them by maintaining a couple stacks though.
Find the extremal two nodes $\ell \leq p \leq q \leq u$ and their common ancestor $a$ in $O(h)...
- 14k
Only top scored, non community-wiki answers of a minimum length are eligible