Advertisement
Guest User

Untitled

a guest
Jan 24th, 2020
331
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.70 KB | None | 0 0
  1. public class Btree<key extends Comparable<key>, value> {//MAX children per b-tree node = M-1//(Must
  2.  
  3.   be even and greater than 2) private static final int M = 4;    private Node root;   Root of the b-tree private int height;      The height of the b-tree private int n; Number of key-value pairs in the B-tree//Helper b-tree node data type private static final class node {p               rivate int m;  Number of children private entry[] children = new ENTRY[M];
  4.     The array of children//create a node with K Children private node (int k) {m = k;  
  5.   }//Internal nodes:only use key and next//external nodes:only the use key and value private static class Entry
  6.     {Private comparable key;
  7.     Private Object Val;   Private Node Next; Helper field to iterate over array entries public Entry (comparable key, Object Val, Node next) {this.ke
  8.       y = key;
  9.       This.val = val; This.next = Next;
  10.    }/** * Initializes an empty b-tree.
  11.   * * Public btree () {root = new Node (0);
  12.    }/** * Returns True if this symbol table is empty. * @return {@code true} if this symbol table is empty;
  13.   {@code false} otherwise */public Boolean isempty () {return size () = 0;
  14.    }/** * Returns the number of key-value pairs in this symbol table.
  15.   * @return The number of key-value pairs in this symbol table */public int size () {return n;
  16.    }/** * Returns The height of this b-tree (for debugging).
  17.   * * @return The height of this b-tree */public int height () {return height;
  18.    }/** * Returns The value associated with the given key.     * * @param key The key * @return the value associated with the given key if the ' key is ' in the ' symbol table *
  19.    and {@code null} if the key is not in the ' symbol table * @throws nullpointerexception if {@code key} is {@code null} */Public Value GET (key key) {if (key = = null) {throw new NullPointerException ("key must not being null");
  20.   return search (root, key, height); @SuppressWarnings ("unchecked") Private Value Search (Node x, key key, int ht) {entry[] children = X.children
  21.  
  22.     ; External node to the lowest leaf node, traversing if (ht = = 0) {for (int j = 0; J < X.M + +) {if EQ (k
  23.         EY, Children[j].key)) {return (Value) Children[j].val;  Internal node recursively lookup next address else {for (int j = 0; J < x.m; J + +) {if
  24.         (j+1 = = X.M | | Less (key, Children[j+1].key))
  25.         {return search (Children[j].next, key, ht-1);
  26.   }} return null; }/** * Inserts the key-value pair into the symbol table, overwriting the "old" value * with the new value if the
  27.    The key is already in the symbol table. * If The value is {@code null}, this effectively deletes the key from the SYMBOL table.
  28.   * @param key The key * @param val The value * @throws nullpointerexception if {@code key} is {@code null} * *  public void put (key key, Value val) {if (key = = null) {throw new NullPointerException ("key must not
  29.     be null "); Node U = insert (root, Key, Val, height);
  30.     The right node n++ formed after splitting;
  31.     if (U = = null) {return;
  32.     ///need to split root recombination root node t = new Node (2);
  33.     T.children[0] = new Entry (Root.children[0].key, null, root);
  34.     T.CHILDREN[1] = new Entry (U.children[0].key, NULL, u);
  35.     root = t;
  36.   height++;
  37.     Private node Insert (node h, key key, Value val, int ht) {int J;
  38.  
  39.     Entry t = new Entry (key, Val, null);
  40.         External node outer node, also leaf node, at the bottom of the tree, is the content value if (ht = = 0) {for (j = 0; J < H.M; j) {
  41.         if (Less (key, H.children[j].key)) {break; }}//Internal node internal node, save next address else {for (j = 0; J < H.M; J + +) {if (j+1 = = H.M) | | | Less (key, H.children[j+1].key)) {Node u = insert (h.children[
  42.           J++].next, Key, Val, ht-1);
  43.           if (U = null) {return null;
  44.           } T.key = U.children[0].key;
  45.           T.next = u;
  46.         Break
  47.     for (int i = H.M i > J; i--) {h.children[i] = h.children[i-1];
  48.     } H.children[j] = t;
  49.     h.m++;
  50.     if (H.M < m) {return null;
  51.     else {//split node return split (h);
  52.     }//Split node in half private node split (node H) {Node T = new node (M/2);
  53.     H.M = M/2;    
  54.     for (int j = 0; J < M/2; J +) {T.children[j] = h.children[m/2+j];  
  55.   } return t;
  56.    }/** * Returns A string representation of this b-tree (for debugging).
  57.    * * @return A string representation of this b-tree. */Public String toString () {return toString (root, Height, "") + "\ n";
  58.     Private String toString (Node h, int ht, String indent) {StringBuilder s = new StringBuilder ();
  59.  
  60.     Entry[] children = H.children; if (ht = = 0) {for (int j = 0; J < H.M; J + +) {s.append (indent + Children[j].key + "" + chil
  61.       Dren[j].val + "\ n"); } else {for (int j = 0; J < H.M; J +) {if (J > 0) {s.appen
  62.         D (Indent + "(" + Children[j].key + ") \ n");
  63.       } s.append (ToString (Children[j].next, ht-1, indent + ""));
  64.   } return s.tostring (); }//comparison functions-make comparable instead of Key to avoid casts private Boolean less (comparable K1, compar
  65.   Able K2) {return K1.compareto (K2) < 0;
  66.   Private Boolean eq (comparable K1, comparable K2) {return K1.compareto (k2) = 0;
  67.    }/** * Unit tests the {@code btree} data type. * * @param args the command-line arguments/public static void main (STRIng[] args) {btree<string, string> st = new Btree<string, string> ();
  68.     St.put ("www.cs.princeton.edu", "128.112.136.12");
  69.     St.put ("www.cs.princeton.edu", "128.112.136.11");
  70.     St.put ("www.princeton.edu", "128.112.128.15");
  71.     St.put ("www.yale.edu", "130.132.143.21");
  72.     St.put ("www.simpsons.com", "209.052.165.60");
  73.     St.put ("www.apple.com", "17.112.152.32");
  74.     St.put ("www.amazon.com", "207.171.182.16");
  75.     St.put ("www.ebay.com", "66.135.192.87");
  76.     St.put ("www.cnn.com", "64.236.16.20");
  77.     St.put ("www.google.com", "216.239.41.99");
  78.     St.put ("www.nytimes.com", "199.239.136.200");
  79.     St.put ("www.microsoft.com", "207.126.99.140");
  80.     St.put ("www.dell.com", "143.166.224.230");
  81.     St.put ("www.slashdot.org", "66.35.250.151");
  82.     St.put ("www.espn.com", "199.181.135.201");
  83.     St.put ("www.weather.com", "63.111.66.11");
  84.  
  85.  
  86.     St.put ("www.yahoo.com", "216.109.118.65"); System.out.println ("cs.princeton.edu:"+ St.get ("www.cs.princeton.edu"));
  87.     System.out.println ("hardvardsucks.com:" + st.get ("www.harvardsucks.com"));
  88.     System.out.println ("simpsons.com:" + st.get ("www.simpsons.com"));
  89.     System.out.println ("apple.com:" + st.get ("www.apple.com"));
  90.     System.out.println ("ebay.com:" + st.get ("www.ebay.com"));
  91.     System.out.println ("dell.com:" + st.get ("www.dell.com"));
  92.  
  93.     System.out.println ();
  94.     SYSTEM.OUT.PRINTLN ("Size:" + st.size ());
  95.     System.out.println ("Height:" + st.height ());
  96.     System.out.println (ST);
  97.   System.out.println ();
  98.  }
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement