2
Hi friends .............
this is a question regarding the data structures trees
Pleas post it if possible with in 2 days
I will thankful if some body could help doing this.
Operating system: windows xp
compiler : Dev c++
Question is as folllows :
Genaration of keys :
Assume that your keys are character strings of length 10 obtained by scannig a c++ program. If a string has less than 10 characters make it up to 10 characters by including an appropriate number of trailing *'s. On the other hand, if the current string has more than 10 characters, truncate it to have the first ten characters only.
What should the program take as input?
1. n: the initial number of insertion of distinct strings to be made for setting up
an initial search tree(Red black tree or spaly tree)
2. I: This is a decimal number from which a ternary string is to be generated (namely radic-3 representation of I) In this representation, assume that a 0
represent the search operation, a 1 represents the insert operation , and a2 represents the delete operation
3. N : number of operations to be performed on the data structure.
4. A c++ program from which the tokens are to be picked up for setting up and
experimenting with the search trees.
What should the program do?
1. Scan the c++ program and as you scan , insert the first n distinct strings
scanned into an initial search treee ( Red black tree or splay tree)
2. For each individual operation keep track of ::
a) Nurmber of probes (comparisions of two strigs of 10 characters each)
b) Number of pointer assignments ( a single rotation involves three pointer
assignments )
c) Number of single rotations and number of double rotations ( in case of red
black trees and splay trees)
d) Examining or changing the colour ( in a red-black tree)
Now, compute for the redblack tree and splay tree, the following:
1.Height of the search tree
2. total number of probes for all the operations
3. Average number of probes (averaged over all the operations ) for a typical
sucessful search, unsucessful search, insert and delete
4. Total number of pointer assignments
5. Total number of single rotations
6. total number of double rotations
7.Total number of each type of spaying steps (Zig, Zag, Zig-Zag, Zag-zig , Zag-Zag) in the case of splay trees.
8. Total number of recolurings in the case of Red black trees
