Menu
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 ?
358
In computer science, a 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that can be used to implement dictionaries.
2-3 trees were developed as a data structure which supports efficient search, insertion and deletion operations. In a 2-3 tree, each tree node contains either one or two keys, and all leaves are at the same level. An interesting parameter for storage space is the number of nodes of a 2-3 tree with N keys.
In computing, binary trees are mainly used for searching and sorting as they provide a means to store data hierarchically. Some common operations that can be conducted on binary trees include insertion, deletion, and traversal.
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.
85
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
