CS 610留学生讲解、辅导AVL tree、辅导c/c++，Java，Python程序语言
- 首页 >> 其他 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.
1
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.
1