Question
Please answer: Data structure Java
Let t be the degree of a BTree. Suppose the size of each object, including the
key, stored in the tree is 90 bytes. Also, suppose the size of a BTreeNode pointer is 4
bytes. In addition, 100 bytes of meta-data is required for each BTree node to keep track
of some useful information. Suppose each BTreeNode has only the meta-data, a parent
pointer, a list of objects, and a list of child pointers. What is the optimal degree for this
BTree if a disk block is 4096 bytes?
/////////////////////////////////
For a BTree with height 4 (or 5 levels), what is the maximal number of objects
can be stored if the degree t = 51?
Explanation / Answer
class BinaryTreeNode { Object data; BinaryTreeNode leftChild, rightChild; public BinaryTreeNode(Object info) { data = info; leftChild = null; rightChild = null; } } class BinaryTree { BinaryTreeNode root; public BinaryTree() { root = null; } // Create a new tree with one node (the root) whose value is given public BinaryTree(Object rootValue) { root = new BinaryTreeNode(rootValue); } public BinaryTree(Object rootValue, BinaryTreeNode leftRoot, BinaryTreeNode rightRoot) { root = new BinaryTreeNode(rootValue); root.leftChild = leftRoot; root.rightChild = rightRoot; } public Boolean isEmpty() { return root == null; } public void clear() { root == null; } public int height() { return height(root); } private int height(BinaryTreeNode treeRoot) { if (treeRoot == null) return 0; else return 1 + Math.max(height(treeRoot.leftChild),height(treeRoot.rightChild)); } public int size() { return size(root); } private int size(BinaryTreeNode treeRoot) { if (treeRoot == null) return 0; else return 1 + size(treeRoot.leftChild) + size(treeRoot.rightChild)); } public void add(Object value) { if (this.isEmpty()) root = new BinaryTreeNode(value); else add(value, root); } private void add(Object value, BinaryTreeNode treeRoot) { if (treeRoot.leftChild == null) treeRoot.leftChild = new BinaryTreeNode(value); else if (treeRoot.rightChild == null) treeRoot.rightChild = new BinaryTreeNode(value); else if (size(treeRoot.leftChild)