2-3-4-Trees |
|
A 2-3-4-tree is a generalisation of a [2-3-tree].
An interior fork-node has the following structure:
The keys in fork nodes are used to determine which subtree to descend when searching and inserting. When a new element is added, it may make the parent fork-node full. If the parent is already full, it can be split, rather as for [2-3-trees], and splits may propagate farther up the tree. An alternative method (e.g. Sedgewick 1990 p216) is to split any 4-nodes encountered during the descent of the 2-3-4-tree. ---->[|, |] --->[|, |, |] | | | | | | | | | | | | | | [|, |] T [|, |, |, |] -- 4-node T | | | | | | | | | | | | | | | C D | | | | | A B C D | [|, |] | | | | A B Before After There may still be 4-nodes after this process, e.g. ---->[|, |, |] --->[|, |, |, |] | | | | | | | | | | | | | | | | | | | | [|, |] T U [|, |, |, |] -- 4-node T U | | | | | | | | | | | | | | | C D A B C D | | [|, |] | | | | A B Before Afterbut none of the 4-nodes can have another 4-node as parent! This means that insertion has only "local" effects; no further action is necessary, higher up the 2-3-4-tree, after a new element has been added. It can be thought of as a 2-3-tree where the over-full (3+1)-nodes are not split immediately, but rather exist for a time as 4-nodes, and are split during some later insertion(s). Notes
© L.A. 1986, Dept. Computer Science, Monash University, Australia 3168. |
|
|