In Subsection 9.4.2, the textbook says that \"if the [binary sort] tree is creat

Question

In Subsection 9.4.2, the textbook says that "if the [binary sort] tree is created by inserting items in a random order, there is a high probability that the tree is approximately balanced." For this exercise, you will do an experiment to test whether that is true.

In the Introduction to this Learning Guide, you read that the depth of a node in a binary tree is the length of the path from the root of the tree to that node. That is, the root has depth 0, its children have depth 1, its grandchildren have depth 2, and so on. In a balanced tree, all the leaves in the tree are about the same depth. For example, in a perfectly balanced tree with 1023 nodes, all the leaves are at depth 9. In an approximately balanced tree with 1023 nodes, the average depth of all the leaves should be not too much bigger than 9.

On the other hand, even if the tree is approximately balanced, there might be a few leaves that have much larger depth than the average, so we might also want to look at the maximum depth among all the leaves in a tree.

For this exercise, you should create a random binary sort tree with 1023 nodes. The items in the tree can be real numbers, and you can create the tree by generating 1023 random real numbers and inserting them into the tree, using the usual treeInsert() method for binary sort trees. Once you have the tree, you should compute and output the average depth of all the leaves in the tree and the maximum depth of all the leaves. To do this, you will need three recursive subroutines: one to count the leaves, one to find the sum of the depths of all the leaves, and one to find the maximum depth. The latter two subroutines should have an int-valued parameter, depth, that tells how deep in the tree you've gone. When you call this routine from the main program, the depth parameter is 0; when you call the routine recursively, the parameter increases by 1

I WILL LIKE THE SUBROUTINES WRITTEN IN JAVA, THAT IS THE LANGUAGE I AM LEARNING RIGHT NOW.

THANKS

Explanation / Answer

/** * This program makes a random binary sort tree containing 1023 random * real numbers. It then computes the height of the tree and the * average depth of the leaves of the tree. Hopefully, the average * depth will tend to be close to 9, which is what it would be * if the tree were perfectly balanced. The height of the tree, * which is the same as the maximum depth of any leaf, can be * significantly larger. */ public class RandomSortTree { static TreeNode root; // Pointer to the binary sort tree. /** * An object of type TreeNode represents one node in a binary tree of real numbers. */ static class TreeNode { double item; // The data in this node. TreeNode left; // Pointer to left subtree. TreeNode right; // Pointer to right subtree. TreeNode(double x) { // Constructor. Make a node containing x. item = x; } } // end class TreeNode /** * Add x to the binary sort tree to which the global variable "root" refers. */ static void treeInsert(double x) { if ( root == null ) { // The tree is empty. Set root to point to a new node // containing the new item. root = new TreeNode( x ); return; } TreeNode runner; // Runs down the tree to find a place for newItem. runner = root; // Start at the root. while (true) { if ( x rightMax) return leftMax; else return rightMax; } } // end maximumLeafDepth() /** * The main routine makes the random tree and prints the statistics. */ public static void main(String[] args) { root = null; // Start with an empty tree. Root is a global // variable, defined at the top of the class. // Insert 1023 random items. for (int i = 0; i < 1023; i++) treeInsert(Math.random()); // Get the statistics. int leafCount = countLeaves(root); int depthSum = sumOfLeafDepths(root,0); int depthMax = maximumLeafDepth(root,0); double averageDepth = ((double)depthSum) / leafCount; // Display the results. System.out.println("Number of leaves: " + leafCount); System.out.println("Average depth of leaves: " + averageDepth); System.out.println("Maximum depth of leaves: " + depthMax); } // end main() } // end class RandomSortTree

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.