b-tree - 实现 BTREE 的好 ADT

Question

我应该使用什么数据结构来实现 BTree？为什么？

Answer 1

您可以使用以下类创建一个 btree 节点。它有 7 个键和 8 个指针。你可以根据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 
    }


}