Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think I've found the answer, or at least a facsimile. </p> <p>Assume the tree nodes are numbered, starting at 1, top-down and left-to-right. Assume traversal begins at the root, and halts when it finds node X (which means the parent is linked to its children). Also, for quick reference, the base 2 logarithmic values for nodes 1 through 12 are:</p> <pre><code>log2(1) = 0.0 log2(2) = 1 log2(3) = 1.58 log2(4) = 2 log2(5) = 2.32 log2(6) = 2.58 log2(7) = 2.807 log2(8) = 3 log2(9) = 3.16 log2(10) = 3.32 log2(11) = 3.459 log2(12) = 3.58 </code></pre> <p>The fractional portion represents a unique diagonal position (notice how nodes 3, 6, and 12 all have fractional portion 0.58). Also notice that every node belongs either to the left or right side of the tree, depending on whether the log fractional component is less or great than 0.5. Anecdotes aside, the algorithm for finding a node is then as follows:</p> <ul> <li>examine fractional portion, if it is less than .5, turn left. Else turn right.</li> <li>subtract one from the whole number portion of the log, stop if the value reaches zero.</li> <li>double the fractional portion, and start over.</li> </ul> <p>So, for example, if node 11 is what you seek then you start by computing the log which is 3.459. Then...</p> <ol> <li>3-459 &lt;=fraction less than .5: turn left and decrement whole number to 2.</li> <li>2-918 &lt;=doubled fraction more than .5: turn right and decrement whole number to 1.</li> <li>1-836 &lt;=doubling .918 gives 1.836: but only fractional part counts: turn right and dec prior whole number to 0. Done!!</li> </ol> <p>With appropriate accomodations, the same technique appears to work for any balanced n-ary tree. For example, given a balanced ternary tree, the choice of following left, middle, or right edges is again based on the fractional portion of the log, as follows:</p> <pre><code>between 0.5-0.832: turn left (a one-third fraction range) between 0.17-0.49: turn right (another one-third fraction range) otherwise go down the middle. (the last one-third range) </code></pre> <p>The algorithm is adjusted by multiplying the fractional portion by 3 instead of 2. Again, a quick reference for those who want to test this last statement:</p> <pre><code>log3(1) = 0.0 log3(2) = 0.63 log3(3) = 1 log3(4) = 1.26 log3(5) = 1.46 log3(6) = 1.63 log3(7) = 1.77 log3(8) = 1.89 log3(9) = 2 </code></pre> <p>At this point I wonder if there is an even more concise way to express this whole "log-based top-down selection of a node." I'm interested if anyone knows...</p>
    singulars
    1. This table or related slice is empty.
    1. POApplying a Logarithm to Navigate a Tree
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USBrent Arias
    1. USBrent Arias
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POApplying a Logarithm to Navigate a Tree
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload