CS 610留学生代做、代写AVL tree、代写c/c++，Java，Python程序语言-代写Java编程

Assignment 4 (75 points)

CS 610 Spring 2019

Instructor : Ravi Varadarajan

Due : Mar 27,2019 in class

Problem 1. (5 points) Recall in a red-black tree black-height bh(x) of a node

x is the number of black nodes in a path to an external node in the subtree

rooted at x, excluding x. Prove by induction on the height of x that the number

of internal nodes in the subtree rooted at x is at least 2bh(x) ? 1.

Problem 2. (10 points) Starting with an empty AVL tree show the trees (with

balance factor at each node) after insertion of each of the following keys in the

order shown: 25,10,5,18,22,20,12,14,15,16

Problem 3. (10 points) Starting with the AVL tree constructed in the first

problem show the trees (with balance factor at each node) after deletion of

each of the following keys in the order shown: 25,15,18,10,5,12,16,22,14,20

Problem 4. (20 points) Problem R-3.11 of the text book. For RB tree, lightly

crosshatch the nodes colored black.

Problem 5. (10 points) Show that the total running time of performing n

union and find operations in amortized union-find data structure is O(n) if

all the union operations are performed before all the finds in the sequence of n

operations.

Problem 6. (8 points) Show that 5 elements can be sorted using 7 comparisons

in the worst-case. Is it optimal Explain.

Problem 7. (12 points) Let A and B be two sequences of n integers each.

Given an integer x, describe an O(n log n)-time algorithm for determining if

there is an integer a in A and b in B such that x = a + b.