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

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


テーブル構造


このテーブル構造はそれぞれノード 左、中央、右の 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($a); $i ) {<br /> $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*
[左] =>