First of all, excuse me if my English is not good, I'm still learning. I'd like to ask if someone can help me to create a B Tree in java using the data of a text archive.
Here is the data structure.
4
0,6,25
1,2,10,16
1,5,30,40
2,0,1,3,8
2,1,12,15
2,3,18,19,21
2,4,27,28
2,8,33,36,39
2,7,42,45
The first line contains the order of the tree.
In the next lines we got node data. The level, Node ID and the keys.
The image shows how the tree must be built.
This is the code I used to define the BNode class to create nodes.
`import java.util.*;
public class BNode<e extends="" comparable<e="">> {
protected static int IdGen = 1;
protected ArrayList<e> keys;
protected ArrayList<bnode<e>> childs;
protected int count;
protected int id;
protected int nivel;
public BNode(int n) {
this.keys = new ArrayList<e>(n);
this.childs = new ArrayList<bnode<e>>(n);
this.count = 0;
this.id = IdGen++;
for(int i = 0; i < n; i++) {
this.keys.add(null);
this.childs.add(null);
}
}
public boolean nodeFull(int n) {
return this.count == n-1;
}
public boolean nodeEmpty(int n) {
if(n%2 == 0)
return this.count < (n/2) - 1;
else
return this.count < (n/2);
}
public boolean searchNode(E cl, int pos[]) {
pos[0] = 0;
while(pos[0] < this.count && this.keys.get(pos[0]).compareTo(cl)<0)
pos[0] ++;
if(pos[0] == this.count)
return false;
return(cl.equals(this.keys.get(pos[0])));
}
public String toString() {
String str = String.valueOf(this.id);
str += "\t(";
for(int i=0; i<this.count; i++) {
str="" +this.keys.get(i);
if(i < this.count-1)
;
else
}
return="" str;
}
}`and this is the btree code with auxiliary methods i've done:
`import="" java.io.bufferedreader;
import="" java.io.file;
import="" java.io.filereader;
import="" java.io.ioexception;
public="" class="" btree<e="" extends="" comparable<e="">>{
private BNode<e> root;
private int orden;
private boolean up;
private BNode<e> nDes;
public BTree(int orden) {
this.orden = orden;
this.root = null;
}
public static BTree<integer> buildingTree(String filename) {
try {
File archivo = new File(filename);
BufferedReader br = new BufferedReader(new FileReader(archivo));
int orden = Integer.parseInt(br.readLine());
BTree<integer> TreeNew = new BTree<>(orden);
TreeNew.root = buildNode(br, TreeNew.orden, true);
buildHelper(TreeNew.root, br, orden,null);
br.close();
return TreeNew;
}catch(Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
}
return null;
}
private static void buildHelper(BNode<integer> node, BufferedReader br, int orden,BNode temp) throws Exception{
if(node != null) {
for(int i = 0; i<=node.count; i++) {
node.childs.add(i,buildNode(br,orden, false));
}
for(int i = 0; i<=node.count; i++) {
buildHelper(node.childs.get(i),br,orden,null);
}
}
}
private static BNode<integer> buildNode(BufferedReader br, int orden, boolean root) throws Exception {
String line = br.readLine();
if(line != null) {
String[] numbers = line.split(",");
BNode<integer> node = new BNode<integer>(orden);
node.id = Integer.parseInt(numbers[1]);
for(int i = 2; i<numbers.length; i++)="" {
="" if(node.nodefull(orden))
="" throw="" new="" exception("nodo="" lleno.");
="" int="" key="Integer.parseInt(numbers[i]);
" node.keys.add(i-2,="" key);
="" node.count++;
="" }
="" if(node.nodeempty(orden)="" &&="" !root)
="" con="" claves="" insuficientes.");
="" system.out.println(node);
="" return="" node;
="" null;
=""
="" public="" boolean="" isempty()="" this.root="=" void="" insert(e="" cl)="" up="false;
" e="" mediana;
="" bnode<e=""> pnew;
mediana = push(this.root, cl);
if(up) {
pnew = new BNode<e>(this.orden);
pnew.count = 1;
pnew.keys.set(0, mediana);
pnew.childs.set(0, this.root);
pnew.childs.set(1, nDes);
this.root = pnew;
}
}
private E push(BNode<e> current, E cl) {
int pos[] = new int[1];
E mediana;
if(current == null){
up = true;
nDes = null;
return cl;
}
else{
boolean fl;
fl = current.searchNode(cl, pos);
if(fl){
System.out.println("Item duplicado\n");
up = false;
return null;
}
mediana = push(current.childs.get(pos[0]),cl);
if(up){
if(current.nodeFull(this.orden))
mediana = dividedNode(current,mediana,pos[0]);
else{
up = false;
putNode(current,mediana,nDes,pos[0]);
}
}
return mediana;
}
}
private void putNode(BNode<e> current, E cl, BNode<e> rd, int k) {
int i;
for(i = current.count - 1; i >= k; i--) {
current.keys.set(i + 1, current.keys.get(i));
current.childs.set(i + 2, current.childs.get(i + 1));
}
current.keys.set(k, cl);
current.childs.set(k + 1, rd);
current.count++;
}
private E dividedNode(BNode<e> current,E cl,int k){
BNode<e> rd = nDes;
int i, posMdna;
posMdna = (k <= this.orden/2) ? this.orden/2 : this.orden/2+1;
nDes = new BNode<e>(this.orden);
for(i = posMdna; i < this.orden-1; i++) {
nDes.keys.set(i-posMdna,current.keys.get(i));
nDes.childs.set(i-posMdna+1,current.childs.get(i+1));
}
nDes.count = (this.orden - 1) - posMdna;
current.count = posMdna;
if(k <= this.orden/2)
putNode(current,cl,rd,k);
else
putNode(nDes,cl,rd,k-posMdna);
E median = current.keys.get(current.count-1);
nDes.childs.set(0,current.childs.get(current.count));
current.count--;
return median;
}
public boolean search(E cl) {
return searchHelper(this.root, cl);
}
private boolean searchHelper(BNode<e> e, E cl) {
int pos[] = new int[1];
if(e.searchNode(cl, pos)) {
System.out.printf("%s se encuentra en el nodo %d, posicion %d \n", cl.toString(),e.id,pos[0]);
return true;
}
boolean temp = false;
for(int i=0; i<=e.count; i++) {
if(e.childs.get(i) != null)
temp = searchHelper(e.childs.get(i), cl);
if(temp)
return temp;
}
return false;
}
public String toString() {
String str = "ID Nodo\tClaves Nodo\tId Padre\tId Hijos\n";
if(!isEmpty())
str+= writeTreeFamily(this.root,null);
return str;
}
private String writeTree(BNode<e> node) {
String str = "";
if(node != null) {
str += node.toString() + "\n";
for(int i = 0; i<=node.count; i++)
str += writeTree(node.childs.get(i));
}
return str;
}
private String writeTreeFamily(BNode<e> node, BNode<e> ancestor) {
String str = "";
if(node != null) {
str += node.toString() + "\t\t ";
if(ancestor != null)
str += ancestor.id + "\t";
else
str += "--\t";
if(node.childs.get(0) != null) {
str += "[ ";
for (int i = 0; i<=node.count; i++) {
if(node.childs.get(i) != null) {
str += node.childs.get(i).id;
if (i < node.count - 1)
str += ", ";
}
}
str +=" ]\n";
}else
str += "--\n";
for(int i = 0; i<=node.count; i++)
str += writeTreeFamily(node.childs.get(i), node);
}
return str;
}
}`
What I have tried:
I need to use the static method buildingTree(). There is nothing wrong creating nodes, but when it comes to asocciate them with their parents the nodes 4, 8 and 7 are set as node 0 childs instead of node 5 childs. How can I fix this?
Submit an article or tip