Menu
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?
235
Red black is more efficient.
AVL trees provide faster lookups than Red-Black Trees because they are more strictly balanced.
AVL trees are intended for in-memory use, where random access is relatively cheap. B-trees are better suited for disk-backed storage, because they group a larger number of keys into each node to minimize the number of seeks required by a read or write operation.
An RB tree is simply a variant of a B-tree and balancing is implemented differently than an AVL tree. AFIAK, an AVL tree has also O(1) rotation per insertion. For RB-tree and AVL - one insertion may have 1 or 0 rotations.
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.
178
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
