class Node234
1: //Node234.java
3: // Node234 class - represents a node in a 2-3-4 tree
4: class Node234
5: {
6: public Integer A, B, C;
7: public Node234 left, middle1, middle2, right;
9: public Node234
10: (
11: int keyA,
12: Node234 leftChild,
13: Node234 middle1Child
14: )
15: {
16: A = keyA;
17: B = null;
18: C = null;
19: left = leftChild;
20: middle1 = middle1Child;
21: middle2 = null;
22: right = null;
23: }
25: public Node234(int keyA)
26: {
27: this(keyA, null, null);
28: }
30: // Appends 1 key and 1 child to this node.
31: // Preconditions:
32: // 1. This node has 1 or 2 keys
33: // 2. key > all keys in this node
34: // 3. Child subtree contains only keys > key
35: public void appendKeyAndChild(Integer key, Node234 child)
36: {
37: if (B == null)
38: {
39: B = key;
40: middle2 = child;
41: }
42: else
43: {
44: C = key;
45: right = child;
46: }
47: }
49: // Returns the number of keys in this node, which will be 1, 2, or 3.
50: public int countKeys()
51: {
52: if (C != null)
53: {
54: return 3;
55: }
56: else if (B != null)
57: {
58: return 2;
59: }
60: return 1;
61: }
63: // Returns the left, middle1, middle2, or right child if the childIndex
64: // argument is 0, 1, 2, or 3, respectively.
65: // Returns null if the childIndex argument is < 0 or > 3.
66: public Node234 getChild(int childIndex)
67: {
68: if (childIndex == 0)
69: {
70: return left;
71: }
72: else if (childIndex == 1)
73: {
74: return middle1;
75: }
76: else if (childIndex == 2)
77: {
78: return middle2;
79: }
80: else if (childIndex == 3)
81: {
82: return right;
83: }
84: return null;
85: }
87: // Returns 0, 1, 2, or 3 if the child argument is this node's left,
88: // middle1, middle2, or right child, respectively.
89: // Returns -1 if the child argument is not a child of this node.
90: public int getChildIndex(Node234 child)
91: {
92: if (child == left)
93: {
94: return 0;
95: }
96: else if (child == middle1)
97: {
98: return 1;
99: }
100: else if (child == middle2)
101: {
102: return 2;
103: }
104: else if (child == right)
105: {
106: return 3;
107: }
108: return -1;
109: }
111: // Returns this node's A, B, or C key, if the keyIndex argument is
112: // 0, 1, or 2, respectively.
113: // Returns null if the keyIndex argument is < 0 or > 2.
114: public Integer getKey(int keyIndex)
115: {
116: if (keyIndex == 0)
117: {
118: return A;
119: }
120: else if (keyIndex == 1)
121: {
122: return B;
123: }
124: else if (keyIndex == 2)
125: {
126: return C;
127: }
128: return null;
129: }
131: // Returns 0, 1, or 2, if the key argument is this node's A, B, or
132: // C key, respectively.
133: // Returns -1 if the key argument is not a key of this node.
134: public int getKeyIndex(Integer key)
135: {
136: if (key.equals(A))
137: {
138: return 0;
139: }
140: else if (key.equals(B))
141: {
142: return 1;
143: }
144: else if (key.equals(C))
145: {
146: return 2;
147: }
148: return -1;
149: }
151: // Returns true if this node has the specified key, false otherwise.
152: public boolean hasKey(Integer key)
153: {
154: return key.equals(A) || key.equals(B) || key.equals(C);
155: }
157: // Inserts a new key into the proper location in this node.
158: // Precondition: This node is a leaf and has 2 or fewer keys
159: public void insertKey(Integer key)
160: {
161: if (key.compareTo(A) < 0)
162: {
163: C = B;
164: B = A;
165: A = key;
166: }
167: else if (B == null || key.compareTo(B) < 0)
168: {
169: C = B;
170: B = key;
171: }
172: else
173: {
174: C = key;
175: }
176: }
178: // Inserts a new key into the proper location in this node, and
179: // sets the children on either side of the inserted key.
180: // Precondition: This node has 2 or fewer keys
181: public void insertKeyWithChildren
182: (
183: Integer key,
184: Node234 leftChild,
185: Node234 rightChild
186: )
187: {
188: if (key.compareTo(A) < 0)
189: {
190: C = B;
191: B = A;
192: A = key;
193: right = middle2;
194: middle2 = middle1;
195: middle1 = rightChild;
196: left = leftChild;
197: }
198: else if (B == null || key.compareTo(B) < 0)
199: {
200: C = B;
201: B = key;
202: right = middle2;
203: middle2 = rightChild;
204: middle1 = leftChild;
205: }
206: else
207: {
208: C = key;
209: right = rightChild;
210: middle2 = leftChild;
211: }
212: }
214: // Returns true if this node is a leaf, false otherwise.
215: public boolean isLeaf()
216: {
217: return left == null;
218: }
220: // Returns the child of this node that would be visited next in the
221: // traversal to search for the specified key
222: public Node234 nextNode(Integer key)
223: {
224: if (key.compareTo(A) < 0)
225: {
226: return left;
227: }
228: else if (B == null || key.compareTo(B) < 0)
229: {
230: return middle1;
231: }
232: else if (C == null || key.compareTo(C) < 0)
233: {
234: return middle2;
235: }
236: return right;
237: }
239: // Removes key A, B, or C from this node, if keyIndex is 0, 1, or 2,
240: // respectively. Other keys and children are shifted as necessary.
241: public void removeKey(int keyIndex)
242: {
243: if (keyIndex == 0)
244: {
245: A = B;
246: B = C;
247: C = null;
248: left = middle1;
249: middle1 = middle2;
250: middle2 = right;
251: right = null;
252: }
253: else if (keyIndex == 1)
254: {
255: B = C;
256: C = null;
257: middle2 = right;
258: right = null;
259: }
260: else if (keyIndex == 2)
261: {
262: C = null;
263: right = null;
264: }
265: }
267: // Removes and returns the rightmost child. Two possible cases exist:
268: // 1. If this node has a right child, right is set to null, and the
269: // previous right value is returned.
270: // 2. Else if this node has a middle2 child, middle2 is set to null, and
271: // the previous right value is returned.
272: // 3. Otherwise no action is taken, and null is returned.
273: // No keys are changed in any case.
274: public Node234 removeRightmostChild()
275: {
276: Node234 removed = null;
277: if (right != null)
278: {
279: removed = right;
280: right = null;
281: }
282: else if (middle2 != null)
283: {
284: removed = middle2;
285: middle2 = null;
286: }
287: return removed;
288: }
290: // Removes and returns the rightmost key. Three possible cases exist:
291: // 1. If this node has 3 keys, C is set to null and
292: // the previous C value is returned.
293: // 2. If this node has 2 keys, B is set to null and
294: // the previous B value is returned.
295: // 3. Otherwise no action is taken and null is returned.
296: // No children are changed in any case.
297: public Integer removeRightmostKey()
298: {
299: Integer removed = null;
300: if (C != null)
301: {
302: removed = C;
303: C = null;
304: }
305: else if (B != null)
306: {
307: removed = B;
308: B = null;
309: }
310: return removed;
311: }
313: // Sets the left, middle1, middle2, or right child if the childIndex
314: // argument is 0, 1, 2, or 3, respectively.
315: // Does nothing if the childIndex argument is < 0 or > 3.
316: public void setChild(Node234 child, int childIndex)
317: {
318: if (childIndex == 0)
319: {
320: left = child;
321: }
322: else if (childIndex == 1)
323: {
324: middle1 = child;
325: }
326: else if (childIndex == 2)
327: {
328: middle2 = child;
329: }
330: else if (childIndex == 3)
331: {
332: right = child;
333: }
334: }
336: // Sets this node's A, B, or C key if the keyIndex argument is 0, 1, or
337: // 2, respectively.
338: // Does nothing if the keyndex argument is < 0 or > 2.
339: public void setKey(Integer key, int keyIndex)
340: {
341: if (keyIndex == 0)
342: {
343: A = key;
344: }
345: else if (keyIndex == 1)
346: {
347: B = key;
348: }
349: else if (keyIndex == 2)
350: {
351: C = key;
352: }
353: }
354: }