CS 310代做、代做AVL trees、代写c/c++/java编程设计、代做Balanced Trees

日期：2018-12-17 09:43

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