Contents | Index | < Browse | Browse >
  Optimize FSS List:

  As you maybe have guessed, the FSS will store all the  modules  you  have
  heard  as  a  binary tree. This is because it's the fastest way to search
  for a file to see if it already exist when you load a new module. If  you
  know  a  little  bit  about binary trees, you will properly know that the
  tree will get unbalanced after a while. The term  unbalanced  is  further
  described in the figures below:



                                     8
                                    / 
                                   3   9
                                  / 
                                 2   4
                                      
                                       5

                           Fig1: Unbalanced Tree

                                     5
                                    / 
                                   3   8
                                  /    
                                 2   4   9

                           Fig2: The same tree, but balanced

  A tree can be divided into two subtrees, from the  root.  The  trees  are
  split  in  layers,  for  instance  the unbalanced tree in fig.1 has got 4
  layers, while fig.2 has got 3  layers.  If  a  tree  is  unbalanced  it's
  because  the  difference  between  the  number  of layers in the two main
  subtrees is bigger than one.

  If the tree isn't balanced, it will decrease the search time. Let's  take
  an example: if you will insert the number 7 in figure 1, you have to test
  4 other nodes (8, 3, 4 & 5) to know where to place it, but  in  figure  2
  you  only need 2 tests (5 & 8). Now you can see, the search time has been
  halfed.

  This is what this function does, it balances the binary tree (from now on
  named  AVL-trees).  It will test if the modules are still present on your
  HD and if they aren't they will be deleted from the  tree.  If  you  have
  some  modules  on  floppy disk the optimizer asks for the disk. To delete
  the module from the tree just cancel the disk requesters.