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
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.7k
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
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,170
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
Accepted

Maximal difference of height between two leaves in an AVL tree

We consider Fibonacci tree ([TAOCP3, Knuth98, Sect. 6.2.1]) and compute the maximal height difference in it. A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of ...
user avatar
  • 9,179
6 votes
Accepted

Is every AVL tree a BST or just BT?

Yes every AVL tree is a BST also note that every binary search tree itself is a binary tree (binary tree is basically a tree that each node has at most two child) so therefore every AVL is a binary ...
user avatar
  • 740
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

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

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

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
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 ...
user avatar
  • 66
5 votes

rope data structure - undo operation

The approach is to build a fully persistent version of the rope data structure. This then lets you keep a pointer to each version of the data structure: you have a pointer to version 1 ("hello world")...
user avatar
  • 140k
4 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 ...
user avatar
4 votes

Are degree and order the same thing when referring to a B-Tree?

Order(m) of B-tree defines (max and min) no. of children for a particular node. Degree(t) of B-tree defines (max and min) no. of keys for a particular node. Degree is defined as minimum degree of B-...
user avatar
  • 41
4 votes

Balance factor changes after local rotations in AVL tree

I found the answer myself. We know that $$b(x)=b(x')+b(y)[b(y)>0]+1$$ $$b(y′)=b(x)+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$ thus $$b(y′)=b(x')+b(y)[b(y)>0]+1+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$ ...
user avatar
  • 283
4 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 @...
user avatar
4 votes

Compute height of AVL tree as efficiently as possible

No. There's a $\Omega(\lg n)$ lower bound. You can't do better than $O(\lg n)$ time. In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree. Let $T_1$ be a ...
user avatar
  • 140k
4 votes
Accepted

AVL tree such that each insert causes rotation (single or double)

Short answer: it depends. The answer depends on what is the set of the possible elements of the AVL tree. Natural numbers, no duplicates allowed. Yes, there is an AVL tree requiring a rotation on ...
user avatar
  • 14.1k
4 votes
Accepted

Question on the properties of red black trees

The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties. In the worst case scenario, the left subtree is a minimal black binary tree of height $\log n$, ...
user avatar
  • 156
4 votes
Accepted

Zero-based array implementation with logarithmic insertion time

All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-...
user avatar
4 votes
Accepted

Insertions in Red-Black Trees

Yes, a given set can be represented by multiple red-black trees, and this works incrementally, at least some of the time. That is, there exists more than one valid red-black tree insertion algorithm, ...
user avatar
4 votes
Accepted

Should one limit the maximum level of a skip list node?

Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance. The strategy demotes (reduces the level) of a ...
user avatar
  • 11k
4 votes

BVL Balanced Tree

If you want to show that the height is $h=\mathcal O(\log(n))$ then I would suggest the following: Define $n_h$ as the minimum vertices in tree with height $h$ Then to get the minimum vertices for ...
user avatar
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: $...
user avatar
  • 27.1k

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