By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,364 Members | 1,576 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,364 IT Pros & Developers. It's quick & easy.

performance of Red-black trees and splay trees ie.. insert ,search,delete etc

P: 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
Oct 4 '07 #1
Share this Question
Share on Google+
2 Replies

Expert Mod 100+
P: 931

Welcome to TSDN. This question looks like homework or assignment. Have you tried anything so far? Then paste it here. Also follow posting guidelines as TSDN is not the site to do homeworks or assignments. You can ask your perticular problem,errors or logical queries and we would be glad to help you then.

Kind regards
Oct 4 '07 #2

P: 2
1.How to take a character input from another file ?
2.what is the command to retrieve this ?
Oct 5 '07 #3

Post your reply

Sign in to post your reply or Sign up for a free account.