001package algs62; // section 6.2 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac BTree.java 005 * Execution: java BTree 006 * 007 * B-tree. 008 * 009 * Limitations 010 * ----------- 011 * - Assumes M is even and M >= 4 012 * - should b be an array of children or list (it would help with 013 * casting to make it a list) 014 * 015 *************************************************************************/ 016 017public class BTree<K extends Comparable<? super K>, V> { 018 private static final int M = 4; // max children per B-tree node = M-1 019 020 private Node<K,V> root; // root of the B-tree 021 private int HT; // height of the B-tree 022 private int N; // number of key-value pairs in the B-tree 023 024 // helper B-tree node data type 025 private static class Node<K extends Comparable<? super K>, V> { 026 public int m; // number of children 027 @SuppressWarnings("unchecked") 028 public final Entry<K,V>[] children = new Entry[M]; 029 public Node(int k) { m = k; } // create a node with k children 030 } 031 032 // internal nodes: only use key and next 033 // external nodes: only use key and value 034 private static class Entry<K extends Comparable<? super K>, V> { 035 K key; 036 V value; 037 Node<K,V> next; // helper field to iterate over array entries 038 public Entry(K key, V value, Node<K,V> next) { 039 this.key = key; 040 this.value = value; 041 this.next = next; 042 } 043 } 044 045 // constructor 046 public BTree() { root = new Node<>(0); } 047 048 // return number of key-value pairs in the B-tree 049 public int size() { return N; } 050 051 // return height of B-tree 052 public int height() { return HT; } 053 054 055 // search for given key, return associated value; return null if no such key 056 public V get(K key) { return search(root, key, HT); } 057 private V search(Node<K,V> x, K key, int ht) { 058 Entry<K,V>[] children = x.children; 059 060 // external node 061 if (ht == 0) { 062 for (int j = 0; j < x.m; j++) { 063 if (eq(key, children[j].key)) return children[j].value; 064 } 065 } 066 067 // internal node 068 else { 069 for (int j = 0; j < x.m; j++) { 070 if (j+1 == x.m || less(key, children[j+1].key)) 071 return search(children[j].next, key, ht-1); 072 } 073 } 074 return null; 075 } 076 077 078 // insert key-value pair 079 // add code to check for duplicate keys 080 public void put(K key, V value) { 081 Node<K,V> u = insert(root, key, value, HT); 082 N++; 083 if (u == null) return; 084 085 // need to split root 086 Node<K,V> t = new Node<>(2); 087 t.children[0] = new Entry<>(root.children[0].key, null, root); 088 t.children[1] = new Entry<>(u.children[0].key, null, u); 089 root = t; 090 HT++; 091 } 092 093 094 private Node<K,V> insert(Node<K,V> h, K key, V value, int ht) { 095 int j; 096 Entry<K,V> t = new Entry<>(key, value, null); 097 098 // external node 099 if (ht == 0) { 100 for (j = 0; j < h.m; j++) { 101 if (less(key, h.children[j].key)) break; 102 } 103 } 104 105 // internal node 106 else { 107 for (j = 0; j < h.m; j++) { 108 if ((j+1 == h.m) || less(key, h.children[j+1].key)) { 109 Node<K,V> u = insert(h.children[j++].next, key, value, ht-1); 110 if (u == null) return null; 111 t.key = u.children[0].key; 112 t.next = u; 113 break; 114 } 115 } 116 } 117 118 for (int i = h.m; i > j; i--) h.children[i] = h.children[i-1]; 119 h.children[j] = t; 120 h.m++; 121 if (h.m < M) return null; 122 else return split(h); 123 } 124 125 // split node in half 126 private Node<K,V> split(Node<K,V> h) { 127 Node<K,V> t = new Node<>(M/2); 128 h.m = M/2; 129 for (int j = 0; j < M/2; j++) 130 t.children[j] = h.children[M/2+j]; 131 return t; 132 } 133 134 // for debugging 135 public String toString() { 136 return toString(root, HT, "") + "\n"; 137 } 138 private String toString(Node<K,V> h, int ht, String indent) { 139 String s = ""; 140 Entry<K,V>[] children = h.children; 141 142 if (ht == 0) { 143 for (int j = 0; j < h.m; j++) { 144 s += indent + children[j].key + " " + children[j].value + "\n"; 145 } 146 } 147 else { 148 for (int j = 0; j < h.m; j++) { 149 if (j > 0) s += indent + "(" + children[j].key + ")\n"; 150 s += toString(children[j].next, ht-1, indent + " "); 151 } 152 } 153 return s; 154 } 155 156 157 private boolean less(K k1, K k2) { 158 return k1.compareTo(k2) < 0; 159 } 160 161 private boolean eq(K k1, K k2) { 162 return k1.compareTo(k2) == 0; 163 } 164 165 166 /* *********************************************************************** 167 * test client 168 *************************************************************************/ 169 public static void main(String[] args) { 170 BTree<String, String> st = new BTree<>(); 171 172 // st.put("www.cs.princeton.edu", "128.112.136.12"); 173 st.put("www.cs.princeton.edu", "128.112.136.11"); 174 st.put("www.princeton.edu", "128.112.128.15"); 175 st.put("www.yale.edu", "130.132.143.21"); 176 st.put("www.simpsons.com", "209.052.165.60"); 177 st.put("www.apple.com", "17.112.152.32"); 178 st.put("www.amazon.com", "207.171.182.16"); 179 st.put("www.ebay.com", "66.135.192.87"); 180 st.put("www.cnn.com", "64.236.16.20"); 181 st.put("www.google.com", "216.239.41.99"); 182 st.put("www.nytimes.com", "199.239.136.200"); 183 st.put("www.microsoft.com", "207.126.99.140"); 184 st.put("www.dell.com", "143.166.224.230"); 185 st.put("www.slashdot.org", "66.35.250.151"); 186 st.put("www.espn.com", "199.181.135.201"); 187 st.put("www.weather.com", "63.111.66.11"); 188 st.put("www.yahoo.com", "216.109.118.65"); 189 190 191 StdOut.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu")); 192 StdOut.println("hardvardsucks.com: " + st.get("www.harvardsucks.com")); 193 StdOut.println("simpsons.com: " + st.get("www.simpsons.com")); 194 StdOut.println("apple.com: " + st.get("www.apple.com")); 195 StdOut.println("ebay.com: " + st.get("www.ebay.com")); 196 StdOut.println("dell.com: " + st.get("www.dell.com")); 197 StdOut.println(); 198 199 StdOut.println("size: " + st.size()); 200 StdOut.println("height: " + st.height()); 201 StdOut.println(st); 202 StdOut.println(); 203 } 204 205}