Skip to content

Instantly share code, notes, and snippets.

@manoelf

manoelf/B.java

Created September 28, 2016 06:08
Show Gist options
  • Save manoelf/3691f23bd43b8a964427d6179f29e0e0 to your computer and use it in GitHub Desktop.
Save manoelf/3691f23bd43b8a964427d6179f29e0e0 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
B.java
@Override
public void insert(T element) {
if (element != null) {
BNode<T> node = search(element).node;
if (node != null) {
insert(node, element);
}
}
}
private void insert(BNode<T> node, T element) {
node.addElement(element);
Collections.sort(node.getElements());
if (node.isFull()) {
split(node);
}
}
private void split(BNode<T> node) {
if (node.equals(root)) {
BNode<T> newRoot = new BNode<>(node.getMaxKeys() + 1);
newRoot.addElement(getMedianElement(node));
newRoot.addChild(0, divideFirstPart(node));
newRoot.addChild(1, divideSecondPart(node));
this.root = newRoot;
} else {
T middle = getMedianElement(node);
BNode<T> parent = node.getParent();
insert(node.getParent(), middle);
int position = parent.elements.indexOf(middle);
parent.addChild(position, divideFirstPart(node));
parent.addChild(position + 1, divideSecondPart(node));
node = divideFirstPart(node);
}
}
private T getMedianElement(BNode<T> node) {
return node.getElementAt(node.size() / 2);
}
private BNode<T> divideFirstPart(BNode<T> node) {
BNode<T> newNode = new BNode<>(node.getMaxKeys() + 1);
for (int i = 0; i < node.size() / 2 - 1; i++) {
newNode.addElement(node.getElementAt(i));
}
if (!node.isLeaf()) {
for (int i = 0; i < node.getChildren().size() / 2; i++) {
newNode.addChild(i, node.getChildren().get(i));
}
}
return newNode;
}
private BNode<T> divideSecondPart(BNode<T> node) {
BNode<T> newNode = new BNode<>(node.getMaxKeys() + 1);
for (int i = 0; i > node.size() / 2 && i < node.size(); i++) {
newNode.addElement(node.getElementAt(i));
}
if (!node.isLeaf())
for (int i = 0; i > node.getChildren().size() / 2 && i < node.getChildren().size(); i++) {
newNode.addChild(i, node.getChildren().get(i));
}
return newNode;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment