Ternary Search Trees

I looked online and (in two books) but did not find very good explanations of ternary search trees. Following is what I combined together from various sources:

Ternary Search Trees are specialized structures used to store strings so they are easily searchable.

1. The traversal of the tree proceeds character by character
2.  Each node can have up to three children ( as opposed to two in binary trees)

3. Middle node connection is dotted.
4. Nodes that form the end of a word are colored.

These are the rules for insertion:
An insert compares the current character in the string to be inserted (insert character) with the current character at the node (node character):

1. If the insert character is less than the node’s character then the insertion is made to the left (the line between nodes is solid)
2. If the insert character is greater than the node’s character then the insertion is made to the right(the line between nodes is solid)
3. If the insert character is equal to the node’s character then the insertion is made to the middle child and proceeds to the next character in the string to be inserted (or the next insert character).(the line between nodes is dotted)

Suppose you had the following words AB, ABBA, ABCD, and BCD and you wished to store them and then search for them.
We begin with AB. We insert A and then B is a child so a dotted line is drawn between the two :

The yellow circle indicates that the search string has terminated.
AB, ABBA, ABCD, and BCD
Now we wish to store string ABBA. We try to insert A. We find it is already there so we move to B in and notice that B is also already in the tree. Then we insert the rest of the string "ABBA" which is B and A :

AB, ABBA, ABCD, and BCD
Then we insert the next string: ABCD. We try to insert A and we find A. So we move to the next node in the tree B. Then we try to insert B and we find B in the tree so we move to the next node in the tree, again a B. Then we try to insert C and we find that we are on the second B or the third node. So to insert C we take a right branch and insert C and then insert D.

AB, ABBA, ABCD, and BCD
Now we try to insert BCD and as we enter the tree we encounter the first node character A which is not the same as the first character of the string BCD which is B. We insert B to the right branch of A so:

 A search compares the current character in the search string (search character) with the character at the node (node character):

1. If the search character is less than the node’s character then the search goes to the left
2. If the search character is greater than the node’s character then the search goes to the right
3. If the search character is equal to the node’s character then the search goes down to the middle child and proceeds to the next character in the search string (or the next search character).

If we searched for the string ABBA we would see the following path followed in blue:

If we searched for ABD we would be unable to find it:

Another example of a ternary search tree is the following:

In the above don’t be surprised by the far left location of the first word “as” it is merely shifted left.

How Men Told Longitude

The question of how to tell longitude accurately was contested for a very long time. People had figured out how to tell latitude by use of a device that would give them the angle between a star and a horizon (usually the sun or the north star). In other words they could tell where they were when moving North or South.
They just didn't know how to tell precisely where they were when going East to West. They could divide their sphere into longitudes but they couldn't tell precisely where their ship was during its travels:

Earth Divided into Longitudes: A Polar Projection or Looking On Earth From Above

We were interested in finding the distance we had traveled and we did it by dividing the earth into equal parts (longitudes).

The first workable answer used by the mariners came with the invention of the clock (or the chronometer) by John Harrison.

The Harrison Chronometer or clock or fancy term "chronometer" (chrono:time; meter:measure-er).Perhaps use of easier, briefer words could make knowledge more accessible?

This is perhaps how they did it:

Once again we used the angle between the sun and the horizon. For example you expect the sun to be straight over head when its noon and make an angle of 90 degrees with the horizon. At 11 o Clock you expect it to be at an angle of 60 degrees.

The Sun And Its Journey through the day

The sun and earth actually looks so when the earth is rotating on its axis :

Sun lights up the earth as it rotates

As you can see below the sun is automatically demarcating the longitude for us :

Sun is in effect marking the longitude for us

How do we use this information to tell what longitude we are in? First we pick a reference point : in the case of human kind we picked Greenwich, London.

Reference Point London If you look at Earth From Above

This is because England developed this method and her sailors and navy has been renowned for a long time; btw. that is also the origin of Greenwich Mean Time or GMT as the point of reference.

We set our clock (or chronometer) to the time in London.  

Then we go with our clock (or chronometer) set to London time (Greenwich Mean Time or GMT) on board a ship. We then travel far away from London and head into the Atlantic ocean.

We are interested in finding our Longitude : Or Angle Between the Sun at Noon (In London) and Our Position

When our clock (set to the time in London) says 12 o' clock (noon) we expect the sun to be directly over London. In other words we expect the sun to be directly aligned with London:

This is What Earth Looks Like When the Sun is Directly Above London

We know that since our on board clock(set to London time) which we carried with our ship , says it is noon it means that in London the sun would be directly overhead or as we say at 0 degrees Longitude (since we decided it was a reference point). Knowing that if London is at 0 degree longitude? (ground zero) where are we located or rather what is our longitude compared to London's?

To find that out we go on the deck of our ship and with our sextant (or any of the measuring devices) we measure the angle of the sun with the horizon at our location:

Suppose our sextant tells us that the angle of the sun with the horizon is 70 degrees. This where we would be on earth :

This is where we will be in the Atlantic Ocean with the Sun at 70 degrees overhead and our clock saying its noon in London

This means that we are not located too far away (from London) and it does look like the sun is almost over our heads as well and the earth rotating in due time will have the sun above our heads very soon. Remember this is what the sun looks like when it is at 70 degrees:

Sun At Our Location aboard a ship in the Atlantic

We are interested in finding out the longitude though which is the following angle marked with a question mark:

The longitude would be the angle between us and London (our reference) marked in red question mark.

Our longitude can be told by looking at the angle between the sun and our our longitude (our position on the polar projection of the map).

If you look at the above and take out the triangles formed between the sun, the ship and the location of London:

Focusing on Lines In the Map Above we Get The Above Similar Triangles.

If A is the location of London (as in the map above) and B is the location of the ship. D is the pole and the C is the location of the Sun. By Side Angle Side(SAS) (Side AB is common, Angle( DAB) and Angle(CAB) are same and sides AD and AC are proportional) we see that Triangle ADB and Triangle ACB are similar triangles. By similar triangles we know that Angle (ADB) and Angle (ACB) are equal. Angle (ABC) is the angle of the sun with the horizon which we found to be 70 degrees (using a sextant or any other measurement tool). If we know Angle (ABC) (70 deg) we know that Angle (ACB) is 90-70=20 degrees.

So Angle (ADB) or our angle with London's Longitude (Longitude 0) will be 20.

Thus we can tell our position on the longitude with great precision using the clock (set to the time in London and using a sextant or any other device that measures the angle of the sun with the horizon). But an angle is not very useful. We really want to know how far from London we really are. We were only trying to find this angle so we could tell the longitude (or the partition that earth was divided into) . Once we know this angle we or partition we could tell how far we are from London.

Once you have found the angle you may wish to know how far you are from London in miles. If you want to know the distance then knowing the angle is not enough. You must know the latitude as well because the distance varies from latitude to latitude:

Distance between Longitudes varies as Latitude Varies

In our case if we were at the same latitude as London (50 degrees) then we would be approximately (44.55x2=89 miles) 89 miles west of London, perhaps. Again we were able to tell all of this because we had a watch that was set to London time (GMT) which allowed us to discern our position relative to the city.

The struggle to come up with accurate measurements of longitude took centuries and this method came about in the 1700s after many other schemes failed or were found unworkable. The greatest minds human kind had ever produced thought about this problem and both Galileo and Huygen proposed their solution (even Newton is said to have tackled this problem though his idea was not used). Galileo proposed that we use the moons of Jupiter but it is said that his relations with the Church caused that idea to go unnoticed. Today we use satellites which can accurately pin point our position in orbit. They have been in use for over half a century (first in military and only recently in civilian use). Only the most learned of civilizations have their own systems (US, EU, Japan, Russia, China and India!). All their systems are therefore likely to be mostly redundant, however it would serve all of them well if they cooperated and made their systems into extensions (rather than as mere alternatives or backups or competing systems).

Some 300 years later we use GPS!

p.s. if the reader would be kind enough to please correct any errors if possible that would be great. One is using "we" when speaking of discoveries and methods used by a prettier and smarter and gentler people; one apologizes for this presumption and hopes all are become gentle and pretty and smart. It is also quite lamentable that one comes from a society where people are merely catching up with the developed world and are unable to make original , positive and significant contributions of their own. We hope all are worthy and able to make all places not merely better but perfect for love and life.

Measuring the Circumference of the Earth

How did early man attempt to discover the circumference of the earth without ever traveling it?

This is how it was accomplished by a man without much apparatus. Eratosthenes simply needed the sun, a deep well and a wall. Eratosthenes was in Alexandria , Egypt the home of the best sailors and navigators of the age. He was getting lots of first hand geographical information from every other man on the street with a desire to explore the earth. Alexandria (at that time) had the best stocked library and museum in the world.

On 21st of June (250 BC), Eratosthenes noticed that the sun at Syene was so straight over head that it completely lighted up a deep well. If that well but continued to the center of the earth the shaft would be a sunlit radius without a shadow.

But Eratosthenes was sure that at this very moment in Alexandria north of here, the walls were all casting shadows. This is because the earth is spherical. Due to the curving of the earth if everything in Syene cast no shadows then in Alexandria everything had to meet the sun's rays at an angle. As depicted below:

He calculated (see aside for details)  the angle (O) the wall (at Alexandria) made with the sun's rays and it was 7.2 degrees. After finding Angle(O) he also knew from the following geometric truth that Angle(C) at the center of the earth would equal to Angle (O):

Parallel lines when intersected have equal opposing angles.

Once he knew the length of the arc (500 miles distance between Syene and Alexandria), and the angle(O=A=7.2 degrees) it was easy to find the circumference of the circle :

Eratosthenes calculated the circumference of the earth to be 25,000 miles (using the above ratio). Modern computations put the circumference of the earth at 24,860 miles. After Erastosthenes geographers came up with a figure of 18,000 miles (which Columbus used) and Ptolemy advocated. It overrode Eratosthenes' figure perhaps because men really wanted to circumnavigate the earth (and preferred a shorter inaccurate estimate rather than a more accurate estimate perhaps?).

[Aside : How did Erastosthenes Find the Angle (O) or Angle(theta) as below]
Find the height of the wall : h.
Find the length of the shadow : s.
Calculate angle(theta) using tangent equation.  

[End Aside: How did Erastosthenes Find the Angle O or theta]
[Begin Aside: How did Eratosthenes know at what time he ought to measure the angle At Alexandria]
Perhaps a way of coordinating times over large distances by means of flags placed on horizons. You could raise the flag from source. When viewers view it upon horizon they raise their flag to trigger the next flag holder on a horizon to raise his flag. It would need 50 flag bearers to communicate to a spot 500 miles away. Other communication devices could be mirrors (to shine light to the next horizon) , smoke signals etc. One person could see when the light reaches the bottom of the well. Then signal to the flag bearer on the horizon by waving his flag. The flag bearer on the horizon could signal the person on the next horizon and so on till the person by the wall sees the flag on the horizon and he could measure the angle at that point. Thus we would know precisely when to measure on both ends.
If anyone can provide a better answer or improve on this one that would be great.
[End Aside: How did Eratosthenes know at what time he ought to measure the angle At Alexandria]

Today men may use satellites and fly in spaceships to outer space and view earth and other planets far beyond earth. (well not all men, just the men who are blessed and have excellent space programs).