B-Tree java实现

package com.company.javaalgrithom.btree;
/**
 * @Author:yudx
 * 算法参考:数据结构(C语言版)238页
 */

import java.util.LinkedList;

import static java.lang.System.out;

public class BTree23<K extends Comparable<K>,V> {
    private  final class Node{
        int keynum;
        Node parent;
        LinkedList<Entry> entries;
        LinkedList<Node> childs;
    }
    private  final class Entry{
        K k;
        V v;
        public Entry(){}
        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }

        @Override
        public String toString() {
            return "{"+ k +
                    "," + v +
                    '}';
        }
    }
    private  final class Result{
        Node ptr;int i;boolean tag;
        public Result(Node ptr, int i, boolean tag) {
            this.ptr = ptr;
            this.i = i;
            this.tag = tag;
        }
    }
    private int degree;
    private Node root;
    public BTree23(int degree, Node root) {
        this.degree = degree;
        this.root = root;
    }
    private Result searchTree(Node T,K k){
        Node p=T,q=null;
        boolean found=false;
        int i=0;
        while(p!=null && !found){
            i=search(p,k);
            if(i>0 && eq(k,p.entries.get(i).k))found=true;
            else{
                q=p;
                p=p.childs.get(i);
            }
        }
        if(found)return new Result(p,i,true);
        else return new Result(q,i,false);
    }
    //index
    private int search(Node p,K k){
       int j=0;
       for(;j<p.keynum;j++){
           if(lt(k,p.entries.get(j+1).k))break;
       }
       return j;
    }
    public void put(K k,V v){
        Entry entry=new Entry(k,v);
        Result result=searchTree(root,entry.k);
        if(!result.tag) insertBTree(result.ptr,entry,result.i);
        else{
            result.ptr.entries.set(result.i,entry);
        }
            //result.ptr.entries.set(result.i,entry);
    }
    public void insertBTree(Node q,Entry entry,int i){
        int s;Entry x=entry;Node ap=null,tmp=null;boolean finished=false;
        while(q!=null && !finished){
            insert(q,i,x,ap);
            if(q.keynum<degree)finished=true;
            else{
                s=degree%2==0?degree/2:degree/2+1;
                x=q.entries.get(s);
                ap=new Node();
                split(q,x,s,ap);
                tmp=q;
                q=q.parent;
                if(q!=null){i=search(q,entry.k);}
            }
        }
        if(!finished){
            root=tmp;
            newRoot(q,x,ap);
        }
    }
    public void insert(Node q,int i,Entry entry,Node ap){
        q.childs.add(i+1,ap);
        q.entries.add(i+1,entry);
        if(ap != null) ap.parent=q;
        q.keynum++;
    }
    public void newRoot(Node q,Entry entry,Node ap){
        q=new Node();
        q.entries=new LinkedList<>();
        q.childs=new LinkedList<>();
        q.parent=null;
        q.entries.add(null);
        q.entries.add(entry);
        q.keynum=1;
        q.childs.add(root);
        q.childs.add(ap);
        for(int i=0;i<=q.keynum;i++){
            if(q.childs.get(i)!=null){
                q.childs.get(i).parent=q;
            }
        }
        root=q;
    }
    public void split(Node q,Entry entry,int s,Node ap){
        ap.childs=new LinkedList<>();
        ap.entries=new LinkedList<>();
        ap.entries.add(null);
        ap.entries.addAll(q.entries.subList(s+1,degree+1));
        ap.childs.add(q.childs.get(s));
        ap.childs.addAll(q.childs.subList(s+1,degree+1));
        ap.keynum=degree-s;
        q.keynum=s-1;
        for(int i=degree;i>q.keynum;i--){
            q.entries.removeLast();
            q.childs.removeLast();
        }
        for(int i=0;i<=ap.keynum;i++){
            if(ap.childs.get(i)!=null){
                ap.childs.get(i).parent=ap;
            }
        }
    }

    /*
    delete---------------------------------
     */
    public boolean deleteKey(K k){
        Result result=searchTree(root,k);
        if(result.tag) return deleteTree(result);
        else return false;
    }
    public boolean deleteTree(Result result){
        Node q=result.ptr;
        Result minResult=null;
        int i=0;
        Node node=null;
        if(q.childs.get(result.i)!=null){
            minResult=searchMinKey(q);
        }
        if(minResult!=null){
            node=minResult.ptr;
            i=minResult.i;
        }else{
            node=result.ptr;
            i=result.i;
        }
        //when the node and q refers to the same object exceptions accured
        LinkedList<Entry> tmplist=new LinkedList<>();
        tmplist.addAll(node.entries);
        q.entries.remove(result.i);
        q.entries.add(result.i,tmplist.get(i));
        return delete(node ,i);
    }
    private boolean delete(Node q,int i){
        int s,tag=0;
        Node p=null,lc,rc;
        s=degree%2==0?degree/2:(degree/2+1);
        int order=-1;
        p=q.parent;
        if(p==null){
            tag=1;
        }else{
            order=foundIndexOfParent(q,p);
            if(q.keynum>=s){
                tag=2;//delete the entry directyly
            }else{
                if(tag==0 && order<p.keynum && p.childs.get(order+1).keynum>=s){ tag=3; }
                if(tag==0 && order>0 && p.childs.get(order-1).keynum>=s){ tag=4; }
                if(tag==0 && order<p.keynum && p.childs.get(order+1).keynum==s-1){ tag=5; }
                if(tag==0 && order>0 && p.childs.get(order-1).keynum==s-1){ tag=6; }
            }
        }
        switch (tag){
            case 0:return false;
            case 1:
                removeKeyAndChild(q,i);
                if(q.keynum==1 && i==1) root=q.childs.get(0);
                q.keynum--;
                break;
            case 2:
                removeKeyAndChild(q,i);
                q.keynum--;
                break;
            case 3:
                rc=p.childs.get(order+1);
                removeKeyAndChild(q,i);
                q.entries.add(p.entries.get(order+1));
                q.childs.add(rc.childs.get(0));
                p.entries.remove(order+1);
                p.entries.add(order+1,rc.entries.get(1));
                rc.childs.remove(0);
                rc.entries.remove(1);
                rc.keynum--;
                break;
            case 4:
                lc=p.childs.get(order-1);
                removeKeyAndChild(q,i);
                q.childs.add(0,lc.childs.get(lc.keynum));
                q.entries.add(1,p.entries.get(order));
                p.entries.remove(order);
                p.entries.add(order,lc.entries.get(lc.keynum));
                removeKeyAndChild(lc,lc.keynum);
                lc.keynum--;
                break;
            case 5:
                rc=p.childs.get(order+1);
                removeKeyAndChild(q,i);
                q.entries.add(p.entries.get(order+1));
                q.keynum=q.keynum+rc.keynum;
                removeKeyAndChild(p,order+1);
                q.childs.addAll(rc.childs);
                q.entries.addAll(rc.entries.subList(1,rc.entries.size()));
                p.keynum--;
                if(p.keynum<s-1){
                    p.keynum=p.keynum+1;
                    q=p;
                    delete(q,q.keynum);
                }
                break;
            case 6:
                lc = p.childs.get(order - 1);
                lc.entries.add(p.entries.get(order));
                lc.keynum++;
                removeKeyAndChild(q, i);
                q.keynum--;
                removeKeyAndChild(p, order);
                p.keynum--;
                lc.childs.addAll(q.childs);
                q.entries.removeFirst();
                lc.entries.addAll(q.entries);
                lc.keynum += q.keynum;
                if(p.keynum < s - 1){
                    p.keynum++;
                    q = p;
                    delete(q,q.keynum);
                }
                break;
        }
        return true;
    }
    private void removeKeyAndChild(Node q,int i){
        if(i>q.entries.size()-1) return;
        q.childs.remove(i);
        q.entries.remove(i);
    }
    public int foundIndexOfParent(Node q,Node p){
        int count;
        for(count=0;p.childs.get(count)!=q;count++);
        return count;
    }
    public Result searchMinKey(Node p){
        while(p!=null && p.childs.get(0)!=null)
            p=p.childs.get(0);
        return new Result(p,1,true);
    }
    //--------------------------------------------

    private boolean lt(K k1, K k2){return k1.compareTo(k2)<0;}
    private boolean eq(K k1,K k2){return k1.compareTo(k2)==0;}
    private boolean gt(K k1,K k2){return k1.compareTo(k2)>0;}
    public void printfTree(Node root,int count){
        count ++;
        for(int i = 0;i<=root.keynum;i++){
            if(i == 0){
                out.println(root.entries.toString());
            }
            if(root.childs.get(i) != null){
                out.print("第"+count+"层第"+i+"个孩子:");
                printfTree(root.childs.get(i),count);
            }
        }
    }
    public Node getRoot(){return root;}
    public V get(K k){
        Result result=searchTree(root,k);
        return result.ptr.entries.get(result.i).v;
    }
}
class btree23test{
    public static void main(String[] args) {
        BTree23 bst=new BTree23(3,null);
        bst.put(3,"world");
        bst.put(24,"world");
        bst.put(37,"world");
        bst.put(45,"haokan");
        bst.put(50,"world");
        bst.put(53,"kanren");
        bst.put(61,"world");
        bst.put(90,"world");
        bst.put(100,"world");
        bst.put(70,"haokan");

        System.out.println("删除前：");
        bst.printfTree(bst.getRoot(),0);
        bst.deleteKey(50);
        System.out.println("删除后："+50);
        bst.printfTree(bst.getRoot(), 0);
        bst.deleteKey(53);
        System.out.println("删除后："+53);
        bst.printfTree(bst.getRoot(), 0);
        bst.deleteKey(37);
        System.out.println("删除后："+37);
        bst.printfTree(bst.getRoot(), 0);
    }
}