CS 310讲解、讲解AVL trees、辅导c/c++/java编程设计、讲解Balanced Trees
- 首页 >> Java编程CS 310: Worksheet 07 San Diego State University
Name: Section:
Due Date: 2018-DEC-11/12 Score:
Maps and Balanced Trees
Identify the correctness of each of the following statements by marking either a T for true of F for
false.
1. (1 point) A balanced tree is exclusively defined as one in which the height of each sub-tree
(or child) differs by no more than one (1).
2. (1 point) In a red-black tree, after rotating three nodes, the two children will each be red.
3. (1 point) One will only ever need to perform one rotation or color-flip in a red-black tree
when balancing.
4. (1 point) Both red-black and AVL trees produce keys in sorted order.
5. (1 point) Adding a single item to a hash table or AVL tree, both of size n requires a
complexity of O(log(n))
Balanced Trees
6. (2 points) Which data structure implements the Map interface by connecting a sequence of
independent Node objects through reference pointers?
A. Binary Heap B. Hash table C. Binary search tree D. Both B and C E. None of
the above
6.
7. (5 points) Complete the following Java method which takes a grandparent node and performs
a left rotation:
public Node<E> rotateLeft( Node<E> node ){
CS 310: Worksheet 07 San Diego State University
8. (2 points) An AVL tree must maintain the height of each sub-tree in every node. An inexperienced
software engineer suggests saving space by simply calculating it at run-time. What
negatives might one point out, if any, with this approach?
9. (4 points) Draw the final AVL tree resulting from inserting the following number sequence in
order from left to right. Show each major insertion (e.g., one where the tree rotates) for partial
credit: 22, 91, -12, 45, 88, 10, 12, 11, 43
Page 2
CS 310: Worksheet 07 San Diego State University
10. (4 points) Draw the final Red-Black tree, noting each node’s color, resulting from inserting the
following number sequence in order from left to right. Show each major insertion for partial
credit: 3, 79, -15, 19, 20, 39, 40, 41, -16