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.