drzewo binarne - dodawanie wg poziomów Opcje

[megasinski]

Witam
Mam pewien problem
Stworzyłem w mysql tabelę do której chciałbym wstawiać rekordy w pewien określony sposób.
Ma to być hierarchia binarna, czyli drzewko z dwoma odnogami za każdym razem.

tabela posiada kolumny id, id_parent, right, left

Do tabeli mają być dodawane nowe rekordy w taki sposób, aby najpierw, niezależnie od tego jak aktualnie wygląda struktura, rozpoczynając od wybranego rekordu, najpierw sprawdzał pierwszy poziom pod wybranym rekordem i jeśli jest wolne miejsce to w pierwszej kolejności dodawał nowy rekord do prawej odnogi a jeśli ta jest zajęta, to do lewej. Jeśli natomiast w poziomie pierwszym nie ma już miejsca to przechodzi do poziomu drugiego itd.

To co do tej pory wykombinowałem to przynosiło taki efekt, że najpierw sprawdzał prawą odnogę, jeśli była wolna to dopisywał, jeśli nie to sprawdzał lewą i jeśli była wolna to dopisywał, a jeśli nie to wtedy wchodzi w poziom niżej i do tego miejsca było OK, ale dalej kiedy sprawdził rekord w drugim poziomie to juz nie przechodził do następnego rekordu w tym poziomie tylko szedł niżej w będącej już odnodze i praktycznie pomijał pozostałe rekordy w danym poziomie.

Chodzi mi o to, żeby najpierw sprawdził poziom 1 pod jakimś tam rekordem, jeśli jest pełny to wtedy poziom 2, jeśli ten jest pełny to przechodzi do poziomu 3 itd.
Czy da się coś takiego stworzyć w PHP? Jeśli tak to w jaki sposób?
Pomocy please.
Mam nadzieję, że nie zagmatwałem pytania.

[megasinski]

Idea jest dobra...
tylko jeszcze jeden mały problem.
Powiedzmy, że niektóre odnogi zostaną rozwinięte (przez kogoś)tak jak np. 3-6-10 i jeśli chcę dodać losowo kolejny ID to chcę żeby uzupełnił pierwszy pusty na najbliższym poziomie, czyli w tym wypadku będzie to drugie ramię trójki i tam wejdzie 11.
W tym momencie nawet jeśli dodam to pole, to wywołanie rodzica będzie błędne no i w wielu przypadkach dziecka też.

[timon27]

Powiedzmy, że niektóre odnogi zostaną rozwinięte (przez kogoś)tak jak np. 3-6-10...

1. drzewo musi mieć na samym początku określony korzeń.
Czyli musi istnieć pole id=0, sytuacja 3-6-10 nie jest dopuszczalna
2. Systuacja 0-3-6-10 również nie jest dopuszczalna, bo 10 powinno być dzieckiem 5 której nie ma, więc już wcześniej ktoś coś namieszał z drzewem.

Generalnie zakładamy że drzewo ma poprawną strukturę.
Wtedy dodanie w najwyższym miejscu, najbardziej na lewo (tak jak chcesz) = dodanie pola o najmniejszym niewykorzystanym id.
Dodanie dziecka pola o id=n to stworzenie pola o id=2n (lewe) lub 2n+1 (prawe).