 |
Administrators :saucer, Iseason, us2u | |
 |
Forum Physiks Causali |
Not logged | Login
|
|
Online:There are 5 online. Click here to see more | |
Register | 
Profile | 
Private messages | 
Search | 
Online |  Help
| Create a free blog | ||
 | ||
|  |  |
Email Notification
Warn moderators| Author : | Topic: mathematics | Bottom |
| ferme Posts : 85 |
|
| 360pan gold Posts : 14  |
http://www-groups.dcs.st-and.ac.uk/~history/Indexes/Math_Physics.html ]at Einstein hyperlink After the major step of the equivalence principle in 1907, Einstein published nothing further on gravitation until 1911. Then he realised that the bending of light in a gravitational field, which he knew in 1907 was a consequence of the equivalence principle, could be checked with astronomical observations. He had only thought in 1907 in terms of terrestrial observations where there seemed little chance of experimental verification. Also discussed at this time is the gravitational redshift, light leaving a massive body will be shifted towards the red by the energy loss of escaping the gravitational field. 360 --Last edited by saucer on 2007-09-11 00:17:50 -- |
| saucer admin Posts : 673 A Good Tautology is Hard to Find!  |
|
| saucer admin Posts : 673 A Good Tautology is Hard to Find! |
|
| 3141582n Posts : 6  |
Courtesy: mathforum.org Binary Search Trees Date: 02/06/2003 at 18:47:59 From: Ben Ullian Subject: C++ and AP Computer Science Exam Consider the following characters to be entered into an empty binary search tree. 'A' 'B' 'C' 'D' 'E' 'F' 'G' Which of the following sequences represent(s) an order of insertion that will result in a binary search tree where each node in the tree has the same number of nodes in its left and right subtrees? I. 'D' 'B' 'F' 'A' 'E' 'C' 'G' II. 'D' 'E' 'F' 'G' 'C' 'B' 'A' III. 'D' 'F' 'G' 'E' 'B' 'A' 'C' (A) I only (B) II only (C) III only (D) I and III only (E) I, II, and III No matter which order you use, you always end up with a binary tree that has even subtrees on both right and left sides. Since there are 7 elements, the tree should fully fill the first three levels. Without any significance to the letters (they are said to be "just characters"), the order doesn't seem to have any meaning. In terms of binary *search* trees, the process used is to divide a list into halves, choose the half with the thing you want, then split that into halves and select recursively until you end up with the thing you are looking for. This makes a type of tree (splitting) formation, but I do not think that this applies here because you don't know the character you are "searching" for. Date: 02/07/2003 at 03:21:58 From: Doctor Jacques Subject: Re: C++ and AP Computer Science Exam Hi Ben, There are two different things to consider in binary trees: (1) How we search a binary tree for a given element. (2) How the tree is built incrementally by inserting elements. The question here relates to problem (2). Note that there may be many different search trees for the same data, depending on the order in which elements are inserted. The easy way to build a tree is best illustrated by considering the second sequence: 'D' 'E' 'F' 'G' 'C' 'B' 'A' We start by inserting D - there is no choice available in this, we just store D as the root: D Now we insert E. We do that by searching the tree for E; if we don't find it, we insert it at the next empty place where it would have to be. As E > D, we have to move right from D, and we find an empty place, so we store E there: D \ E To insert F, we start at D, move right, find E, move right (since F > E), and find an empty place, so we store F there: D \ E \ F The procedure for G is similar: D \ E \ F \ G To insert C, we start at D, and, since C < D, we look left and find an empty slot: D / \ C E \ F \ G To insert B, we follow the path D -> C -> (left) : D / \ C E / \ B F \ G And finally, we insert A by following the path D -> C -> B -> (left) D / \ C E / \ B F / \ A G You will notice that, in this case, some nodes do NOT have the same number of children in their left and right subtrees; for example node C has 2 children on the left subtree and none on the right subtree - we say that the tree is not "balanced." I'll let you use the same procedure for the other two insertion sequences. If the tree were balanced, there would be just 3 levels: we could find an element by doing at most three comparisons. In the example above, we may, in some cases, need 4 comparisons. If the tree is to be used intensively, it is best to have it balanced. The procedure described above is the "easy" way to insert elements. There are other, more complicated procedures that can be used to build the tree in such a way that it is almost balanced; this improves performance on searching. One of these methods involves re-arranging some nodes at each step in order to keep the tree balanced. You will find easily that (with this easy procedure) the worst case happens when the elements to be inserted are already in ascending or descending order - in that case, you end up with a linear structure, in which each node has only one child; it's no longer a "binary" tree. On the other hand, if the elements are inserted in random order, there is a good chance that the resulting tree will be decently balanced, but you can never be sure of that. Courtesey: mathforum.org --Last edited by 3141582n on 2008-06-08 20:04:23 -- |
| | |
Get a free forum!
AceBoard Free Forum v 5.3
Download Premium Web Templates!