class Tree234
1: //Tree234.java
3: import java.util.Stack;
5: class Tree234
6: {
7: private Node234 root;
9: // Initializes the tree with the root node reference set to null.
10: public Tree234()
11: {
12: root = null;
13: }
15: // Inserts a new key into this tree, provided the tree doesn't already
16: // contain the same key.
17: public Node234 insert
18: (
19: Integer key,
20: Node234 node,
21: Node234 nodeParent
22: )
23: {
24: // Special case for empty tree
25: if (root == null)
26: {
27: root = new Node234(key);
28: return root;
29: }
31: // If the node argument is null, recursively call with root
32: if (node == null)
33: {
34: return insert(key, root, null);
35: }
37: // Check for duplicate key
38: if (node.hasKey(key))
39: {
40: // Duplicate keys are not allowed
41: return null;
42: }
44: // Preemptively split full nodes
45: if (node.C != null)
46: {
47: node = split(node, nodeParent);
48: }
50: // If node is not a leaf, recursively insert into child subtree
51: if (!node.isLeaf())
52: {
53: return insert(key, node.nextNode(key), node);
54: }
56: // key can be inserted into leaf node
57: node.insertKey(key);
58: return node;
59: }
61: public Node234 insert(Integer key)
62: {
63: return insert(key, null, null);
64: }
66: // Searches this tree for the specified key. If found, the node containing
67: // the key is returned. Otherwise null is returned.
68: public Node234 search(Integer key)
69: {
70: return searchRecursive(key, root);
71: }
73: // Recursive helper method for search.
74: private Node234 searchRecursive(Integer key, Node234 node)
75: {
76: if (node == null)
77: {
78: return null;
79: }
81: // Check if the node contains the key
82: if (node.hasKey(key))
83: {
84: return node;
85: }
87: // Recursively search the appropriate subtree
88: return searchRecursive(key, node.nextNode(key));
89: }
91: // Splits a full node, moving the middle key up into the parent node.
92: private Node234 split
93: (
94: Node234 node,
95: Node234 nodeParent
96: )
97: {
98: Node234 splitLeft = new Node234(node.A, node.left, node.middle1);
99: Node234 splitRight = new Node234(node.C, node.middle2, node.right);
100: if (nodeParent != null)
101: {
102: nodeParent.insertKeyWithChildren(node.B, splitLeft, splitRight);
103: }
104: else
105: {
106: // Split root
107: nodeParent = new Node234(node.B, splitLeft, splitRight);
108: root = nodeParent;
109: }
111: return nodeParent;
112: }
114: // Fuses a parent node and two children into one node.
115: // Precondition: Each of the three nodes must have one key each.
116: private Node234 fuse
117: (
118: Node234 parent,
119: Node234 leftNode,
120: Node234 rightNode
121: )
122: {
123: if (parent == root && parent.countKeys() == 1)
124: {
125: return fuseRoot();
126: }
128: int leftNodeIndex = parent.getChildIndex(leftNode);
129: Integer middleKey = parent.getKey(leftNodeIndex);
130: Node234 fusedNode = new Node234(leftNode.A);
131: fusedNode.B = middleKey;
132: fusedNode.C = rightNode.A;
133: fusedNode.left = leftNode.left;
134: fusedNode.middle1 = leftNode.middle1;
135: fusedNode.middle2 = rightNode.left;
136: fusedNode.right = rightNode.middle1;
137: int keyIndex = parent.getKeyIndex(middleKey);
138: parent.removeKey(keyIndex);
139: parent.setChild(fusedNode, keyIndex);
140: return fusedNode;
141: }
143: // Fuses the tree's root node with the root's two children.
144: // Precondition: Each of the three nodes must have one key each.
145: private Node234 fuseRoot()
146: {
147: Node234 oldLeft = root.left;
148: Node234 oldMiddle1 = root.middle1;
149: root.B = root.A;
150: root.A = oldLeft.A;
151: root.C = oldMiddle1.A;
152: root.left = oldLeft.left;
153: root.middle1 = oldLeft.middle1;
154: root.middle2 = oldMiddle1.left;
155: root.right = oldMiddle1.middle1;
156: return root;
157: }
159: private int getHeight(Node234 node)
160: {
161: if (node.left == null)
162: {
163: return 0;
164: }
165: return 1 + getHeight(node.left);
166: }
168: // Returns the height of this tree.
169: public int getHeight()
170: {
171: return getHeight(root);
172: }
174: // Searches for, and returns, the minimum key in a subtree
175: public Integer getMinKey(Node234 node)
176: {
177: Node234 current = node;
178: while (current.left != null)
179: {
180: current = current.left;
181: }
182: return current.A;
183: }
185: // Finds and replaces one key with another. The replacement key must
186: // be known to be a key that can be used as a replacement without violating
187: // any of the 2-3-4 tree rules.
188: private boolean keySwap
189: (
190: Node234 node,
191: Integer existing,
192: Integer replacement
193: )
194: {
195: if (node == null)
196: {
197: return false;
198: }
200: int keyIndex = node.getKeyIndex(existing);
201: if (keyIndex == -1)
202: {
203: Node234 next = node.nextNode(existing);
204: return keySwap(next, existing, replacement);
205: }
207: node.setKey(replacement, keyIndex);
208: return true;
209: }
211: // Returns the number of keys in this tree.
212: public int length()
213: {
214: int count = 0;
215: Stack<Node234> nodes = new Stack<Node234>();
216: nodes.push(root);
218: while (!nodes.empty())
219: {
220: Node234 node = nodes.pop();
221: if (node != null)
222: {
223: // Add the number of keys in the node to the count
224: count = count + node.countKeys();
226: // Push children
227: nodes.push(node.left);
228: nodes.push(node.middle1);
229: nodes.push(node.middle2);
230: nodes.push(node.right);
231: }
232: }
233: return count;
234: }
236: // Rotates or fuses to add 1 or 2 additional keys to a node with 1 key.
237: private Node234 merge
238: (
239: Node234 node,
240: Node234 nodeParent
241: )
242: {
243: // Get references to node's siblings
244: int nodeIndex = nodeParent.getChildIndex(node);
245: Node234 leftSibling = nodeParent.getChild(nodeIndex - 1);
246: Node234 rightSibling = nodeParent.getChild(nodeIndex + 1);
248: // Check siblings for a key that can be transferred
249: if (leftSibling != null && leftSibling.countKeys() >= 2)
250: {
251: rotateRight(leftSibling, nodeParent);
252: }
253: else if (rightSibling != null && rightSibling.countKeys() >= 2)
254: {
255: rotateLeft(rightSibling, nodeParent);
256: }
257: else // fuse
258: {
259: if (leftSibling == null)
260: {
261: node = fuse(nodeParent, node, rightSibling);
262: }
263: else
264: {
265: node = fuse(nodeParent, leftSibling, node);
266: }
267: }
269: return node;
270: }
272: // Finds and removes the specified key from this tree.
273: public boolean remove(Integer key)
274: {
275: // Special case for tree with 1 key
276: if (root.isLeaf() && root.countKeys() == 1)
277: {
278: if (root.A == key)
279: {
280: root = null;
281: return true;
282: }
283: return false;
284: }
286: Node234 currentParent = null;
287: Node234 current = root;
288: while (current != null)
289: {
290: // Merge any non-root node with 1 key
291: if (current.countKeys() == 1 && current != root)
292: {
293: current = merge(current, currentParent);
294: }
296: // Check if current node contains key
297: int keyIndex = current.getKeyIndex(key);
298: if (keyIndex != -1)
299: {
300: if (current.isLeaf())
301: {
302: current.removeKey(keyIndex);
303: return true;
304: }
306: // The node contains the key and is not a leaf, so the key is
307: // replaced with the successor
308: Node234 tmpChild = current.getChild(keyIndex + 1);
309: Integer tmpKey = getMinKey(tmpChild);
310: remove(tmpKey);
311: keySwap(root, key, tmpKey);
312: return true;
313: }
315: // Current node does not contain key, so continue down tree
316: currentParent = current;
317: current = current.nextNode(key);
318: }
320: // key not found
321: return false;
322: }
324: private void rotateLeft
325: (
326: Node234 node,
327: Node234 nodeParent
328: )
329: {
330: // Get the node's left sibling
331: int nodeIndex = nodeParent.getChildIndex(node);
332: Node234 leftSibling = nodeParent.getChild(nodeIndex - 1);
334: // Get key from the parent that will be copied into the left sibling
335: Integer keyForLeftSibling = nodeParent.getKey(nodeIndex - 1);
337: // Append the key to the left sibling
338: leftSibling.appendKeyAndChild(keyForLeftSibling, node.left);
340: // Replace the parent's key that was appended to the left sibling
341: nodeParent.setKey(node.A, nodeIndex - 1);
343: // Remove key A and left child from node
344: node.removeKey(0);
345: }
347: private void rotateRight
348: (
349: Node234 node,
350: Node234 nodeParent
351: )
352: {
353: // Get the node's right sibling
354: int nodeIndex = nodeParent.getChildIndex(node);
355: Node234 rightSibling = nodeParent.getChild(nodeIndex + 1);
357: // Get key from the parent that will be copied into the right sibling
358: Integer keyForRightSibling = nodeParent.getKey(nodeIndex);
360: // Shift key and child references in right sibling
361: rightSibling.C = rightSibling.B;
362: rightSibling.B = rightSibling.A;
363: rightSibling.right = rightSibling.middle2;
364: rightSibling.middle2 = rightSibling.middle1;
365: rightSibling.middle1 = rightSibling.left;
367: // Set key A and the left child of rightSibling
368: rightSibling.A = keyForRightSibling;
369: rightSibling.left = node.removeRightmostChild();
371: // Replace the parent's key that was prepended to the right sibling
372: nodeParent.setKey(node.removeRightmostKey(), nodeIndex);
373: }
374: }