хорошая ADT для реализации BTREE

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

Я внедрил BTree несколько дней назад с LinkedList (удалите 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 
    }


}