Talk:2–3–4 tree
WikiProject Computer science  

Move article?[edit]
Shouldn't this article be at 234 tree instead, with the plural linking to the singular? Enochlau 20:34, 1 Jun 2005 (UTC)
 Agreed. I'll put up a request for a page move. —Ghakko 30 June 2005 09:26 (UTC)
Draft[edit]
I'm planning to expand the article to include a walkthough of all the 234 tree operations, a la redblack tree. I'll put the draftinprogress below for comment. —Ghakko 13:41, 27 July 2005 (UTC)
Operations[edit]
Lookup[edit]
To find an element, we look for it in the root; if it's not there, we descend into the child whose interval the element is in and repeat. If we encounter an empty child, the element is not present in the tree.
Insertion[edit]
Don't mean to be harsh, but this isn't a 234tree. Over Christmas I will have a go at improving this.
 Split 4nodes on way down (splitting root node heightens tree by one).
You don't do this, instead you put the middle element into the node above and point it to the other two elements and 4 children of this node. Only the root node can add a level like this.
 Insertion is at leaf.
You can never actually insert at a 4node, because it would have been split by the node before. This is trivally wrong as it generates 5nodes.
131.111.8.104 03:40, 29 November 2005 (UTC)
Deletion[edit]
 Find node to delete, then find inorder successor if any. (Any 4nodes encountered should be split first, to reduce the number of special cases.)
 Delete from successor, heeding the following cases:
 3node? Shrink to 2node.
 2node at root? Tree becomes empty.
 2node with sibling, sibling is a 3node? Redistribute.
 Otherwise? Merge.
 Merge leaves hole in parent? Recurse, treating parent as new deletee.
Analysis[edit]
The height of a 234 tree with elements is .
 Worst case is a tree of 2nodes.
 Suppose the height of the tree is .
 Best case is a tree of 4nodes: . —Preceding unsigned comment added by 84.196.239.127 (talk) 12:57, 18 August 2008 (UTC)
Implementation[edit]
I was thinking of writing an implementation of a 234 tree using the objectoriented design pattern. I was considering Python/Java, do any of you think that would be a useful thing to include in this article? —Programmerer 19:12, 1 November 2011 (UTC)
References[edit]
Need citation for original paper.