When to choose RB tree, B-Tree or AVL tree?

data-structures tree b-tree avl-tree red-black-tree
Palladin picture Palladin · Oct 19, 2009 · Viewed 28.8k times · Source

As a programmer when should I consider using a RB tree, B- tree or an AVL tree? What are the key points that needs to be considered before deciding on the choice?

Can someone please explain with a scenario for each tree structure why it is chosen over others with reference to the key points?

Answer

blwy10 picture blwy10 · Oct 19, 2009

Take this with a pinch of salt:

B-tree when you're managing more than thousands of items and you're paging them from a disk or some slow storage medium.

RB tree when you're doing fairly frequent inserts, deletes and retrievals on the tree.

AVL tree when your inserts and deletes are infrequent relative to your retrievals.

Related questions

Max and min number of keys in a B-tree

What is the maximum and minimum number of keys that can be stored in a B-tree of order 128 and height 3? For the maximum, here's what I did: You have a single root node. The maximum children a root node can …

Read More
Difference between B-Trees and 2-3-4 Trees

What is the difference between B-Trees and 2-3-4 Trees? Also, how would you find the maximum and minimum height of each?

Read More
Advantage of B+ trees over BSTs?

I'm learning about B+ trees in a class about databases and I was wondering what concrete advantages B+ trees would give over Binary Search Trees? It seems like they both have O(logN) average complexity for most operations of note …

Read More