写的匆忙 估计有BUG 修改后  会去掉这个 说明

/**
* @author shuly
* @date 2017/6/5.
*/

// hint 一日为叶，终身为叶, 最后还是要转换成 <链表存储节 | 数组> 比较快, 自己写个链表吧
// 先写一个数组的好用一点
class Config {
static int M = 8; // 写的不好请确保这是个偶数.
static int MIN_NUM = M / 2;
}

class LinkData {
LinkData next;
Entry data;
LinkData(){
next = null;
data = null;
}
}

class Node {
int m;
Node left;
Node right;
Entry[] children = new Entry[Config.M];
//LinkData children = new LinkData();
Node(int k) {
m = k;
left = null;
right = null;
}
}

abstract class Entry {
Comparable key;
}

class EntryLeaf extends Entry {
Object val;

EntryLeaf(Comparable key, Object val) {  
    this.key = key;  
    this.val = val;  
}  

}

class EntryNotLeaf extends Entry {
Node nextNode;

EntryNotLeaf(Comparable key, Node next) {  
    this.nextNode = next;  
    this.key = key;  
}

}

public class BPXTree, Value> {
private int height;
private int total;
private Node root;
// todo push
private Node leafNodeHead;

public BPXTree() {

    leafNodeHead = new Node(0);  
    root =  new Node(0);  
    leafNodeHead.right = root;  
    root.left = leafNodeHead;  
}

public int insert(Key key, Value value) {  
    if (key == null) throw new IllegalArgumentException("插入空值我操");  
    ++total;  
    Node u = insert(root, key, value, height);  
    if (u != null) {  
        Node t = new Node(2);  
        t.children\[0\] = new EntryNotLeaf(root.children\[0\].key, root);  
        t.children\[1\] = new EntryNotLeaf(u.children\[0\].key, u);  
        root = t;  
        ++height; // 树的生长  
    }  
    return 1;  
}

/\*\*  
 \* @param now   当前插入节点  
 \* @param key   key  
 \* @param value value  
 \* @param h     高度  
 \* @return 需要分裂则但会当前节点，否则是null  
 \*/  
private Node insert(Node now, Key key, Value value, int h) {  
    int j;  
    Entry tmp;

    if (h == 0) { // 叶子节点  
        tmp = new EntryLeaf(key, value);  
        for (j = 0; j < now.m; ++j) {  
            if (less(key, now.children\[j\].key)) {  
                break;  
            }  
        }  
    } else { // 非叶子节点  
        tmp = new EntryNotLeaf(key, null);  
        for (j = 0; j < now.m; ++j) {  
            if ((j + 1 == now.m) || less(key, now.children\[j + 1\].key)) {  
                Node u = insert(((EntryNotLeaf) now.children\[j++\]).nextNode, key, value, h - 1);  
                if (u == null) return null;  
                tmp.key = u.children\[0\].key;  
                ((EntryNotLeaf) tmp).nextNode = u;  
                break;  
            }  
        }  
    }  
    // 挪地方  
    for (int i = now.m; i > j; --i) {  
        now.children\[i\] = now.children\[i - 1\];  
    }  
    now.children\[j\] = tmp;  
    now.m++;  
    if (now.m < Config.M) {  
        return null;  
    }  
    return split(now);  
}

private static Node split(Node now) {  
    int base = Config.M / 2;  
    Node tmp = new Node(base);  
    now.m = base;  
    for (int j = 0; j < base; ++j) {  
        tmp.children\[j\] = now.children\[base + j\];  
        now.children\[base + j\] = null;  
    }  
    tmp.right = now.right;  
    tmp.left = now;  
    now.right = tmp;  
    return tmp;  
}

public Value query(Key key) {  
    if (key == null) {  
        throw new IllegalArgumentException("查询值是空啊");  
    }  
    return query(root, key, height);  
}

/\*\*  
 \* @param now 当前节点  
 \* @param key 插入的值  
 \* @param h   当前高度  
 \* @return key对应的value, 没有就是null;  
 \*/  
private Value query(Node now, Key key, int h) {  
    Entry\[\] children = now.children;  
    if (h == 0) {// 叶子节点  
        for (int j = 0; j < now.m; ++j) {  
            if (eq(key, children\[j\].key)) {  
                return (Value) ((EntryLeaf) children\[j\]).val;  
            }  
        }  
    } else { // 非叶子节点  
        for (int j = 0; j < now.m; ++j) {  
            if ((j + 1 == now.m) || less(key, children\[j + 1\].key)) {  
                return query(((EntryNotLeaf) children\[j\]).nextNode, key, h - 1);  
            }  
        }  
    }  
    return null;  
}

public Queue<Value> queue(Key left, Key right) {  
    Queue<Value> ans = new LinkedList<>();  
    query(root, left, right, height, ans);  
    return ans;  
}

// todo  
private void query(Node now, Key left, Key right, int h, Queue<Value> ans) {

}

/\*\*  
 \* @param key 删除的关键字  
 \* @return 删除的内容；  
 \* <p>  
 \* <p>  
 \* 切记在合并的时候 要去要别的节点，而不是自己的给别人，也不能去和自己的堂兄弟借，要找兄弟合并。  
 \* 这样才能 递归的更新 索引. 3Q  
 \*/  
public Value delete(Key key) {  
    // root 节点的size没有限制  
    Triple<Value, Boolean, Key> ans = delete(root, key, height);  
    return ans.first;  
}

/\*\*  
 \* @param now 当前节点  
 \* @param key 删除的主键  
 \* @param h   目前的高度  
 \* @return <删除的 映射值, 修改的儿子节点是否足够用,  抢的节点>  
 \* <p>  
 \* <p>  
 \* 采用自己先去抢，抢不到在让父亲节点调度的方式.  
 \*/  
public Triple<Value, Boolean, Key> delete(Node now, Key key, int h) {  
    Triple<Value, Boolean, Key> ans = new Triple<>(null, null, null);  
    if (h == 0) {  
        //叶子了  
        for (int i = 0; i < now.m; i++) {  
            if (eq(key, now.children\[i\].key)) {  
                ans.first = (Value) ((EntryLeaf) now.children\[i\]).val;  
                now.m--;  
                for (int j = i; j < now.m; j++) {  
                    now.children\[j\] = now.children\[j + 1\];  
                }  
                now.children\[now.m\] = null; // 删除吗 不可能 越界  
                break;  
            }  
        }  
    } else {  
        // 非叶子 节点  
        // 狗儿子们开始干活了.  
        for (int i = 0; i < now.m; i++) {  
            if ((i + 1 == now.m) || less(key, now.children\[i + 1\].key)) {  
                // 去吧比卡丘  
                ans = delete(((EntryNotLeaf) now.children\[i\]).nextNode, key, h - 1);

                if (ans.second) {  
                    // 操 欲求不满的东西，让我来施舍你! 妈的我 还要维护你们的链接信息，我了个去，  
                    int source;  
                    int target = i;

                    if (i + 1 == now.m && i != 0) {  
                        source = i - 1;  
                        Node sourceNode = ((EntryNotLeaf) now.children\[source\]).nextNode;  
                        Node targetNode = ((EntryNotLeaf) now.children\[target\]).nextNode;

                        for (int w = 0; w < targetNode.m; ++w) {  
                            targetNode.children\[w + sourceNode.m\] = targetNode.children\[w\];  
                        }

                        for (int s = 0; s < sourceNode.m; s++) {  
                            targetNode.children\[s\] = sourceNode.children\[s\];  
                        }  
                        targetNode.m += sourceNode.m;

                        if(sourceNode.left != null) {  
                            sourceNode.left.right = targetNode;  
                        }  
                        targetNode.left = sourceNode.left;  
                    } else {  
                        source = i + 1;

                        if (source == now.m) {  
                            // 结束了 这是root节点  
                            this.root = ((EntryNotLeaf)root.children\[0\]).nextNode;  
                            this.height--;  
                            return ans;  
                        }  
                        Node sourceNode = ((EntryNotLeaf) now.children\[source\]).nextNode;  
                        Node targetNode = ((EntryNotLeaf) now.children\[target\]).nextNode;  
                        for (int s = 0, t = targetNode.m; s < sourceNode.m; s++, t++) {  
                            targetNode.children\[t\] = sourceNode.children\[s\];  
                        }  
                        targetNode.m += sourceNode.m;  
                        targetNode.right = sourceNode.right;  
                        if(sourceNode.right != null) {  
                            sourceNode.right.left = targetNode;  
                        }  
                    }

                    // 再见我 的 小伙伴, 满足了你，牺牲了他，何必同室操戈，  
                    for (int s = source; s < now.m; s++) {  
                        now.children\[s\] = now.children\[s + 1\];  
                    }  
                    now.m--;  
                    now.children\[now.m\] = null;  
                    // 抢东西更新  
                } else if (ans.third != null && i + 1 != now.m && ans.third.compareTo((Key) now.children\[i + 1\].key) == 0) {  
                    // 借东西索引更新  
                    now.children\[i + 1\].key = updateIndexUntil(((EntryNotLeaf) now.children\[i + 1\]).nextNode, ans.third);  
                    now.children\[i\].key = ((EntryNotLeaf)now.children\[i\]).nextNode.children\[0\].key;  
                } else {  
                    now.children\[i\].key = ((EntryNotLeaf)now.children\[i\]).nextNode.children\[0\].key;  
                }  
                //now.children\[i\].key = ((EntryNotLeaf)now.children\[i\]).nextNode.children\[0\].key;  
                break;  
            }  
        }  
    }  
    ans.second = false;  
    if (now.m < Config.MIN\_NUM) { //卧槽节点不够了  
        if (now.left != null && now.left.m > Config.MIN\_NUM) {  
            // left 请给我点吧，我不行了QAQ  
            now.left.m--;  
            Entry entry = now.left.children\[now.left.m\];  
            now.left.children\[now.left.m\] = null;

            // 这个刁钻的插入操作妈的  
            for (int i = 1; i <= now.m; ++i) {  
                now.children\[i\] = now.children\[i - 1\];  
            }  
            now.children\[0\] = entry;  
            now.m++;  
            ans.third = (Key) entry.key;  
        } else if (now.right != null && now.right.m > Config.MIN\_NUM) {  
            // right 请给我点吧，我不行了QAQ  
            Entry entry = now.right.children\[0\];  
            now.right.m--;  
            for (int i = 0; i < now.right.m; ++i) {  
                now.right.children\[i\] = now.right.children\[i + 1\];  
            }  
            now.right.children\[now.right.m\] = null;

            now.children\[now.m\] = entry;  
            now.m++;  
            // 这个要更新那边 等待到LCA  
            ans.third = (Key) entry.key;  
        } else {  
            // 父亲啊，请给我做主，灭了他们其中一个要不我不满足  
            ans.second = true;  
        }  
    }  
    return ans;  
}

private Key updateIndexUntil(Node now, Key key) {  
    if (now.children\[0\].key.compareTo(key) == 0) {  
        now.children\[0\].key = updateIndexUntil(((EntryNotLeaf)now.children\[0\]).nextNode, key);  
    }  
    return (Key) now.children\[0\].key;  
}

@Override  
public String toString() {  
    return toString(root, height, "") + "\\n";  
}

private String toString(Node h, int ht, String indent) {  
    StringBuilder s = new StringBuilder();  
    Entry\[\] children = h.children;  
    if (ht == 0) {  
        for (int j = 0; j < h.m; j++) {  
            s.append(indent).append(children\[j\].key).append(" ").append(((EntryLeaf) children\[j\]).val).append("\\n");  
        }  
    } else {  
        for (int j = 0; j < h.m; j++) {  
            s.append(indent).append("(").append(children\[j\].key).append(")").append("\\n");  
            s.append(toString(((EntryNotLeaf) children\[j\]).nextNode, ht - 1, indent + "     "));  
        }  
    }  
    return s.toString();  
}

private static boolean less(Comparable k1, Comparable k2) {  
    return k1.compareTo(k2) < 0;  
}

private static boolean eq(Comparable k1, Comparable k2) {  
    return k1.compareTo(k2) == 0;  
}

private void linkOut() {  
    Node head = this.leafNodeHead;  
    while (head != null) {

        for (int i = 0; i < head.m; i++) {  
            System.out.print(head.children\[i\].key + " : " + ((EntryLeaf) head.children\[i\]).val + '\\t');  
        }  
        head = head.right;  
    }  
}

public static void main(String\[\] args) {  
    BPXTree<Integer, Long> st = new BPXTree<>();  
    for (int i = 1; i <= 20; i++) {  
        st.insert(i, (long) i);  
    }  
    Long value = st.delete(10);  
    Long pp = st.delete(9);  
    pp = st.delete(3);  
    pp = st.delete(6);  
    pp = st.delete(1);  
    pp = st.delete(4);  
    pp = st.delete(7);  
    pp = st.delete(2);  
    pp = st.delete(8);  
    pp = st.delete(5);

    pp = st.delete(11);  
    pp = st.delete(12);  
    pp = st.delete(16);  
    pp = st.delete(17);

    System.out.println("START");  
    System.out.println(st.toString());  
    System.out.println("END");  
    st.linkOut();

    pp = st.delete(18);

    System.out.println("START");  
    System.out.println(st.toString());  
    System.out.println("END");  
    st.linkOut();  
    pp = st.delete(19);  
    pp = st.delete(20);  
    pp = st.delete(13);  
    pp = st.delete(14);  
    System.out.println("START");  
    System.out.println(st.toString());  
    System.out.println("END");  
    st.linkOut();  
    pp = st.delete(15);

    System.out.println("START");  
    System.out.println(st.toString());  
    System.out.println("END");  
    st.linkOut();  
}  

}