C S
C 3 6 5 E X A M #
2 Name:__________________
M.
Mohammadi Fall 2002
(40
Points) 1.
Consider the following AVL Tree:
50-
20/
80\
12- 32-
61- 92-
5- 15- 83- 99-
a) Insert 13 into the tree.
Explain where rotation(s) are needed and why, if they are. Show the balance factors when insertion is
completed.
b)
Remove 50 from the original AVL tree shown above, not the one
after
inserting 13. Use the
successor for the root replacement.
Explain where rotation(s) are needed and why, if they are. Show the
balance factors when removal is completed.
c) Consider the following insert() method from the AVL implementation
discussed in class. Remember that the Tree class maintains a root_
field that is
an AVL object. Each request to add for the Tree
class when root_ is
not null invokes a call to root_'s insert
method; in turn, insert
calls for left_ and right_ of the root_ may
be invoked. These insert
calls are propagated until we are ready to
insert a value.
How many calls to insert need to be made in
order to insert 13,
including the first call to insert from the
add method in the Tree class?
AVL insert(Comparable o) {
if(element_.compareTo(o)==0) return
this;
if (element_.compareTo(o)<0) {
if (right_==null) {
right_=new AVL(o);
switch (BF_) {
case '-':BF_='\\'; taller_=true;
break;
case '/':BF_='-';break;
default:
System.err.println("invalid
balance factor when inserting " + o);
dump(5);
}
}
else {
right_=right_.insert(o);
if (right_.taller_) {
right_.taller_=false;
switch (BF_) {
case '/': BF_='-'; break;
case '-': BF_='\\'; taller_=true;
break;
case '\\'://rotation needed
switch(right_.BF_) {
case '\\':
AVL tmp=rotateLeft();
tmp.BF_=tmp.left_.BF_='-';
return tmp;
case '/':
switch (right_.left_.BF_) {
case
'/':BF_='-';right_.BF_='\\'; break;
case
'\\':BF_='/';right_.BF_='-'; break;
case
'-':BF_='-';right_.BF_='-'; break;
}
right_=right_.rotateRight();
AVL tmp2= rotateLeft();
tmp2.BF_='-';
return tmp2;
default:
System.err.println("invalid balance factor when inserting " +
o);
dump(5);
}
}
}
}
}
else{
if (left_==null) {
left_=new AVL(o);
switch (BF_) {
case '-':BF_='/'; taller_=true;
break;
case '\\':BF_='-';taller_=false;
break;
default:
System.err.println("invalid
balance factor when inserting " + o);
dump(5);
}
}
else {
left_=left_.insert(o);
if (left_.taller_) {
left_.taller_=false;
switch (BF_) {
case '\\':BF_='-'; taller_=false;
break;
case '-':BF_='/'; taller_=true; break;
case '/'://rotation needed
switch(left_.BF_) {
case '/':
AVL tmp=rotateRight();
tmp.BF_=tmp.right_.BF_='-';
return tmp;
case '\\':
switch (left_.right_.BF_) {
case
'/':BF_='\\';left_.BF_='-'; break;
case '\\':BF_='-';left_.BF_='/';
break;
case
'-':BF_='-';left_.BF_='-'; break;
}
left_=left_.rotateLeft();
AVL tmp2= rotateRight();
tmp2.BF_='-';
return tmp2;
default:
System.err.println("invalid balance factor when inserting " +
o);
dump(5);
}
}
}
}
}
return this;
}
d) Count the number of AVL nodes visited in each of the versions
of the levels method shown below if we start with the node that holds 20
in the tree shown at the beginning of question 1.
|
int levels() { if (left_ == null && right_==
null) return 1; if (left_ == null || right_== null) return 2; int L=left_.levels(); int R=right_.levels(); return (L<R?R+1:L+1); } How
Many Nodes? |
int levels() { switch (BF_) { case '/':return 1+left_.levels(); case '-':return 1+(left_ ==null ?0:left_.levels()); default: return 1+right_.levels(); } } How
Many Nodes? |
(30 Pts.) 3.
---------
Consider
the following RAF where the breakdown of each record is similar to that of our
externalDictionary's extra credit:
AAA0000000 M BBB1111111 U
AAB2222222 U
----------------- -----------------
-----------------
Record #0 Record #1 Record #2
Each record starts with a 3-character key followed by a
7-character "other data" associated with each key. At the end of each
record, we have a flag that identifies it a Master/UserAugmented/Deleted.
Also
assume that the process of inserting and deleting records in similar to that of
the extra credit assignment:
New records are inserted at the end and records are simply marked
as deleted when we get rid of them.
a) Upon
construction, a vector of vectorElements (i.e. key/position) is to be created
based on the entries that are not deleted in this file. This vector is then
sorted. Show what this vector's content is suppose to look like if the above
records are in our file.
Location
0 of vector contains:
Location
1 of vector contains:
.
.
.
b) What
will the file and the corresponding vector contain if we add
(Key=ABB, other data = 3333333)?
c) Show
the file and vector contents after deleting BBB. Assume b) has taken place.
(30
points) 4. External
index structures.
a) In real database systems, index
structures are maintained externally in a file. Briefly, give the rational for why this is
done.
b) Finding a word in an internal
vector like word used in our externalDictionary class
involves use a method like indexOf(). The index found corresponds to where
the record with that word is in the random access file that holds
word/meanings.
What would each record look like in an external index that would
be used instead of our internal vector? What kind of file would you use
(sequential, Random) and why?
Describe an algorithm that you would employ to locate a word if
the vector were external.
