Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
28 votes
Accepted

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

Tree Examples (image): ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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: $$...
user avatar
  • 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}}(...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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, ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
  • 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 (...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,254

Only top scored, non community-wiki answers of a minimum length are eligible