BT.rar_b tree in java_b tree java_b-tree_tree

// B树的结点 class BTNode { static int nodes = 1; // 计输出的节点数 int m; // B树的阶 int keynum; // 结点中关键字个数 BTNode parent; // 指向双亲结点的指针 int[] key; // 关键字，0号单元不用 BTNode[] ptr; // 指向子树的指针 public BTNode(int j) { m = j; keynum = 0; parent = null; key = new int[m+1]; ptr = new BTNode[m+1]; } public BTNode(int m, int keynum, BTNode parent, int[] key, BTNode[] ptr) { this.m = m; this.keynum = keynum; this.parent = parent; this.key = key; this.ptr = ptr; } // 将p分裂为两个节点，返回新节点和需提升的关键字 public SplitResult split() { int k = 0; //System.out.println("This is the split"); BTNode child1 = new BTNode(this.m); BTNode child2 = new BTNode(this.m); BTNode parent1; if (this.parent == null) { parent1 = new BTNode(this.m); } else { parent1 = this.parent; } child1.keynum = this.keynum/2; child2.keynum = this.keynum/2; if (this.parent == null) {//System.out.println("This.parent is null"); parent1.keynum = 1; } else parent1.keynum = this.parent.keynum + 1; child1.parent = parent1; child2.parent = parent1; if ( this.parent == null || this.parent.parent == null) { parent1.parent = null; } else parent1.parent = this.parent.parent; for (int i=1; i <= this.keynum ;i++ ) { System.out.println("This is the value3: "+this.key[i]+" :"+i); } System.out.println("This is the keynum: "+this.keynum); for (int i = 1; i <= this.keynum/2 ; i++ ) { child1.key[i] = this.key[i]; System.out.println("This is the child1 value: "+child1.key[i]); } for (int i = 1; i <= this.keynum/2 ; i++ ) { child2.key[i] = this.key[i + (this.keynum+1)/2]; System.out.println("This is the child2 value: "+child2.key[i]+": "+i+" "+(this.keynum+1)/2); } if (this.parent == null) { System.out.println("This.keynum: "+this.keynum); parent1.key[1] = this.key[(this.keynum+1)/2];//this.key.length/2 } else { for (int i = 1; i <= this.parent.keynum; i++ ) { int b = this.key[this.key.length/2]; int a = this.parent.key[i]; int c = this.parent.key[i+1]; if (a <= b && b < c) { k = i; parent1.key[i] = b; } else if (a <= b && c <= b) { parent1.key[i] = this.parent.key[i]; } else if (a >= b && c > b) { parent1.key[i + 1] = this.parent.key[i]; } } } if (this.parent == null) { parent1.ptr[0] = child1; parent1.ptr[1] = child2; } else { parent1.ptr[k] = child1; parent1.ptr[k + 1] = child2; for (int i = 0; i <= this.parent.ptr.length; i++ ) { if (i < k) { parent1.ptr[i] = this.parent.ptr[i]; } else if (i > k+1) { parent1.ptr[i] = this.parent.ptr[i - 1]; } } } if (this.ptr != null) { //System.out.println("This is the ptr.length: " + this.ptr.length); for (int i = 0; i < this.ptr.length/2 ; i++ ) { child1.ptr[i] = this.ptr[i]; } for (int i = 0; i < this.ptr.length/2 ; i++ ) { child2.ptr[i] = this.ptr[i + this.ptr.length/2]; } } else { child1.ptr = null; child2.ptr = null; } //if (parent1.key.length > m) //{ //return parent1.split(); //} //else System.out.println("This is the parent1: "+parent1.key[1]+": "+parent1.keynum); return new SplitResult(parent1, this.key[this.key.length/2]); } // 遍历该节点及其子节点 public void visit() { System.out.print("Node" + BTNode.nodes + ": "); BTNode.nodes++; for(int i = 1; i <= keynum; i++) { System.out.print(key[i] + " "); } System.out.println(""); for(int i = 0; i <= keynum; i++) { if(ptr[i] != null) ptr[i].visit(); } } } // 查找结果的包装类 class SearchResult { BTNode pos; // 指向找到的结点 int i; // 在结点中的关键字序号 boolean status; // 查找成功与否 public SearchResult(BTNode pos, int i, boolean status) { this.pos = pos; this.i = i; this.status= status; } } // 分裂结果的包装类 class SplitResult { BTNode newNode; // 指向新节点 int promote; // 需提升的关键字 public SplitResult(BTNode newNode, int promote) { this.newNode = newNode; this.promote = promote; System.out.println("This is the SplitResult: "+newNode.key[1]); } } // B树的实现 class BTree { BTNode root; // B树的根节点 public BTree(BTNode t) { root = t; } // 在node.key[1...keynum]中查找val， // node.key[i] <= val < node.key[i+1] private int searchVal(BTNode node, int val) { boolean found = false; int k = 1; //System.out.println("This is the keynum: " + node.keynum); if (node != null && !found) { for (int i = 0; i <= node.keynum; i++) { if (node.key[i] == val) { k = i; found = true; } //System.out.println("this is the node length: " + node.key.length); if (found == false && node.key[i] <= val) { k = i; } } } //System.out.println("This is the position0: " + k); return k;// your implementation } // 从根节点开始查找关键字val，结果被包装成 // 一个SearchResult对象 public SearchResult search(int val) { BTNode p = root; BTNode q = null; int k = 0; boolean found = false; while (p != null && !found) { //System.out.println("Wang!"); k = this.searchVal(p, val); q = p; if ( p.key[k] == val) found = true; else p = p.ptr[k]; } //System.out.println("This is the position: " + k); return new SearchResult(q, k, found); } // 将val和child分别插入到node.key[pos+1]和node.ptr[pos+1] private void insertVal(BTNode node, int pos, int val, BTNode child) { int p; System.out.println("This is the keynum: "+node.keynum); System.out.println("This is the pos: "+pos); System.out.println("This is the value: "+val); for (int i = node.keynum; i > pos; i--) { node.key[i + 1] = node.key[i]; } node.key[pos + 1] = val; for (int i = node.keynum; i > pos; i--) { node.ptr[i+1] = node.ptr[i]; } node.ptr[pos + 1] = child; node.keynum = node.keynum + 1; } // 在B树的结点q的key[i]与key[i+1]之间插入 // 关键字val。若引起结点过大，则沿双亲链进行 // 必要的结点分裂调整，使原B树仍符合定义。 public void insert(int val, BTNode q, int i) { BTNode child = null; //System.out.println("This is the q: "+q.keynum); if ( (q.keynum + 1) < q.m) { System.out.println("wang"); this.insertVal(q, i, val, child); } else if ((q.keynum + 1) == q.m) { this.insertVal(q, i, val, child); SplitResult f = q.split(); q = f.newNode; System.out.println("This is the Jona: "+q.key[i]); } } // 在B树中插入关键字val public void insert(int val) { SearchResult sr = search(val); insert(val, sr.pos, sr.i); } // 深度遍历 public void visit() { if(root != null) root.visit(); } /** 深度遍历 本例中，你的程序应该输出 =====B-Tree Implementation===== Step1: Node1: 18 33 Step2: Node1: 18 Node2: 12 Node3: 23 33 Step3: Node1: 18 30 Node2: 12 Node3: 23 Node4: 33 48 Step4: Node1: 18 Node2: 12 Node3: 10 Node4: 15 Node5: 30 Node6: 20 23 Node7: 33 48 Step5: Node1: 18 30 Node2: 12 Node3: 10 Node4: 15 Node5: 21 Node6: 20 Node7: 23 24 Node8: 33 Node9: 31 Node10: 48 Step6: Node1: 18 30 Node2: 12 Node3: 10 Node4: