Talk:2–3–4 tree

isomorphism to red-black trees

The article currently says that "red-black trees are isomorphic to 2-3-4 trees" and "for every 2-3-4 tree there exists at least one and at most one equivalent red-black tree". But I'm pretty sure this is wrong; for example, consider the 2-3-4 tree consisting of a single 3-node, with values 0 and 1. Aren't there _two_ different ways to represent this as a red-black tree? KyeShi (talk) 23:22, 14 April 2024 (UTC)

Yes, the article was wrong and seems to have arrived in that state via a series of unfortunate edits, originally speaking of an "isometry" that was then replaced by "isomorphism", with the "at most one" phrase added later. I've gone ahead and fixed the description of the correspondence using the explanation by Sedgewick, and removed the claims about 2-3-4 trees being harder to implement than red-black trees (that as far as I can tell are not in the Sedgewick reference, which is about the difficulty of implementing red-black trees).

Noamz (talk) 07:43, 21 April 2024 (UTC)

Move article?

Shouldn't this article be at 2-3-4 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

I'm planning to expand the article to include a walkthough of all the 2-3-4 tree operations, a la red-black tree. I'll put the draft-in-progress below for comment. —Ghakko 13:41, 27 July 2005 (UTC)

Operations

Lookup

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

Don't mean to be harsh, but this isn't a 2-3-4-tree. Over Christmas I will have a go at improving this.

• Split 4-nodes 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.
  • 2-node leaf insertion (2 cases).
    • 
  • 3-node leaf insertion (3 cases).
    • 
  • 4-node leaf insertion (4 cases).

You can never actually insert at a 4-node, because it would have been split by the node before. This is trivally wrong as it generates 5-nodes.

• • • 

131.111.8.104 03:40, 29 November 2005 (UTC)

Deletion

• Find node to delete, then find in-order successor if any. (Any 4-nodes encountered should be split first, to reduce the number of special cases.)
• Delete from successor, heeding the following cases:
  • 3-node? Shrink to 2-node.
  • 2-node at root? Tree becomes empty.
  • 2-node with sibling, sibling is a 3-node? Redistribute.
  • Otherwise? Merge.
    • Merge leaves hole in parent? Recurse, treating parent as new deletee.

Analysis

The height of a 2-3-4 tree with $n\,\!$ elements is $O(\log {n})\,\!$.

• Worst case is a tree of 2-nodes.
• Suppose the height of the tree is $h\,\!$.
• $n\geq 1+2+\ldots +2^{h-1}$
• $n\geq 2^{h}-1$
• $\log _{2}({n+1})\geq h$

• Best case is a tree of 4-nodes: $O(\log _{4}{n})={\frac {1}{2}}\ O(\log {n})\,\!$. —Preceding unsigned comment added by 84.196.239.127 (talk) 12:57, 18 August 2008 (UTC)

Implementation

I was thinking of writing an implementation of a 2-3-4 tree using the object-oriented 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

Need citation for original paper.

External links

The link to "2–3–4 Trees: A Visual Introduction, 2017" seems to be dead. — Preceding unsigned comment added by 89.179.246.152 (talk) 05:52, 1 November 2022 (UTC)