数据结构与算法 实战代码

package com.itheima.datastructure.btree; import java.lang.*; import java.util.*; import java.io.*; public class bplustree { int m; InternalNode root; LeafNode firstLeaf; /*~~~~~~~~~~~~~~~~ HELPER FUNCTIONS ~~~~~~~~~~~~~~~~*/ /** * This method performs a standard binary search on a sorted * DictionaryPair[] and returns the index of the dictionary pair * with target key t if found. Otherwise, this method returns a negative * value. * @param dps: list of dictionary pairs sorted by key within leaf node * @param t: target key value of dictionary pair being searched for * @return index of the target value if found, else a negative value */ private int binarySearch(DictionaryPair[] dps, int numPairs, int t) { Comparator<DictionaryPair> c = new Comparator<DictionaryPair>() { @Override public int compare(DictionaryPair o1, DictionaryPair o2) { Integer a = Integer.valueOf(o1.key); Integer b = Integer.valueOf(o2.key); return a.compareTo(b); } }; return Arrays.binarySearch(dps, 0, numPairs, new DictionaryPair(t, 0), c); } /** * This method starts at the root of the B+ tree and traverses down the * tree via key comparisons to the corresponding leaf node that holds 'key' * within its dictionary. * @param key: the unique key that lies within the dictionary of a LeafNode object * @return the LeafNode object that contains the key within its dictionary */ private LeafNode findLeafNode(int key) { // Initialize keys and index variable Integer[] keys = this.root.keys; int i; // Find next node on path to appropriate leaf node for (i = 0; i < this.root.degree - 1; i++) { if (key < keys[i]) { break; } } /* Return node if it is a LeafNode object, otherwise repeat the search function a level down */ Node child = this.root.childPointers[i]; if (child instanceof LeafNode) { return (LeafNode)child; } else { return findLeafNode((InternalNode)child, key); } } private LeafNode findLeafNode(InternalNode node, int key) { // Initialize keys and index variable Integer[] keys = node.keys; int i; // Find next node on path to appropriate leaf node for (i = 0; i < node.degree - 1; i++) { if (key < keys[i]) { break; } } /* Return node if it is a LeafNode object, otherwise repeat the search function a level down */ Node childNode = node.childPointers[i]; if (childNode instanceof LeafNode) { return (LeafNode)childNode; } else { return findLeafNode((InternalNode)node.childPointers[i], key); } } /** * Given a list of pointers to Node objects, this method returns the index of * the pointer that points to the specified 'node' LeafNode object. * @param pointers: a list of pointers to Node objects * @param node: a specific pointer to a LeafNode * @return (int) index of pointer in list of pointers */ private int findIndexOfPointer(Node[] pointers, LeafNode node) { int i; for (i = 0; i < pointers.length; i++) { if (pointers[i] == node) { break; } } return i; } /** * This is a simple method that returns the midpoint (or lower bound * depending on the context of the method invocation) of the max degree m of * the B+ tree. * @return (int) midpoint/lower bound */ private int getMidpoint() { return (int)Math.ceil((this.m + 1) / 2.0) - 1; } /** * Given a deficient InternalNode in, this method remedies the deficiency * through borrowing and merging. * @param in: a deficient InternalNode */ private void handleDeficiency(InternalNode in) { InternalNode sibling; InternalNode parent = in.parent; // Remedy deficient root node if (this.root == in) { for (int i = 0; i < in.childPointers.length; i++) { if (in.childPointers[i] != null) { if (in.childPointers[i] instanceof InternalNode) { this.root = (InternalNode)in.childPointers[i]; this.root.parent = null; } else if (in.childPointers[i] instanceof LeafNode) { this.root = null; } } } } // Borrow: else if (in.leftSibling != null && in.leftSibling.isLendable()) { sibling = in.leftSibling; } else if (in.rightSibling != null && in.rightSibling.isLendable()) { sibling = in.rightSibling; // Copy 1 key and pointer from sibling (atm just 1 key) int borrowedKey = sibling.keys[0]; Node pointer = sibling.childPointers[0]; // Copy root key and pointer into parent in.keys[in.degree - 1] = parent.keys[0]; in.childPointers[in.degree] = pointer; // Copy borrowedKey into root parent.keys[0] = borrowedKey; // Delete key and pointer from sibling sibling.removePointer(0); Arrays.sort(sibling.keys); sibling.removePointer(0); shiftDown(in.childPointers, 1); } // Merge: else if (in.leftSibling != null && in.leftSibling.isMergeable()) { } else if (in.rightSibling != null && in.rightSibling.isMergeable()) { sibling = in.rightSibling; // Copy rightmost key in parent to beginning of sibling's keys & // delete key from parent sibling.keys[sibling.degree - 1] = parent.keys[parent.degree - 2]; Arrays.sort(sibling.keys, 0, sibling.degree); parent.keys[parent.degree - 2] = null; // Copy in's child pointer over to sibling's list of child pointers for (int i = 0; i < in.childPointers.length; i++) { if (in.childPointers[i] != null) { sibling.prependChildPointer(in.childPointers[i]); in.childPointers[i].parent = sibling; in.removePointer(i); } } // Delete child pointer from grandparent to deficient node parent.removePointer(in); // Remove left sibling sibling.leftSibling = in.leftSibling; } // Handle deficiency a level up if it exists if (parent != null && parent.isDeficient()) { handleDeficiency(parent); } } /** * This is a simple method that determines if the B+ tree is empty or not. * @return a boolean indicating if the B+ tree is empty or not */ private boolean isEmpty() { return firstLeaf == null; } /** * This method performs a standard linear search on a sorted * DictionaryPair[] and returns the index of the first null entry found. * Otherwise, this method returns a -1. This method is primarily used in * place of binarySearch() when the target t = null. * @param dps: list of dictionary pairs sorted by key within leaf node * @return index of the target value if found, else -1 */ private int linearNullSearch(DictionaryPair[] dps) { for (int i = 0; i < dps.length; i++) { if (dps[i] == null) { return i; } } return -1; } /** * This method performs a standard linear search on a list of Node[] pointers * and returns the index of the first null entry found. Otherwise, this * method returns a -1. This method is primarily used in place of * binarySearch() when the target t = null. * @param pointers: list of Node[] pointers * @return index of the target value if found, else -1 */ private int linearNullSearch(Node[] pointers) { for (int i = 0; i < pointers.length; i++) { if (pointers[i] == null) { return i; } } return -1; } /** * This method is used to shift down a set of pointers that are prepended * by null values. * @param pointers: the list of pointers that are to be shifted * @param amount: the amount by which the pointers are to be shifted */ private void shiftDown(Node[] pointers, int amount) { Node[] newPointers = new Node[this.m + 1]; for (int i = amount; i < pointers.length; i++) { newPointers[i - amount] = pointers[i]; } pointers = newPointers; } /** * This is a specialized sorting method used upon lists of DictionaryPairs * that may contain interspersed null values. * @param dictionary: a list of DictionaryPair objects */ private void sortDictionar