b-tree - BTREEを実装するための優れたADT

Question

BTreeを実装するにはどのデータ構造を使用する必要がありますか？なんで？

Answer 1

次のクラスを使用してbtreeノードを作成できます。7つのキーと8つのポインターがあります。uはbtreeノードの定義に従ってそれを変更し、それに対して操作を実行できます

class BTNode
{
   BTNode pointers[];
   String keys[];
   int numKeys;
   boolean leaf;

   public BTNode()  // constructor to initialize values
   {
     leaf=true;
     numKeys=0;
     keys=new String[7];
     pointers=new BTNode[8];
   }
}

Answer 2

class Node {
   int data;
   Node left;
   Node right;
}

class BNode {
   Node[] nodes;
}

このようにして、BNode のすべてのノードへのポインタが右と左のサブツリーを指すようになります....

Answer 3

数日前に LinkedList を使用して BTree を実装しました (O(1) の削除、O(1) の挿入)。私のコードをお見せします。ここに私の BNode 構造があります:

public class BTree {
    private int order;
    private BNode root;


    public BTree(int order) {
        this.order = order;
    }

    public void insert(int value){}
    public boolean delete(int value){}
    public boolean contains(int value){}
    public void print(){}

}

class BNode{
    private LinkedList<Integer> values;
    private LinkedList<BNode> children;

    public BNode(){
        init(values);
        init(children); // every bnode with order k has k+1 children 
    }


}