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.