The first set() method starts by obtaining the position to the key within the node. If the key was found (index >= 0), the corresponding entry is retrieved, the value updated, and the old value returned. If the key wasn’t found, then it might need to be inserted, but then again it might also exist within a child node. This logic is handled by the second set() method.
The second set() method first determines whether the node is a leaf. If it is, then the key doesn’t exist anywhere in the tree and is therefore inserted along with the value as a new entry, and the size of the map is incremented accordingly. If the node has children, however, the appropriate child is found and a recursive call is made to the first set() method. In this case, if after insertion the child becomes full, it will need to be split:
public Object set(Object key, Object value) { int index = indexOf(key);
if (index >= 0) {
return ((Entry) _entries.get(index)).setValue(value);
}
return set(key, value, -(index + 1));
}
private Object set(Object key, Object value, int index) { if (isLeaf()) {
_entries.insert(index, new Entry(key, value)); ++_size;
return null;
}
Node child = ((Node) _children.get(index));
Object oldValue = child.set(key, value);
if (child.isFull()) { child.split(this, index);
}
return oldValue;
}
The only other method on the node — traverse() — is used for iteration. This method adds all the entries in the tree into a list. It starts by adding all nondeleted entries in the current node. It then recursively calls each of its children to do the same. This is essentially a pre-order traversal (it is also possible to implement an in-order traversal, an exercise left to the reader):
public void traverse(List list) {
assert list != null : “list can’t be null”;
Iterator entries = _entries.iterator();
for (entries.first(); !entries.isDone(); entries.next()) { Entry entry = (Entry) entries.current();
if (!entry.isDeleted()) { list.add(entry);
}
}
Iterator children = _children.iterator();
