小さなアルゴリズムに関する質問を教えたいと思います。

ちょっとしたアルゴリズムの問​​題を教えたいと思います
ツリーフローチャート:


テーブル構造


このテーブル構造はそれぞれノード 左、中央、右の 3 つの子ノードがあります。要件は、ノードを適切な位置に挿入することです。挿入ルールは、id=1 から開始し、その下にある 3 つの子ノードを見つけることです。 3 つの子ノードがすべて存在する場合は、3 つの子ノードの子ノードをそれぞれ検索します。子ノード、3、4 のデータがなくなるまで
を挿入し、2、5、6、7 の子ノードも存在することを検索してから、子を検索します。ノードが 3 で、8 のみの場合は、挿入された 3 の中央の子ノードを見つけることができます。当然のことですが、データが多ければ多いほど検索数も増えます。考えてみたのですが、よくわかりませんでしたので、どなたか具体的なアルゴリズムを教えていただければ幸いです。

-----ソリューションのアイデア----------------------
以前にオンラインで見つけましたPHP のバイナリ ツリーを少し変更して 3 進ツリーに変えました。実際に、 center
class Node {
public $data = null;

 public $ を追加しました。 parent = null;<br> public $left = null;<br> public $center =null;<br> public $right = null;<br>}<br><br>function build_cbtree($a) {<br> $root = new Node();<br> $root->data = $a[0];<br> for ($i = 1; $i <count></count> $node = new Node();<br> $node->data = $a[$i];<br> insert_node($root, $node);<br> }<br> return $root; <br>}<br><br>function insert_node($root, $inode) {<br> $queue = array();<br> array_unshift($queue, $root);<br> while (!empty( $queue)) { <br> $cnode = array_pop($queue);<br> if ($cnode->left == null) {<br> $cnode->left = $inode;<br> $ inode->parent = $cnode;<br> return $root;<br> } else {<br> array_unshift($queue, $cnode->left); {<br> $cnode->center; = $inode;<br> $inode->parent = $cnode;<br> return $root;<br> } else {<br> array_unshift($queue, $cnode->center);<br> } <br> if ($cnode->right == null) {<br> $cnode->right = $inode;<br> $inode->parent = $cnode;<br> return $root;<br> } else {<br> array_unshift($queue, $cnode->right);<br> }<br> }<br> return $root;<br>}<br>// 幅優先トラバーサル (最初に 1 つのレベルを走査し、次に次のレベルを走査します)<br>function bf_traverse($root) {<br> $queue = array();<br> array_unshift($queue, $root);<br> while (!empty( $queue)) {<br> $cnode = array_pop($queue);<br> echo $cnode->data . " ";<br> if ($cnode ->left !== null) array_unshift($ queue, $cnode->left);<br> if ($cnode->center !== null) array_unshift($queue, $cnode->center) ;<br> if ($cnode->right) !== null) array_unshift($queue, $cnode->right);<br> }<br>}<br><br>$a = array(1 ,2,3,4,5,6,7 ,8);<br>//まず配列を三分木に変換します<br>$root = build_cbtree($a);<br><br>echo "< pre>";<br>print_r($root );<br>echo "

";
bf_traverse($root);

/*$root データが多すぎる場合は出力されません Out
幅に応じて-first traversal ルールでは、
1 2 3 4 5 6 7 8
*/

//この時点で $root は三分木です
//実際には 9 を挿入します、 build_cbtree メソッドの for ループのコードを繰り返すことです
$node1 = new Node();
$node1->data =9;
insert_node($root, $node1);

echo "

";<br />print_r($root);<br />echo "

";
bf_traverse($root);
/*
ノード オブジェクト
(
[データ] => 1
[親] =>
[左] => ノード オブジェクト
(
            [データ] => 2
[親] => ノード オブジェクト
*RECURSION*
[左] => ノード オブジェクト
(
[data] => 5
[親] => ノード オブジェクト
*RECURSION*
[左] =>
[中央] => ;
[右] =>
)

[中央] => ノードオブジェクト
(
[data] => 6
[親] => ノードオブジェクト
*RECURSION*
[左] =>