BTree implementation (Java)

The node of the BTree

import java.util.ArrayList;
import java.util.List;

public class BTreeNode<T> {
    private int n;//the number of keys currently stored in node x
    private List<T> keys = new ArrayList<>();//the x.n keys themselves, x.key1;x.key2;...;x.keyx.n, stored in nondecreasing order, so that x.key1<=x.key2<=x.keyx.n
    private boolean leaf;//x.leaf , a boolean value that is TRUE if x is a leaf and FALSE if x is an internal node
    private List<BTreeNode<T>> nodes = new ArrayList<>();//Each internal node x also contains x.n+1 pointers x.c1;x.c2;...;x.cx.n+1 to its children. Leaf nodes have no children, and so their ci attributes are undefined

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }

    public List<T> getKeys() {
        return keys;
    }

    public boolean isLeaf() {
        return leaf;
    }

    public void setLeaf(boolean leaf) {
        this.leaf = leaf;
    }

    public List<BTreeNode<T>> getNodes() {
        return nodes;
    }

}

BTree

import java.util.HashMap;
import java.util.Map;

public class BTree<T extends Comparable<T>> {
    private BTreeNode<T> root;
    private int h;//All leaves have the same depth, which is the tree's height h
    /**
     * a. Every node other than the root must have at least t-1 keys. Every internal
     * node other than the root thus has at least t children. If the tree is nonempty,
     * the root must have at least one key.
     * b. Every node may contain at most 2t-1 keys. Therefore, an internal node
     * may have at most 2t children. We say that a node is full if it contains exactly
     * 2t-1 keys.2
     * The simplest B-tree occurs when t=2. Every internal node then has either 2,
     * 3, or 4 children, and we have a 2-3-4 tree. In practice, however, much larger values
     * of t yield B-trees with smaller height
     */
    private int t;//Nodes have lower and upper bounds on the number of keys they can contain. We express these bounds in terms of a fixed integer t>=2 called the minimum degree of the B-tree

    public static final int NODE_POINTER = 0;

    public static final int KEY_INDEX = 1;

    public BTree() {
        this.createBTree();
    }

    private void createBTree(){
        BTreeNode x = new BTreeNode<T>();
        x.setLeaf(true);
        x.setN(0);
        this.root = x;
    }

    private void splitChild(BTreeNode<T> x, int i){
        BTreeNode<T> z = new BTreeNode<T>();
        BTreeNode<T> y = x.getNodes().get(i);
        z.setLeaf(y.isLeaf());
        z.setN(t-1);
        for (int j = 0; j<t-1;j++){
            T key = y.getKeys().get(t);
            z.getKeys().add(key);
            y.getKeys().remove(key);
        }
        if (!y.isLeaf()){
            for (int j = 0; j<t;j++){
                BTreeNode<T> node = y.getNodes().get(t);
                z.getNodes().add(node);
                y.getNodes().remove(node);
            }
        }
        y.setN(t-1);
        x.getNodes().add(i+1,z);
        T key = y.getKeys().get(t-1);
        x.getKeys().add(i,key);
        y.getKeys().remove(key);
        x.setN(x.getN() + 1);
    }

    public void insertKey(T key) {
        BTreeNode<T> r = this.root;
        if (r.getN() == 2 * t - 1){
            BTreeNode<T> s = new BTreeNode<>();
            this.root = s;
            s.setLeaf(false);
            s.setN(0);
            s.getNodes().add(r);
            this.h = this.h + 1;
            splitChild(s,0);
            insertKeyNonFull(s,key);
        }else {
            insertKeyNonFull(r, key);
        }
    }

    public boolean remove(T key){
        if (search(this.root,key) == null){    //not exist
            return false;
        }
        if (this.root.getN() == 1 && this.root.isLeaf()){    //handle the special case
            clear();
            return true;
        }
        recursiveRemove(this.root, key);
        if (this.root.getN() == 0 && this.getRoot().getNodes().size() > 0){
            this.root = this.root.getNodes().get(0);
            this.h = this.h - 1;
        }
        return true;
    }

    private void clear(){
        this.root = null;
    }

    private void recursiveRemove(BTreeNode<T> node, final T key){
        int i = 0;
        while (i < node.getN() && key.compareTo(node.getKeys().get(i)) > 0){
            i++;
        }
        if (i < node.getN() && key.compareTo(node.getKeys().get(i)) == 0){
            if (node.isLeaf()){    //node is a leaf node
                //delete the key from the node
                node.setN(node.getN() - 1);
                node.getKeys().remove(i);
                return;
            }else {    //node is an inner node
                BTreeNode childPrev = node.getNodes().get(i);    //the child node of the node that is before the key
                BTreeNode childNext = node.getNodes().get(i + 1);    //the child node of the node that is after the key
                if (childPrev.getN() >= t){    //childPrev contains at least CHILD_MIN keys
                    T prevKey = (T) getPredecessor(childPrev);    //get the predecessor key of the key
                    recursiveRemove(childPrev,prevKey);
                    node.getKeys().set(i,prevKey);    //replace the key with the predecessor key
                    return;
                }else if (childNext.getN() >= t){    //childNext contains at least CHILD_MIN keys
                    T nextKey = (T) getSuccessor(childNext);    //get the successor key of the key
                    recursiveRemove(childNext, nextKey);
                    node.getKeys().set(i,nextKey);    //replace the key with the successor key
                    return;
                }
                else {    //both of the childPrev and childNext contain only CHILD_MIN-1 keys
                    mergeChild(node,i);
                    recursiveRemove(childPrev,key);
                }
            }
        }else {    //key is not in the node
            BTreeNode<T> childNode = node.getNodes().get(i);    //child node containing key
            if (childNode.getN() == t - 1){    //there are only t-1 keys in the child node
                BTreeNode<T> left = i > 0 ? node.getNodes().get(i - 1) : null;    //left brother node
                BTreeNode<T> right = i < node.getN() ? node.getNodes().get(i + 1) : null;    //right brother node
                int j;
                if (left != null && left.getN() >= t){    //left brother node contains at least CHILD_MIN keys
                    //The key with the index i-1 in the parent node is moved down to the childNode
                    childNode.getKeys().add(0,node.getKeys().get(i - 1));
                    if (!left.isLeaf()){
                        //The appropriate child node in the left node is ported to the childNode
                        childNode.getNodes().add(0,left.getNodes().get(left.getN() - 1));
                    }
                    childNode.setN(childNode.getN() + 1);
                    node.getKeys().set(i,left.getKeys().get(left.getN() - 1));    //The largest key in the left node rises to node
                    left.setN(left.getN() - 1);
                }else if (right != null && right.getN() >= t){    //right brother node contains at least CHILD_MIN keys
                    //The key with the index i in the parent node is moved down to the childNode
                    childNode.getKeys().add(node.getKeys().get(i));
                    childNode.setN(childNode.getN() + 1);
                    node.getKeys().set(i, right.getKeys().get(0));//The smallest key in the right node rises to node
                    right.setN(right.getN() - 1);
                    right.getKeys().remove(0);
                    if (!right.isLeaf()){
                        childNode.getNodes().add(right.getNodes().get(0));    //The appropriate child node in the right node is ported to the childNode
                        right.getNodes().remove(0);
                    }
                }else if (left != null){    //both of the left and right node contain only CHILD_MIN-1 keys
                    mergeChild(node, i - 1);//merge with the left node
                    childNode = left;
                }else if (right != null){//merge with the right node
                    mergeChild(node, i);
                }
            }
            recursiveRemove(childNode, key);
        }
    }

    private void mergeChild(BTreeNode<T> parent, int index){
        BTreeNode<T> child1 = parent.getNodes().get(index);
        BTreeNode<T> child2 = parent.getNodes().get(index + 1);
        //merge the data of child2 into child1
        child1.setN(2 * t - 1);
        child1.getKeys().add(parent.getKeys().get(index));    //move the key with index 'index' in the parent node down
        for (int i = 0; i < t - 1; i++){
            child1.getKeys().add(child2.getKeys().get(i));
        }
        if (!child1.isLeaf()){
            for (int i = 0; i < t; i++){
                child1.getNodes().add(child2.getNodes().get(i));
            }
        }
        //delete the key with index 'index' in the parent node
        parent.setN(parent.getN() - 1);
        parent.getKeys().remove(index);
        parent.getNodes().remove(index + 1);    //delete the child2
    }

    private T getPredecessor(BTreeNode<T> node){
        while (!node.isLeaf()){
            node = node.getNodes().get(node.getN());
        }
        return node.getKeys().get(node.getN() - 1);
    }

    private T getSuccessor(BTreeNode<T> node){
        while (!node.isLeaf()){
            node = node.getNodes().get(0);
        }
        return node.getKeys().get(0);
    }

    private void insertKeyNonFull(BTreeNode<T> x, T key){
        int i = x.getN() - 1;
        if (x.isLeaf()){
            while (i >= 0 && key.compareTo(x.getKeys().get(i)) < 0){
                i = i-1;
            }
            x.getKeys().add(i + 1, key);
            x.setN(x.getN() + 1);
        }else {
            while (i >= 0 && key.compareTo(x.getKeys().get(i)) < 0){
                i = i-1;
            }
            i = i + 1;
            if (x.getNodes().get(i).getN() == 2 * t -1){
                splitChild(x, i);
                if (key.compareTo(x.getKeys().get(i)) > 0){
                    i = i + 1;
                }
            }
            insertKeyNonFull(x.getNodes().get(i), key);
        }
    }

    public Map search(BTreeNode<T> x, T k){
        int i = 0;
        while (i < x.getN() && k.compareTo(x.getKeys().get(i)) > 0){
            i = i + 1;
        }
        if (i < x.getN() && k.compareTo(x.getKeys().get(i)) == 0){
            Map<Integer,Object> result = new HashMap<>();
            result.put(BTree.NODE_POINTER,x);
            result.put(BTree.KEY_INDEX,i);
            return result;
        }else if (x.isLeaf()){
            return null;
        }else {
            return search(x.getNodes().get(i),k);
        }
    }

    public int getT() {
        return t;
    }

    public void setT(int t) {
        this.t = t;
    }

    public BTreeNode<T> getRoot() {
        return root;
    }
}