234träd

234träd, more commonly known as the 2-3-4 tree, is a self-balancing multiway search tree used to store sorted data. It is a specific form of a B-tree of order 4. In a 234-träd internal nodes contain between one and three keys and have between two and four children; all leaves are at the same depth. This uniform height ensures that the number of comparisons required to locate a key grows only logarithmically with the number of stored elements.

Operations in a 234-träd are designed to preserve balance. Insertion adds a key into the appropriate leaf; if a node already holds four keys, it is split by promoting the middle key to the parent, and this may propagate upward. If the root overflows, the tree grows in height. Deletion removes a key from a leaf or an internal node and may require borrowing a key from a neighboring node or merging nodes to maintain the minimum number of keys per node. These mechanisms keep the tree balanced and guarantee efficient access.

The 234-träd is a practical illustration of the broader B-tree concept, specifically representing B-trees of order 4. It is often used in education to demonstrate splitting and merging rules in an intuitive way. In real-world systems, B-trees are more commonly used for databases and file systems due to their good cache behavior and high fan-out, but the 2-3-4 tree remains a popular teaching tool for understanding balanced search trees and their operations. The term is especially common in Swedish literature, where 234träd is used to refer to this structure.