From: Michelangelo Grigni (mic@mathcs.emory.edu)
Date: Sun Feb 05 2012 - 11:13:53 EST
When you say "at each position are 2 nodes", I'm not sure what you mean. For me, each node is a position in the 2-3 tree, which may hold multiple keys (the keys are the data from the user). I'll guess you mean that each node is a 3-node, holding 2 keys. If every node on the insertion path is a 3-node, then the result is that each will split (from bottom up, each sends a key up) until finally we split the root, resulting in a height increase. The result is one new 2-node at the root, and a pair of 2-nodes where each 3-node (on the insertion path) used to be. On the other hand, if we insert under a 2-node (is that what you meant?) they all we do is convert that one 2-node to a 3-node. For red-black examples like this, see the last two animations on this page, especially when N approaches a power of 2: http://algs4.cs.princeton.edu/33balanced/ YW writes: > In a 2-3 tree, when we consider an extreme situation that at each > position there are two nodes. Now we want to insert a new node, > how could the tree remain perfectly balanced?
This archive was generated by hypermail 2.1.4 : Wed Apr 04 2012 - 17:34:17 EDT