Comp 282 Practice Midterm 1 Fall 2017 Problem 1 Write a method, in Java, that pr

Question

Comp 282 Practice Midterm 1 Fall 2017 Problem 1 Write a method, in Java, that prints out the contents of a BST (containing integers) from largest to smallest. Problem 2 Write a method, in Java, that prints out the number of red nodes in a Red Black Tree. Problem 3 a) Draw the BST after the following values are inserted into an empty BST in the given order: 9, 27, 36, 45, 3, 39, 29, 33, 7, 31, 30, and 44. b) Draw the BST after deleting 27 from the resulting BST from part a. c) Draw the BST after deleting the root from the resulting BST from part b. Use successor replacement for part b and part c if needed. Problem 4 a) What is the minimum number of inserts/values for an AVL tree of height 9? b) What is the maximum number of inserts/values for an AVL tree of height 9? c) Explain why the number of inserts/values for a given AVL tree height affects regular tree operations Problem 5 a) Draw the A VL tree after the following values are inserted into an empty AVL tree in the given order: 9, 27, 36, 45, 3, 39, 29, 33, 7,31, 30, and 44 Problem 6 a) Draw a worst-case example of a Splay tree with ten integer insets. b) Draw the Splay tree from part a after finding the value with the lowest height (could be min or max). Problem 7.The following integers are inserted into an empty Splay tree in this order: 23,45, 6, 37,49,51,47,48, and 44. Draw the resulting Splay tree after all the inserts. Find min and draw the resulting Splay tree. Problem 8 a) Explain why the Splay tree operations are O(log N) on average. b) Distinguish between Splay tree operations and AVL operations O(log N). Discuss why Splay trees and AVL trees are not exactly log N for all operations. Problem 9 Starting with the Red Black tree below, perform the following operations and draw the Red Black Tree after each: insert 10, insert 97, insert 99.

Explanation / Answer

Please find answer for Q1.

Please repost other in separate post.

Inorder traversal of BST print tree in increasing order (samllest tot largest)

So, to pring largest to samllest, we need to first print right subtree before lest subtree

// Node structure

class Node {

Node left, right;

int data;

}

void printLargestToSamllest(Node root) {

if (root != null) {

// first printing right subtree

printLargestToSamllest(root.right);

// printing root

System.out.print(" " + root.data);

// printing left subtree

printLargestToSamllest(root.left);

}

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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