2-3-4 tree

from Wikipedia, the free encyclopedia
2-3-4 tree

A 2-3-4-tree (also (2,4) -tree ) is a data structure in computer science , more precisely a B-tree with the minimum branching level 2 , i.e. it is a tree in which every node has two, three or has a maximum of four children and accordingly saves one, two or a maximum of three data elements that are sorted in ascending order according to the selected order criterion. At the same time, it represents a special balanced search tree .

Example of a 2-3-4 tree

Like all B-trees, the 2-3-4 tree is often used to store large amounts of data. Searching in these trees is possible with a running time of O (log n) . The 2-3-4 tree is always kept balanced by clever insertion.

Search

A simple algorithm is used to search in a B-tree and thus also in a 2-3-4 tree . Starting with the smallest (leftmost) element of the root node :

  1. Compare whether the key you are looking for is the same as the active element.
    • If so, finished your search.
    • If not, go to 2.
  2. Compare whether the key you are looking for is smaller than the active element in the active node .
    • If so, branch to the child node that is attached to the left of the element just checked, set its smallest element as the active element and go back to 1..
    • If not, mark the next larger element in the active node as the active element and go back to 1.. If there is no longer a larger element in the active node, branch to the child node to the right of the active element and set its smallest element as the active element and go back to 1.

Insert

  • A node is filled with elements until it contains three elements (see B in the example).
  • If a fourth element is to be received, the node is cleaved (engl. Split ) in a node with two elements (JK in the example), a node with an element (M in the example) and a central member (L in the example), the is added to the parent node (see step 2 in the example).
  • If the parent node is fully occupied, the element is passed up in the tree. If the element reaches the root of the tree and this is already occupied by three elements, a new root is created according to the same division rule (see step 4 of the example).

There is another way to insert new elements, which differs from the method above in the point in time at which a 4-node is split. In this method, during the traversing each node found 4 split of the tree, it is thus passed the middle element upwards. In the worst case, the split operation is carried out just once, while the first-mentioned method has to carry out log (n) split operations in the worst case.

Clear

The deletion of any element can always be traced back to the deletion of an element in a sheet . To do this, you note the position of the element within the node. If the position is i , the leaf located furthest to the right is searched for in subtree i of the node, where the largest element is swapped with the element to be deleted. Now only the element needs to be deleted from the sheet, whereby three cases must be distinguished:

  • The sheet has more than one element. In this case the element can simply be removed.
  • The sheet contains only one element. In a sibling node (node ​​with the same parent ) there are at least two elements. An element can be borrowed from the sibling node (“ stolen ” in Mehlhorn 1998 ).
  • The sheet has only one element. There are at least three siblings with the same parent (two elements). All have only one element. Two siblings (Engl. Fused fuse ).
  • The sheet has only one element. There is only one sibling node that has only one element. The operation continues recursively at a higher level.

variants

For example, 2-3-4 trees are implemented by red-black trees .

literature

  • D. Maier, SC Salveter: Hysterical B-trees . In: Information Processing Letters 12 , 1981, pp. 199-202
  • S. Huddleston, K. Mehlhorn: A New Data Structure for Representing Sorted Lists . In Acta Informatica 17 , 1982, pp. 157-184
  • Kurt Mehlhorn: data structures and efficient algorithms. Teubner Stuttgart 1988, ISBN 3-519-12255-3 .

Web links