2–3–4 tree

A 2 -3-4 - tree is in computer science, a data structure, specifically a B- tree of branching degree 2, that is, it is a tree in which each node has two, three or a maximum of four children, and according to one, two or maximum of three data items stores, which are sorted in ascending order according to the selected criterion. It thus also a special balanced search tree dar.

As all B - trees is often used for storing large amounts of data of the 2- 3-4 - tree. Searching in these trees is possible with a running time of O (log n). By skillfully inserting the 2 3-4 tree is always kept balanced.

Search

To search in a B- tree and hence also in a 2 -3-4 - tree, a simple algorithm is applied. Starting with the smallest ( leftmost ) element of the root node:

• If so, search ended.
• If no, go to 2

• If yes, branch- to the child node that is attached to the left of just checked element, set its smallest element as the active element and go back to 1.
• If not, select the next larger element in the active node as the active element and go back to 1. If there is no larger element more 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

• A node is filled with elements, until it contains three elements ( see B in the example).
• When a fourth element is to be recorded, the node is divided into a knot with two elements (JK in the example), a node with a member ( M in the example) and a central element (L in this example), which is received in the parent node (see Step 2 in the example).
• If the parent node full, the item will be passed in the tree top. Reaches the element at the root of the tree and this is already occupied with three elements, a new root is created according to the same distribution rule (see step 4 in the example).

There is another way to insert new elements, which differ from the above method differs, at which time a 4- node is split (split operation ). In this method, each found 4- node is split during traversal of the tree, so it will be passed the middle element to the top. The split operation is therefore just performed in the worst case, while the first method in the worst case log (n) must perform split operations.

The deletion of an arbitrary element can always be returned to the deletion of an element on a sheet. To this end, you realize the position of the element within the node. If the position i, so the sheet is in the subtree of node i searched, located furthest to the right, there you swapped the largest element with the element to be deleted. Now only the element of the sheet needs to be deleted, with three cases must be distinguished:

• The sheet has more than one element. In this case, the element can be easily removed.
• The leaf contains only one element. In a neighbor node (node ​​with the same previous ), there are at least two elements. It can be borrowed an element from the neighboring nodes. The key is moved to the previous node, the previous element of the element to be deleted is moved to the position and replaces it.
• The sheet has only one element. The neighboring nodes have only one element. The item is removed and its predecessor element will be merged with a neighboring element. If the parent node itself has only a single element, the same operation is carried out at a higher level.

Variants

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