Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Btree<key extends Comparable<key>, value> {//MAX children per b-tree node = M-1//(Must
- 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];
- The array of children//create a node with K Children private node (int k) {m = k;
- }//Internal nodes:only use key and next//external nodes:only the use key and value private static class Entry
- {Private comparable key;
- Private Object Val; Private Node Next; Helper field to iterate over array entries public Entry (comparable key, Object Val, Node next) {this.ke
- y = key;
- This.val = val; This.next = Next;
- }/** * Initializes an empty b-tree.
- * * Public btree () {root = new Node (0);
- }/** * Returns True if this symbol table is empty. * @return {@code true} if this symbol table is empty;
- {@code false} otherwise */public Boolean isempty () {return size () = 0;
- }/** * Returns the number of key-value pairs in this symbol table.
- * @return The number of key-value pairs in this symbol table */public int size () {return n;
- }/** * Returns The height of this b-tree (for debugging).
- * * @return The height of this b-tree */public int height () {return height;
- }/** * 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 *
- 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");
- return search (root, key, height); @SuppressWarnings ("unchecked") Private Value Search (Node x, key key, int ht) {entry[] children = X.children
- ; External node to the lowest leaf node, traversing if (ht = = 0) {for (int j = 0; J < X.M + +) {if EQ (k
- 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
- (j+1 = = X.M | | Less (key, Children[j+1].key))
- {return search (Children[j].next, key, ht-1);
- }} return null; }/** * Inserts the key-value pair into the symbol table, overwriting the "old" value * with the new value if the
- The key is already in the symbol table. * If The value is {@code null}, this effectively deletes the key from the SYMBOL table.
- * @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
- be null "); Node U = insert (root, Key, Val, height);
- The right node n++ formed after splitting;
- if (U = = null) {return;
- ///need to split root recombination root node t = new Node (2);
- T.children[0] = new Entry (Root.children[0].key, null, root);
- T.CHILDREN[1] = new Entry (U.children[0].key, NULL, u);
- root = t;
- height++;
- Private node Insert (node h, key key, Value val, int ht) {int J;
- Entry t = new Entry (key, Val, null);
- 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) {
- 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[
- J++].next, Key, Val, ht-1);
- if (U = null) {return null;
- } T.key = U.children[0].key;
- T.next = u;
- Break
- for (int i = H.M i > J; i--) {h.children[i] = h.children[i-1];
- } H.children[j] = t;
- h.m++;
- if (H.M < m) {return null;
- else {//split node return split (h);
- }//Split node in half private node split (node H) {Node T = new node (M/2);
- H.M = M/2;
- for (int j = 0; J < M/2; J +) {T.children[j] = h.children[m/2+j];
- } return t;
- }/** * Returns A string representation of this b-tree (for debugging).
- * * @return A string representation of this b-tree. */Public String toString () {return toString (root, Height, "") + "\ n";
- Private String toString (Node h, int ht, String indent) {StringBuilder s = new StringBuilder ();
- Entry[] children = H.children; if (ht = = 0) {for (int j = 0; J < H.M; J + +) {s.append (indent + Children[j].key + "" + chil
- Dren[j].val + "\ n"); } else {for (int j = 0; J < H.M; J +) {if (J > 0) {s.appen
- D (Indent + "(" + Children[j].key + ") \ n");
- } s.append (ToString (Children[j].next, ht-1, indent + ""));
- } return s.tostring (); }//comparison functions-make comparable instead of Key to avoid casts private Boolean less (comparable K1, compar
- Able K2) {return K1.compareto (K2) < 0;
- Private Boolean eq (comparable K1, comparable K2) {return K1.compareto (k2) = 0;
- }/** * 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> ();
- St.put ("www.cs.princeton.edu", "128.112.136.12");
- St.put ("www.cs.princeton.edu", "128.112.136.11");
- St.put ("www.princeton.edu", "128.112.128.15");
- St.put ("www.yale.edu", "130.132.143.21");
- St.put ("www.simpsons.com", "209.052.165.60");
- St.put ("www.apple.com", "17.112.152.32");
- St.put ("www.amazon.com", "207.171.182.16");
- St.put ("www.ebay.com", "66.135.192.87");
- St.put ("www.cnn.com", "64.236.16.20");
- St.put ("www.google.com", "216.239.41.99");
- St.put ("www.nytimes.com", "199.239.136.200");
- St.put ("www.microsoft.com", "207.126.99.140");
- St.put ("www.dell.com", "143.166.224.230");
- St.put ("www.slashdot.org", "66.35.250.151");
- St.put ("www.espn.com", "199.181.135.201");
- St.put ("www.weather.com", "63.111.66.11");
- St.put ("www.yahoo.com", "216.109.118.65"); System.out.println ("cs.princeton.edu:"+ St.get ("www.cs.princeton.edu"));
- System.out.println ("hardvardsucks.com:" + st.get ("www.harvardsucks.com"));
- System.out.println ("simpsons.com:" + st.get ("www.simpsons.com"));
- System.out.println ("apple.com:" + st.get ("www.apple.com"));
- System.out.println ("ebay.com:" + st.get ("www.ebay.com"));
- System.out.println ("dell.com:" + st.get ("www.dell.com"));
- System.out.println ();
- SYSTEM.OUT.PRINTLN ("Size:" + st.size ());
- System.out.println ("Height:" + st.height ());
- System.out.println (ST);
- System.out.println ();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement