Skip to content

Instantly share code, notes, and snippets.

@m-zakeri

m-zakeri/BTree.java

Last active Jan 25, 2018
Embed
What would you like to do?
package btree;
/**
* ***********************************************************************
* Compilation: javac BTree.java Execution: java BTree
*
* B-tree.
*
* Limitations ----------- - Assumes M is even and M >= 4 - should b be an array
* of children or list (it would help with casting to make it a list)
*
* @author Morteza
* @version 1.0.0
* @category CodeBank
*
************************************************************************
*/
public class BTree<Key extends Comparable<Key>, Value> {
private static final int M = 4; // max children per B-tree node = M-1
private Node root; // root of the B-tree
private int HT; // 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 {
private int m; // number of children
private Entry[] children = new Entry[M]; // the array of children
private Node(int k) {
m = k;
} // create a node with k children
}
// internal nodes: only use key and next
// external nodes: only use key and value
private static class Entry {
private Comparable key;
private Object value;
private Node next; // helper field to iterate over array entries
public Entry(Comparable key, Object value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
// constructor
public BTree() {
root = new Node(0);
}
// return number of key-value pairs in the B-tree
public int size() {
return N;
}
// return height of B-tree
public int height() {
return HT;
}
// search for given key, return associated value; return null if no such key
public Value get(Key key) {
return search(root, key, HT);
}
private Value search(Node x, Key key, int ht) {
Entry[] children = x.children;
// external node
if (ht == 0) {
for (int j = 0; j < x.m; j++) {
if (eq(key, children[j].key)) {
return (Value) children[j].value;
}
}
} // internal node
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;
}
// insert key-value pair
// add code to check for duplicate keys
public void put(Key key, Value value) {
Node u = insert(root, key, value, HT);
N++;
if (u == null) {
return;
}
// need to split 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;
HT++;
}
private Node insert(Node h, Key key, Value value, int ht) {
int j;
Entry t = new Entry(key, value, null);
// external node
if (ht == 0) {
for (j = 0; j < h.m; j++) {
if (less(key, h.children[j].key)) {
break;
}
}
} // internal node
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, value, 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 {
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;
}
// for debugging
public String toString() {
return toString(root, HT, "") + "\n";
}
private String toString(Node h, int ht, String indent) {
String s = "";
Entry[] children = h.children;
if (ht == 0) {
for (int j = 0; j < h.m; j++) {
s += indent + children[j].key + " " + children[j].value + "\n";
}
} else {
for (int j = 0; j < h.m; j++) {
if (j > 0) {
s += indent + "(" + children[j].key + ")\n";
}
s += toString(children[j].next, ht - 1, indent + " ");
}
}
return s;
}
// comparison functions - make Comparable instead of Key to avoid casts
private boolean less(Comparable k1, Comparable k2) {
return k1.compareTo(k2) < 0;
}
private boolean eq(Comparable k1, Comparable k2) {
return k1.compareTo(k2) == 0;
}
/**
* ***********************************************************************
* @test program
* ***********************************************************************
*/
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();
}
}
/* output:
cs.princeton.edu: 128.112.136.12
hardvardsucks.com: null
simpsons.com: 209.052.165.60
apple.com: 17.112.152.32
ebay.com: 66.135.192.87
dell.com: 143.166.224.230
size: 17
height: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment