0

我试图从我之前创建的 B 树实现中创建一个 B+ 树，但我真的迷失了在这里......我尝试实现的 B 到 B+ 的唯一区别是将密钥存储在叶子上而不是删除它们。
示例：
最终 B 树
3 6 假
1 2 真
4 5 真
7 8 9 10 真

最终 B+ 树
3 6 假
1 2 真
3 4 5 真
6 7 8 9 10 真


这就是我为 B 树所拥有的（我真的不想发布整个代码，但是解释所有代码会更加困难和混乱）。我至少会欣赏一些想法......

主要

  public class BTreeTest{

public static void main(String[] args)   {
Random generator = new Random();
BTree T = new BTree(3);

final int INSERTS = 50;          // how many elements are inserted
final int VALUE_LIMIT = 1000;    // generated integers up to VALUE_LIMIT
int[] values = new int[INSERTS]; // array can be used to print insert order
                                 // or to test other methods
for (int i=0;i<INSERTS;i++){
  int val = generator.nextInt(VALUE_LIMIT);
  values[i] = val;
  T.insert(val);      
}
T.printNodes();
}}


B树节点

  public class BTreeNode{
  public int[] key;
  public BTreeNode[] c;
  boolean isLeaf;
  public int n;
  private int T; //Each node has at least T-1 and at most 2T-1 keys

  public  BTreeNode(int t){
   T = t;
   isLeaf = true;
   key = new int[2*T-1];
   c = new BTreeNode[2*T];
   n=0; 
 }

 public boolean isFull(){
   return n==(2*T-1);
 }

   public void insert(int newKey){
// Insert new key to current node
// We make sure that the current node is not full by checking and
// splitting if necessary before descending to node

//System.out.println("inserting " + newKey); // Debugging code
int i=n-1;
if (isLeaf){
  while ((i>=0)&& (newKey<key[i])) {
    key[i+1] = key[i];
    i--;
  }
  n++;
  key[i+1]=newKey;
}
else{
  while ((i>=0)&& (newKey<key[i])) {
    i--;
  }
  int insertChild = i+1;  // Subtree where new key must be inserted
  if (c[insertChild].isFull()){
    // The root of the subtree where new key will be inserted has to be split
    // We promote the mediand of that root to the current node and
    // update keys and references accordingly

    //System.out.println("This is the full node we're going to break ");
    // Debugging     code
    //c[insertChild].printNodes();
    //System.out.println("going to promote " + c[insertChild].key[T-1]);
    n++;
    c[n]=c[n-1];
    for(int j = n-1;j>insertChild;j--){
      c[j] =c[j-1];
      key[j] = key[j-1];
    }
    key[insertChild]= c[insertChild].key[T-1];
    c[insertChild].n = T-1;

    BTreeNode newNode = new BTreeNode(T);
    for(int k=0;k<T-1;k++){
      newNode.c[k] = c[insertChild].c[k+T];
      newNode.key[k] = c[insertChild].key[k+T];
    }

    newNode.c[T-1] = c[insertChild].c[2*T-1];
    newNode.n=T-1;
    newNode.isLeaf = c[insertChild].isLeaf;
    c[insertChild+1]=newNode;

    //System.out.println("This is the left side ");
    //c[insertChild].printNodes(); 
    //System.out.println("This is the right side ");
    //c[insertChild+1].printNodes();
    //c[insertChild+1].printNodes();

    if (newKey <key[insertChild]){
      c[insertChild].insert(newKey);     }
    else{
      c[insertChild+1].insert(newKey);    }
  }
  else
    c[insertChild].insert(newKey);
}
 }

 public void print(){
//Prints all keys in the tree in ascending order
if (isLeaf){
  for(int i =0; i<n;i++)
    System.out.print(key[i]+" ");
  System.out.println();
}
else{
  for(int i =0; i<n;i++){
    c[i].print();
    System.out.print(key[i]+" ");
  }
  c[n].print();
}
}

 public void printNodes(){
//Prints all keys in the tree, node by node, using preorder
//It also prints the indicator of whether a node is a leaf
//Used mostly for debugging purposes
printNode();
if (!isLeaf){
  for(int i =0; i<=n;i++){
    c[i].printNodes();
  }
}
 }
 public void printNode(){
 //Prints all keys in node
for(int i =0; i<n;i++)
  System.out.print(key[i]+" ");
System.out.println(isLeaf);
}
 }


B树

      public class BTree{
      private BTreeNode root;
      private int T; //2T is the maximum number of childen a node can have
      private int height;

  public BTree(int t){
    root = new BTreeNode(t);
    T = t;
    height = 0;
  }

  public void printHeight(){
    System.out.println("Tree height is "+height);
  }

  public void insert(int newKey){
    if (root.isFull()){//Split root;
     split();
     height++;
   }
    root.insert(newKey);
    } 

  public void print(){
   // Wrapper for node print method
    root.print();
    }

  public void printNodes(){
    // Wrapper for node print method
    root.printNodes();
    }

  public void split(){
// Splits the root into three nodes.
// The median element becomes the only element in the root
// The left subtree contains the elements that are less than the median
// The right subtree contains the elements that are larger than the median
// The height of the tree is increased by one

//System.out.println("Before splitting root");
//root.printNodes(); // Code used for debugging
BTreeNode leftChild = new BTreeNode(T);
BTreeNode rightChild = new BTreeNode(T);
leftChild.isLeaf = root.isLeaf;
rightChild.isLeaf = root.isLeaf;
leftChild.n = T-1;
rightChild.n = T-1;
int median = T-1;
for (int i = 0;i<T-1;i++){
  leftChild.c[i] = root.c[i];
  leftChild.key[i] = root.key[i];
}
leftChild.c[median]= root.c[median];
for (int i = median+1;i<root.n;i++){
  rightChild.c[i-median-1] = root.c[i];
  rightChild.key[i-median-1] = root.key[i];
}
rightChild.c[median]=root.c[root.n];
root.key[0]=root.key[median];
root.n = 1;
root.c[0]=leftChild;
root.c[1]=rightChild;
root.isLeaf = false;
//System.out.println("After splitting root");
//root.printNodes();
 }}
4

0 回答 0