Phyllis is a classic rock fan, and is creating a movie database program to keep
ID: 664299 • Letter: P
Question
Phyllis is a classic rock fan, and is creating a movie database program to keep her albums and songs organized. One of the things she wants to be able to do is print out a list of all the albums she owns by a particular band, in addition to other meta information about them (the year they formed, how many members, what record studios, etc.) For this, she creates a binary search tree of nodes, each of which represents a band. The nodes, once accessed, will contain everything about the Band that Phyllis needs – the trick is making her system work eciently so that a Band can be quickly pulled up by name. Suppose that Phyllis bootstrapped up her binary search tree by adding the following band nodes, in this order: Led Zeppelin, The Beatles, Crosby Stills and Nash, Jimi Hendrix, Eagles, Boston, Rush, The Who, Bob Dylan, Pink Floyd, Queen. (Do this literally, so that Eagles is literally “Eagles” whereas The Beatles is literally “The Beatles.”) Note that the binary search property here is in reference to band names: the nodes in the left subtree of a node are “less than” that node in the sense that all of them come before the node in alphabetical order.
a. Draw what the search tree would look like at this stage.
b. Give a list of the nodes, in the order in which they would be visited using a pre-order traversal algorithm. c. Give a list of the nodes, in the order in which they would be visited using an in-order traversal algorithm. d. Give a list of the nodes, in the order in which they would be visited using a post-order traversal algorithm.
e. Suppose the initial bands were inserted in a dierent order. Start over with an empty tree, and insert them in this order: The Beatles, The Who, Rush, Queen, Pink Floyd, Led Zeppelin, Jimi Hendrix, Eagles, Crosby Stills and Nash, Boston, Bob Dylan. How would the lookup performance of this tree compare to the previous?
Explanation / Answer
a.)print(node){
if(node !=null) {
printOut(root.value);
print(node.left);
print(node.right);
}
}
b.)Given nodes are
1-Led Zeppelin
2-Beatles
3-Crosby Stills and Nash
4-Jimi Hendrix
5-Eagles
6-Boston
7-Rush
8-The Who
9-Bod Dylan
10-Pink Floyd
11-Queen
1
/
2 5
/ /
3 4 6 7
/ /
8 9 10
/
11
e.) 2-Beatles,8-The Who,7-Rush,11-Queen,10-Pink Floyd,1-led Zeppelin,4-Jimi Hendrix,5-Eagles,3-Crosby Stills and Nash,6-Boston,9-Bob Dylan
2
/
7 8 10 11
/ / /
1 4 3 5 6 9