Data Structures Solution

Draw a balanced tree of strings (words) with the following in-order traversal: this is a balanced tree I think

 

Explain in 1-2 complete sentences: Why do data structures like STL set, STL map, and ds_set need to have their internal tree representation be balanced to have fast performance?

 

For the next two questions, consider the following binary search tree

 

Draw the resulting trees from the following erase calls. Assume this is two independent calls to the tree shown above, and not erase(17); erase(2);. If you need to choose between the left and right subtree, choose the left subtree.

 

erase(17)
 
 
 
erase(2)
 
 
 
 

First draw the structure of the sequences map where SequenceA, SequenceB, and SequenceC are the query sequences.

 

Next, write code to search the map of maps and nd the sequence ID with the best score for each query sequence. The name of the sequence and its best scoring partner are to be stored in a new map called best hits, std::map, <std::string, std::string . Don't store the score of a sequence against itself, if found. That is, your map should not contain entries where the key and the value are the same sequence ID. For example, your map should no contain key-value pairs such as SequenceA as key and SequenceA as a value. Use const where appropriate.



 

You don't need include statements. You can assume using namespace std;

 

Now, write some code to search the map of sequence ID pairs to nd and print the reciprocal best hit pairs; that is, cases such as where SequenceA's best score is with SequenceC, and SequenceC's best score is with SequenceA. Don't print duplicate messages.

 

You don't need include statements. You can assume using namespace std; Here is the typical output

 

SequenceA has a reciprocal best hit with SequenceC

 

SequenceD has a reciprocal best hit with SequenceK

 

For this problem, you will be helping Ben Bitdiddle implement some functions that he claims will lead to a faster sort for binary search trees. All trees in this problem are binary search trees. To start with, you are given the code for the TreeNode class:

 

Write a function called FindLargestInTree that takes a TreeNode pointer to the root of a tree and returns the largest value in the tree. Remember to use const and & where appropriate. This function should work for any type T that has operator< de ned.

 

 

The next thing Ben wants you to do is write a function that will nd the smallest value ret in the tree starting from root such that a < ret < b. You can assume there are no duplicates inside the tree and that a is a value in the tree. If

 

3

no value of ret can satisfy the constraints, the return value should be NULL. To help you get started, he has written the following function:

 

 

Finally Ben says you are ready to write his sort function, TreeSort. The function should take in a pointer to a TreeNode which is the root of the tree. Your function should return a vector with the values in order from smallest to largest. You should not use std::sort or STL map, set, or list. Furthermore, Ben insists that you don't use the left, right, or parent pointers in your implementation, though it's okay to call FindLargestInTree and FindSmallestInRange. It's also okay to call FindSmallestInTree, even though you didn't implement it.

 

A sample code fragment using TreeSort

 

If FindSmallestInRange runs in O(f(n)) time, and both FindLargestInTree and FindSmallestInTree run in O(g(n)) time, and there are n nodes, what's the worst-case run time for TreeSort()? Use f(n) and g(n) where

 

5

appropriate, even if you expressed your run times in the earlier parts of the problem using n. Is this run time better, the same, or worse than doing an in-order traversal instead of Ben's method?

 

Given two sets of integers, set1 and set2, write an e cient code fragment that creates a third set of integers, set3, containing all of the values from set1 that are also contained in set2. When an element is found, it should be removed from set2.

 

Fill in the missing code for this pair of functions that will count how many times the letter E shows up in str.

 

int EInString(const std::string& str, int index){

 

 

Write a recursive function RecursiveFor() which replaces the following for loop with RecursiveFor(0,35);