How to balance binary tree in PHP without rotating parent?

Question

I will try to make myself as clear as possible. Based from Adjacency List Model: http://articles.sitepoint.com/article/hierarchical-data-database

I need a way to balance this tree

     0 
    / \ 
   1   2 
  /   / \ 
 3    4  5 
       \  \
        6  7

to something like:

        0 
      /   \ 
     1     2 
    / \   / \ 
   3   4 5   6
  /
 7

Based from the sample Code:

<?php 
function display_children($parent, $level) { 
   $result = mysql_query('SELECT title FROM tree '. 
                          'WHERE parent="'.$parent.'";'); 
   while ($row = mysql_fetch_array($result)) { 
       echo str_repeat('  ',$level).$row['title']."\n"; 
       display_children($row['title'], $level+1); 
   } 
} 
?>

I modified the code so it can output a flat html table like this:

$super_parent = '0000' left Node entries into flat list:

 ____________________________________________________
| No. | Date of Entry       | Account ID  | Placement|
------------------------------------------------------
| 1   | 2010-08-24 11:19:19 | 1111a       |    a     |
| 2   | 2010-08-24 11:19:19 | 22221a_a    |    a     |
| 3   | 2010-08-24 11:19:19 | 33_2aa      |    b     | 
| 4   | 2010-08-24 11:19:19 | 33_2Ra      |    a     | 
| 5   | 2010-08-24 11:19:19 | 22221a_b    |    b     |
| 6   | 2010-08-24 11:19:19 | 33_2ba      |    a     |
| 7   | 2010-08-24 11:19:19 | 33_2bb      |    b     |
------------------------------------------------------

But I need a way to reorganize all this into a balanced tree without moving or rotating the parent. Although I can think of creating a duplicate table in the db and do a second query to display or create another Binaray tree, I thought it may be possible to reorganize a flat tree like this into:

        0 
      /   \ 
     1     2 
    / \   / \ 
   3   4 5   6
  /
 7

From left to right. 0 represents the parent or super_parent 0000.

The reason I would like to do this is so I can create a virtual tree from the original tree that will be the basis of another algorithm in my project.

Thanks in advance.

Bob

Answer 1

I have decided to answer my own question with this discovery. In General, this can be called, the "Distribution Method" of recursively automating a Balanced Binary Tree from left to right. This algorithm makes sure to take care of 64 pairs per level and the rest would be flushed out : )

<?php
function makeBTree($load, $colMult, $levCount){
    $exCol=$colMult;
    if($load<=$colMult){
        $exCol=$load;
    } if($load>0) {echo "Load: $load ";} else {echo "Load: 0 ";}
    echo "Level: $levCount ";
    echo "Columns: ";

    for($i=1;$i<=$exCol; $i++){

    }

    if($i<=64) {
        echo "<font color='violet'>".($exCol)." candidate for pairing if count matches with TEAM B</font> \n";
    } else {
        $limiter = ($i)-64; 
        echo "<font color='orange'>$i</font> - <font color='black'>64</font> = 
        <font color='blue'>$limiter auto-flushout</font> \n";   
    }

    $load -=$colMult; if($load>0) {echo "Load: $load ";} else {echo "Load: 0";}
    echo "<br />\n";

    if($load>=1){
        makeBTree($load,$colMult*2, $levCount+1);
    }
}

makeBTree(1000,1,1);
?>

The left frontline node of super parent should be counted as 1. For 8 entries left, just call:

makeBTree(8,1,1);

Thanks

Oliver Bob Lagumen