CODEWITHSUNDEEP
binary-tree
SuperMan
SuperMan

Reputation: 3584

Applications of 2-3-4 Tree

What are the applications of 2-3-4 trees? Are they widely used in applications for providing better performance of the applications ?

Edit : Which algorithms make the best use of 2-3-4 trees ?

Upvotes: 6

Views: 4456

Answers (2)

algodextrous
algodextrous

Reputation: 79

Answer to the applications of 2-3-4 Trees are:

•   Linux Kernel.
•   Completely Fair Scheduler
•   To keep track of Virtual Memory Segments of a Process.

Because it is similar of Red Black Trees and as @Adam said we use it in Java Collections Framework itself.

Upvotes: 0

Adam
Adam

Reputation: 512

2-3-4 trees are self-balancing and usually are usually very efficient for finding, adding and deleting elements, so like all trees they can be used for storing and retrieving elements in non-linear order. Unfortunately they tend to use more memory than other trees, because even nodes with only 2 data items still need to have enough memory to possibly store 4 of them.

This is why 2-3-4 trees are used as models for red-black trees, which are like standard BSTs except that nodes can be either red or black, and various rules exist about how to choose which colour a node is.

The key is that algorithms for searching/adding/deleting in a 2-3-4 tree are VERY similar to the ones for a red-black tree, so usually 2-3-4 trees are studied as a way of understanding red-black trees. The red-black trees themselves are quite widely used - I believe the standard Java Collections Framework tree is a red-black tree.

Upvotes: 8

Related Questions