BTree вставка - Java

Question

Я написал код вставки в Java для B-дерева, но мое дерево не инициализировано правильно, и я не знаю, в чем проблема

Например, ввод: ABCDGHKMRWZ

требуемый вывод -

        D
      /   \
     /     \        
    /       \
   B        HM
  / \       /|\
 /   \     / | \
A     C   G  K  RWZ

с D, являющимся родителем B, и HM, HM и B являются потомками D и т. Д.

Но вместо этого я получил следующий вывод:

          D
         / \
        /   \
       /     \
      /       \        
     /         \
    B           HM
   /|\ \        /|\
  / | \ \      / | \    
 A  C G  K    G  K  RWZ

Когда K и G - дети B и HM, B - родитель G, а HM - родитель K.

Вот мой код:

public void insert(String key){
    //this method finds the node to be inserted as 
    //it goes through this starting at root node.
    BTreeNode r = this.root;

    //if it is full
    if(r.count == 2*order - 1)
    {
        //create a new empty node
        BTreeNode s = new BTreeNode(order,null);

        s.leaf = false;
        s.count = 0;
        s.child[0] = r;
        this.root = s; 

        split(s,0,r); //split root

        nonfullInsert(s, key); //call insert method
    }
    else
        nonfullInsert(r,key); //if its not full just insert it
}

public void split(BTreeNode s, int i, BTreeNode r){
    BTreeNode z = new BTreeNode(this.order,null);
    z.leaf = r.leaf; //set boolean to be the same as y

    for(int j = 0; j < this.order - 1; j++){
        z.key[j] = r.key[j+this.order];
        z.count++;
    }

    // if not leaf we have to reassign child nodes.
    if(!r.leaf){
        for(int k = 0; k < this.order; k++){
            z.child[k] = r.child[k+this.order];
        }
    }

    r.count = this.order - 1; //new size of y

    // rearranging the child nodes
    for(int j = s.count ; j> i ; j--){
        s.child[j+1] = s.child[j]; //shift children of x
    }
    s.child[i+1] = z;

    for(int j = s.count; j> i; j--){
        s.key[j + 1] = s.key[j]; // shift keys
    }

    //push the value up into the root.
    s.key[i] = r.key[this.order-1];
    r.key[this.order-1 ] = "";

    for(int j = 0; j < this.order - 1; j++)
        r.key[j + this.order] = ""; //'delete' old values

    s.count++;  //increase count of keys in s
    r.parent=s;
    z.parent=s;
}

public void nonfullInsert(BTreeNode s, String key){
    int i = s.count; //i is number of keys in node x

    if(s.leaf){
        while(i >= 1 && key.compareTo(s.key[i-1]) < 0){
            //shift values to make room for the new one
            s.key[i] = s.key[i-1]; 
            i--;
        }

        s.key[i] = key; //assign the value to the node
        s.count++;
    }

    else{
        int j = 0;
        while(j < s.count  && key.compareTo(s.key[j]) > 0)          
            j++;

        if(s.child[j].count == order*2 - 1){
            split(s,j,s.child[j]);

            if(key.compareTo(s.key[j]) > 0){
                j++;
            }
        }
        nonfullInsert(s.child[j],key);
    }
}

Буду очень признателен за вашу помощь!