Index


Insert Values in a Binary Tree
Using a recursive scan for disk files
and directories as an example


      You can download the code (uncommented followed by the commented examples) by right clicking on the following link and choosing 'save link as' or 'save target as' from the pop down menu to save the text file to your computer ----> insert_binary_tree.txt

A related page scans subdirectories and puts them onto a Delphi TreeView.

     Not to long ago my motherboard fried and had to be replaced. Since that time the software I was using to back up my disk drive no longer works, and has been destroying one CD after another. I have considered buying another program, but since I am learning Delphi Pascal as a diversion and a hobby I thought that my first project should be to write my own backup program to keep my files backed up to CD.

     As 'beta version number one' of this proposed program, I am experimenting with creating a database of disk files in the form of a binary tree. Disk directories and subdirectories and files are by their very nature in the form of a tree like structure so choosing this form of storage seems like it might be a natural fit. I have a lot of memory and I am hoping, for the sake of speed, to be able to hold the entire database in memory in this data structure, and I am also interested in testing the Windows Swap file to see how such a potentially large database might function on a computer with only 32 or 64 megs.

     For the benefit of those of you who know something about these things I will mention that the following code is a preliminary example of an 'unbalanced binary tree structure.' Well balanced binary trees have the advantage of great speed when it comes time to search for a record. If you imagine a flat straight line list, with a value at position number one million (and no index or other such tactics employed) a search would have to go one by one through one million records before finding the matching key. A binary tree, because of the way the data is structured allows the record to be found in only a few operations. The following binary tree sorts and inserts data in alphabetical (or numerical order). Binary trees are balanced only when the data input is random, and the less random, and more orderly the original input to the tree the more the tree structure flattens out and becomes like a straight line data structure rather than a branching tree structure. (In the worst case scenario such an completely unbalanced tree would perform as poorly as a sequential list, so I am doing some research on balancing a tree and different tree structures. However assuming that a person does not have a monster database and given that files on a computer are sorted in directoreis and subdirectories within directories the 'imbalance' in the tree should be restricted to only the files within the directory, and a search for a given directory should be able to take advantage of all the great speed of a binary tree search.)

     A 'node' on a binary tree consists of two pointers to other 'nodes' (a left and a right pointer, designated by 'l' and 'r' in the example) and a data segment. For my example, I am only interested in saving the filenames on my disk and the date on which the file was last modified so that might proposed backup program can quickly identify which files on my disk have newer modification dates than the files in the datebase, and thus need to be backed up. I need a left and right pointer, and for the data segment, I need a string for the filename and an integer to store the time value of when the file was last modified.

The structure of the 'node' then would be

| Left Ptr | String | Integer | Right Ptr |

      The Left Pointer on a node points to values less than the 'key' value (the value used to sort the tree in this case into alphabetical order) and the right pointer points to values greater than the key value. It is this characteristic that both sorts a binary tree into a branching structure and makes searching very quick. Consider the following sequential list (this could be either an array or a linked list, which is like a binary node but with only one link pointing to the next item in the list, rather than a less than and greater than link as in a binary node.)

D G I M P R Z

     If I wanted to search a sequential list or array for the value 'Z' I would need to search through 7 items before finding the object of my search. Now consider the same values arranged as a binary tree, as in the diagram below.

binary_tree.jpg - 9426 Bytes

     In this example the first value entered into the tree was 'M'. I am searching for 'Z' and this is greater than 'M' so I check the value stored in the node pointed to by the right link of 'M'. I find the value 'R'. 'Z' is greater than 'R' so I check the value linked to the right of 'R' and I locate the object of my search, 'Z'. I have located the object of my search in two steps rather the seven required in the flat sequential list. As the size of a database increases the speed advantage of a binary tree increases (logarithmically) so that millions of pieces of data can be searched in only a small number of iterations, while sequential searches take, on the average a number of repeated searches equal to half the number of items on the list (so there really is no comparison in searching speecd between these two ways of storing and searching large amounts of data). However you can imagine what would happen if the data was entered into the tree in order, rather than randomly. You would get instead of the desirable branching tree stucture, a straight line tree, and in that case it would take seven searches once again to find the value 'Z' (just like it did for the sequential list - for this reason I am researching techniques for 'balancing' trees).

      The following example assumes that the binary tree is a global variable. (Global variables are declared in the main declarations of a unit in pascal, rather than in an individual procedure or function.) A 'link' is a pointer to an address in the computer, in this case the address of a record I am calling 'node' which contains the data structure described above. The type declaration of the tree has been placed in the type declaration header of the unit, using the 'record' type which takes the following form...



interface

uses (list of units follows)

type
   link=^node;
   node=record filename:string; ModTime:integer; l, r:link end;
   TForm1 = class(TForm) (etc. the form type declaration follows)



     Because I want this the 'scope' of this tree variable to be 'global' to the unit (all procedures and functions can have access) I then declare the 'head' and 'tail' links in the global variable section that comes just below the type definitions in a Pascal unit as follows.



private { Private declarations }
public { Public declarations }
end;

var
   Form1: TForm1; (the standard Pascal form declaration)
   head, tail: link; (my global head and tail link declaration)



     In this example I am using a 'tail' link to simplify the code. (If a search winds up finding this 'tail' link then the search was unsucessful and that means that either the bottom of the tree has been reached and its time to quit, or it is a signal to the TreeInsert routine that the spot to insert the node has been found. This is simpler to code than using 'nul' pointers, something I won't go into here.)

     In the following example, since I am experimenting with representing the files on a disk in tree form, I am going to use the example of scanning disk directories as a way to fill the tree. You can follow this link to view the basic code for a recursive search of a disk drive which will be reused in this example with only a few modifications to output data to the Tree Insert routine. I will only be commenting the code where the new lines have been introduced and if you wish to consult the commented source code, follow the link above.

     When Delphi comes up you are presented with a blank form (if not choose New Application from the file menu). When you click on an area of the form the Object Inspector on the left of the screen gives focus to the form (rather than any controls such as buttons that might be on the form.) in the diagram below you can see the Object Inspector to the left of the form and you will notice that the the 'Events' tab is selected. Windows is an 'events' driven enviroment where everything that happens in a program can be thought of as a response to an 'event' (such as a button click). On the events tab for the Form itself, you can see that 'OnActivate' has been selected )with empty white space next to it. Down lower on the events panel you will notice that the OnCreate event for the form contains an entry. If you click on the grey 'OnCreate' area and then hit the key 'F1' the help section explains that the OnCreate event takes place once, when the form is created (when the program starts in this case) and this is the time to 'set things up' and get them ready for the rest of the 'event' that are going to take place in your program.

oncreate_event.jpg - 8949 Bytes

      If you doubleclick on the white area next to the event you are automatically taken to the code editor and for the FormCreate event code must be entered to initialize the binary tree. Using the 'new' procedure memory is allocated for the head and the tail pointers (which also creates the corresponding node structure the pointer is pointing to). For the code to work correctly the 'key' value (used to sort the tree, in this case strings representing filenames) must be set to nothing (''). Every other value will be greater than 'nothing' and thus first value on the tree will always be inserted on the right link of the head pointer, but I set the left link to point to 'tail' even though it is never used. Every new 'leaf' node created will have its left and right pointers aimed at the 'tail' node to make coding simpler and searching simpler as described above.



procedure TForm1.FormCreate(Sender: TObject);
begin
new(tail); new(head);
head^.filename:='';
head^.r:=tail;
head^.l:=tail;
end;



     Next for the purposes of this example, I am going to click on the Standard object tab, click on the button icon, and then click on the form to drop the button on the form. On the Object Inspector under the Properties tab, I am going to choose NAME and the button will be named 'FileSearch' and this automatically changes the CAPTION property to read 'FileSearch'. Double clicking on this button once again takes you to code editor and the following code is entered for this event. Note that I have chosen an arbitrary directory to search which I created on the 'f' drive called 'somefiles' into which I have stuffed a bunch of files and directories and subdirectories to test the tree code. A local boolean varible called 'found' is declared, and then the FileLook function is called. If the directory is valid the function searches the disk, fills the binary tree and then returns 'true' and a message box pops up which says 'DUN!', otherwise if the directory does not exist, false is returned and the FileLook function returns without doing anything, and an error message pops up which is self explanatory.



procedure TForm1.FileSearchClick(Sender: TObject);
var
found:boolean;
begin
Found:=FileLook('f:\somefiles\*.*');
{note that this is an abritrary folder}
If found then MessageDlg('DUN!', mtInformation, [mbOk], 0)
else MessageDlg('Directory does not exist', mtError, [mbOk], 0);
end;



     For this example I will be reusing the recursive disk search code (see the link above for commented source code) with a few modifications to allow the data to be inserted into the binary tree as the search progresses. The new lines of code added to this routine are commented below.



Function TForm1.FileLook(Filespec:string):boolean;
var
x:link;

{declare a local binary tree link...this will be used to receive the return value from the TreeInsert function so that the ModifiedDate value can be inserted into the correct node next to the filespec}

validres, ModifiedTime:integer; {create integer for modtime}
SearchRec : TSearchRec;
DirPath, FullName, Flname : string;
begin
   DirPath:=ExtractFilePath(FileSpec);
   Result:= DirectoryExists(DirPath);
   If not Result then exit;
   Flname:=ExtractFileName(FileSpec);
   validres := FindFirst(FileSpec, faAnyFile, SearchRec);
   while validres=0 do begin
      If (SearchRec.Name[1] <> '.') then begin
         FullName:=DirPath + LowerCase(SearchRec.Name);
         x:=TreeInsert(FullName, head);

{pass the filename and the 'head' (or 'root) pointer to the binary tree to the tree insert routine, and receive back in 'x' pointer the location at which the filename was inserted into the tree}

         ModifiedTime:=FileAge(FullName);{find mod date of file}

         x^.ModTime:=ModifiedTime;

{use the 'x' pointer value returned by the TreeInsert function to insert the value into the last modified time of the file into the correct node of the tree beside the filename}

         If (SearchRec.Attr and faDirectory>0) then
           FileLook(FullName+'\'+Flname);
      end; {end if}
   validres:=FindNext(SearchRec);
end; {end while}
end;



     The tree insert function is a simple routine which follows below...



Function TForm1.TreeInsert(Fname:string; q:link):link;

{pass the tree insert function the name of the file, and the 'head' or root pointer to the tree. The filename will function as the 'key' or sorting value for insertion into the tree for example 'apple' would be less than 'orange' files on the 'c:\' drive less than the 'd:\' drive etc.}

var st:link;

{create a local binary link to keep track of the position in the tree just before the spot where the insertion will take place...The search will continue as long as the insertion key value is less than or greater than the value in the 'q' pointer. The new value will be inserted as a 'leaf' in the tree at the spot where there is no 'branch' attached to the insertion node (the node then will be equal to the tail which is the signal to insert the new value ... to understand how this works you might try diagraming a very simply tree and then stepping through the code to see what happens graphically... It will be neccesary to have the address of the preceding link stored in 'st' so that it can then be adjusted to point to the inserted link}

begin
repeat
   st:=q;
   if fname<q^.filename then q:=q^.l else q:=q^.r;

{traverse the tree left (if the new value is less than current key in the tree, or right until it is greater until a 'dead end' is reached}

until q=tail; {'dead end' virtual null pointer}
new(q); q^.filename:=fname; {create a new node, insert key}
q^.l:=tail; q^.r:=tail;

{since the new key is inserted as a 'dead end' or 'leaf' node, set both pointers on the new node to point to 'tail'}

if fname<st^.filename then st^.l:=q else st^.r:=q;

{when 'q' became equal to 'tail' this is a signal that the previously stored pointer address in 'st' must be set to point to 'q' which takes the place in that position previously occupied by 'tail' - all new leaf nodes have their pointers set to 'tail' ... therefore one of the links of this stored previous value must now be set to point to this new 'q' node so that it becomes attached as a leaf on the tree ... if the value in 'q' is less than the value (filename) in this previously stored st pointer node then it is attached to the left pointer of 'st' (keep in mind that 'st' was previously pointing at 'tail' or nothing, and vice versa if the value is greater...}

TreeInsert:=q;

{return the pointer to the address of the new node so that the 'modified date' can be inserted next to the filename in the correct spot on the tree...}

end;



     The following is a simple function that prints out a tree in alphabetical order, and it is included to test the functioning of both the disk file search routine and the tree creation and insert routines. Once again I have dropped a button onto the form, given it the name TreePrint, and double clicked the button, and entered the following code for the button click event. a Textfile variable is declared. Note that the filename for the output file is once again arbitrary, the file is opened for writing and then a procedure called 'PrintTree' is called to do the actual output to the text file, which can then be read by notepad... The code for the PrintTree procedure then follows. This is a recursive procedure that first constantly calls itself over and over again until it reaches the very lowest value on the tree. Because it is recursive a lot of these procedural calls get 'stacked up' until the lowest value is reached (in otherwords there are no values attached to the final left pointer, other than the 'tail'). The accumulated procedural calls began to return, and in each case they fall down to the next line in the code which is a statement to write to the textfile, followed by a check of the right link for a greater than value. Once again, to understand what is happening here it might be a good idea to create a very simple tree and then follow the code graphically to see what is happenning. In the end a textfile is created with all the entries sorted alphabetically.



procedure TForm1.TreePrintClick(Sender: TObject);
var fs:textfile; begin
AssignFile(fs, 'c:\treeprint.txt');
Rewrite(fs);
PrintTree(head);
CloseFile(fs);
MessageDlg('TREE PRINT DUN!', mtInformation, [mbOk], 0);
end;


Procedure Tform1.PrintTree(q:link); {pass the 'head' pointer}
begin
if q<>tail then begin

{when the recursive calls finally hit a 'dead end' (the tail) the stacked up calls will begin returning and depending on whether or not they were called from the left or the right they will on returning hit the appropriate print statement}

PrintTree(q^.l);
Writeln(fs, q^.filename);
PrintTree(q^.r);
end; {end if}
end;



     If you are familiar with Delphi then you will already know that when you double click an object (such as a button or an event in the Object Inspector) Delphi automatically declares the Procedure and jumps to the correct point for that event in the code editor. However when you write your own functions and routines that are not associated directly with a button or event you must declare the Procedure or Function in the Forms type declaration section at the top of the unit. The functions FileLook, Treeinsert and PrintTree all require such manual declaration.


Index       Home




A Unified Field Theory

 failed_gravity_theory.gif - 10361 Bytes



The Unified Field Theory
is also available as a zip file -> unified.zip

Introduction :The Pioneer Effect and the New Physics. A brief description of the new physics required to explain the 'Pioneer Effect', which is the constant deceleration of space craft as they fly through space.




Principles of Evolution: A Study in the Evolution of Bedbugs


A couple of years ago my bedroom was invaded by bedbugs. There were two variant genetic lines. One type of bedbug was an enlongated, thin, tubular insect, and the second genetic line was a flat, perfectly circular insect. The result of the cross breeding of these two genetically distinct variants was the production of a bedbug with charcteristics of both, an enlongated, flat bedbug with a central bulge (such that the shape of the bedbug was somewhere between 'long' and 'circular'). The long skinny bedbugs were such strange and unfamiliar looking insects that at first I did not recognize them as being bedbugs, and considered them to be a seperate species of insect. However, as the photographs of bedbugs above indicate, enlongated and skinny bedbugs are not uncommon, and the photographs also show the variants that are produced by genetic combinations that result in an insect somewhere in between 'circular' and 'enlongated'.

Therefore it is my hypothesis that evolution occurs by means of the transfer of dominate genes, with the production of such dominant genes being the product of 'biological algorithms', a genetic software program that brings physical characteristics into harmony with behavior, such that when behavior changes, and a conflict then exists, this acts as a trigger and causes the release of dominant genes. The result is rapid evolution of species. The bedbug is a relatively new insect, not the product of millions of years of evolution but rather an insect that is evolving in real time. The newly emerging dominant form of the insect is the flat, round ciruclar insect, well adapted to living in human bedrooms (it is flat, rather than tubular, thus allowing it to hide in the smallest cracks, living a stealthy lifestyle, and it is round, which gives the insect a maximum storage capacity such that it must endanger itself only a few times a month by emerging to feed.

Other examples of rapid evolution include the development of long legs in an invasive species of toad in Australia. As the toads move into the mountainous regions of Australia, and their behvaior changes, making them 'climbing toads', over the course of just a couple of decades the toads in the highlands have grown long legs specially adapted to climbing. It is worth noting here that the toads are poisonous, and are a successful invasive species because they have no natural predators in Australia, and so it would not be the case that the toads with long legs were 'the fittest survivors', because all the toads are survivors, and therefore predation does not explain the rapid emergence and spread of such well adapted, long legged toads. Once again we see evidence for the existence of biological algorithms and the rapid spread of dominant genes through a population, which once introduced proceed to overwhelm the older genes which are being replaced (making toad long legged and a bed bug round and flat).


A Theological Experiment

My interest in pursuing the Unified Field Theory is spurred on by my need to discover the theoretical explanation of a new form of propulsion (as explained on this page: Why the Unified Field Theory?). The experiment involving the bedbugs came out of nowhere.

I also believe that it is possible to justify theological propositions using experimental methods. If a thing is an objective truth then it can be verified and proven true by means of experimentation. Such a theological proposition is of more value than a ‘divine revelation’, since such revelations depend upon nothing more than establishing authority figures which requires the creation of artificial hierarchies, for the only reason why I might be encouraged to believe an authority figure who orders me to believe unsubstantiated opinions is if I could somehow be convinced that this authority possessed a mind that was somehow superior to mine, and thus was fit to express opinions as though opinions were unquestionable facts and thus worthy of being elevated to the status of absolute dogma.

There is a self evident human inequality which is visibly apparent. Some people are ‘beautiful’ and thus are the true elite on this planet, and some people are not. It is this sexual inequality and the degeneration that follows upon beauty that is the true driving force behind all the evil that happens on earth. The need for ruthless oppression and the pursuit of wealth and the consequent creation of suffering and poverty which must follow upon this practice is for the purpose of creating an artificial alpha elite.

The true elites are the young and the beautiful. The artificial elite are the rich and the wealthy. The elite aging rich artificial alpha male has no good looks, for he is physically degenerate, but he will be found escorting beauty because he has a beautiful wallet. If he loses his wallet he will be found at home with all the other unattractive aged beta males sitting in a rocking chair watching reruns of Bonanza. No money, no sex. It is for this reason that the alpha males are found to be so ruthless and so violent in pursuit of their goal. The alpha male has fallen. The beta male has arisen and now the whole planet is full of ruinous destruction for it.

We see in religion a confused and contradictory reaction to this reality. On the one hand religion preaches a sexless heaven where castration and the clitorectomy create ‘pure spirits’. Muslims throw women under sacks. On the other hand religion supports hierarchy and is the prop of the elite alpha male. It is for this reason that religion is incoherent when it comes to speaking about sex.

Now we see this same principle at work in all of nature. Guppies dance and show off their colorful tails and the guppy who dances with the most colorful tail is the sexually successful guppy. Therefore it is the doctrine of the ruthless oppressor which teaches that the solution to human sexual violence is to be found in castration and the creation of pure ghosts. This would be equivalent to damning an aardvark for having the ‘sinful aardvark nature’ or prosecuting an anteater for the high crime of ‘ant genocide’.

Therefore it was my theological hypothesis that the correct solution to this problem is to give every guppy a beautiful colorful tail. I compare this solution to the classic religious solution which is to cut off every tail since having a tail is ‘sinful’. If having a tail is sinful then God must be sinful for no human being has any choice in deciding whether or not they would be born with a colorful tail, or whether they would not.

When I was young I was a beautiful guppy with a lovely tail. So everyone seemed to think. I am older now. My nose became very badly sunburned and destroyed. It seemed good to me to test my hypothesis by using these ‘biological algorithms’ to correct this problem. I healed half my nose as you can see by the line separating the still very dark patch on the side in the photograph below.





I documented my experiment on these pages. one two t hree four fi ve six


I have confirmed to my own satisfaction that my theological proposition is correct and that religious dogma is erroneous, being based as it was upon nothing more than ‘divine revelation’ which is just a form of opinionated speculation. For the time being I am not continuing this experiment, for I must wait until the weather on this planet improves, and the dark clouds of ruthless oppression break letting a little sun shine come through so that I can show the world the truth about God, by showing people how God goes about giving an old guppy back his beautiful colorful tail.


Until then I will have to sit on the sidelines, while all my scientific breakthroughs are deliberately ignored, while I wonder to myself what ever in the world could be wrong with the human race, because what this all will prove at the end of it all is that there definitely was something wrong with the people on this planet.