Question

What data structure should I use to implement a BTree? Why?

No correct solution

OTHER TIPS

You can create a btree node using following class.. it is having 7 keys and 8 pointers. u can change it according to the definition of btree node and perform operations on it

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];
   }
}
class Node {
   int data;
   Node left;
   Node right;
}

class BNode {
   Node[] nodes;
}

This way you will have pointers to every node of the BNode to point to the right and left subtree....

I implemented BTree in a few days ago with LinkedList (delete O(1), insert O(1)). I will show you my code. Here is my BNode structure:

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 
    }


}
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top