28
votes
Accepted
Can the pre-order traversal of two different trees be the same even though they are different?
Tree Examples (image):
...
- 566
15
votes
Why are Red-Black trees so popular?
To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question
For some kinds of binary search trees, including red-black trees but
not AVL trees, the "fixes" to ...
- 769
12
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 ...
- 121
11
votes
Time Complexity proof for Segment Tree implementation of the ranged sum problem
The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction.
Consider the segment tree given below.
Let's say that there are $3$ nodes that ...
- 243
9
votes
Accepted
Range update + range query with binary indexed trees
Suppose you had an empty array:
0 0 0 0 0 0 0 0 0 0 (array)
0 0 0 0 0 0 0 0 0 0 (cumulative sums)
And you wanted to make a range update of +5 ...
- 406
9
votes
Accepted
A median of an AVL. How to take advantage of the AVL?
If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To ...
- 269k
9
votes
Memory usage of a BST or hash table?
When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where:
$$...
- 18.8k
9
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,325
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 ...
- 269k
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
Accepted
How can one search in O(log n) time in a red-black tree?
The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are ...
- 2,209
8
votes
Accepted
B-Tree and how it is used in practice
A B-Tree is a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set for the sort of operations we're ...
- 18.8k
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 $...
- 27.2k
7
votes
Split in AVL tree with complexity $O(\log n)$
Yes, this is possible.
You can read about it in Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory", section 3.1.6, (mirror) or in the OCaml standard library, ...
- 3,200
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,777
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 ...
- 24.9k
6
votes
Accepted
(AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees?
I assume that we start labeling heights from $0$.
Actually your approach is right. You must consider the left-side (or right-side) sub-tree with the least possible amount of nodes and the right-side (...
- 360
6
votes
Accepted
kd-tree stores points in inner nodes? If yes, how to search for NN?
Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:
...
- 251
6
votes
Accepted
Don't understand one step for AVL tree height log n proof
You can continue as same as line 4 the process like that:
$$ N_h > 2N_{h-2}> 2(2 N_{h-4})>2(2(2 N_{h-6}))>\cdots$$
As you can see, the indexs are decreasing by substracting $2$ in each ...
- 2,151
6
votes
Why aren't tries generally used?
This is an interesting question. Certainly worth asking.
The choice of a data structure is very much dependent on what you want
to do with it. A more costly sophisticated structure, no matter how
...
- 19.1k
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 $...
- 269k
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-...
- 33.2k
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
Balancing a Binary Search Tree
Yes, the right subtree could be $13(10,14)$.
But notice that the article you've linked discusses the most naive version of building a Binary Search Tree, in which numbers are simply inserted into the ...
- 1,841
5
votes
Traversals from the root in AVL trees and Red Black Trees
For virtually all kinds of binary search trees, including AVL trees and red-black trees, you can implement insertion in what is called a bottom-up fashion. This involves two passes through the tree: ...
- 281
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,325
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
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 ...
- 269k
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 ...
- 8,817
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,254
Only top scored, non community-wiki answers of a minimum length are eligible