Na którym poziomie w drzewie leży element?

[Auilman]

Witam,

mam kompletne drzewo binarne o \(\displaystyle{ p}\) poziomach. I muszę odpowiedzieć, na którym poziomie leży element \(\displaystyle{ 229}\). Jest na to jakiś wzór czy trzeba sprawdzać po kolei każdy poziom. Pomocy, jutro mam klasówkę!

[ecres]

Obczaiłam co to jest drzewo binarne kompletne. Skoro ten element na samej górze to jest poziom zero to wygląda to tak, że liczbę elementów na danym poziomie drzewa można policzyć ze wzoru \(\displaystyle{ 2^{p} }\) (o ile jest cały zapełniony).
A to mi wygląda na ciąg geometryczny, więc znalazłam sobie na necie wzór na sumę ciągu geometrycznego
\(\displaystyle{ S_{n} =a _{1} \cdot \frac{1- q^{n} }{1-q} }\)
ale w naszym ciągu trzeba doliczyć jeszcze ten element z poziomu zerowego (więc dodałam jedynkę na początku) i to będzie
\(\displaystyle{ S _{p} =1+2 \cdot \frac{1- 2^{p} }{1-2}}\)
i dalej liczę
\(\displaystyle{ 1+2 \cdot \frac{1- 2^{p} }{1-2}>229}\) ,gdzie \(\displaystyle{ p}\) dla nas oznacza numer poziomu, więc trzeba dodać że szukamy tylko najmniejszej liczby naturalnej spełniającej to równanie, nie wiem tylko jak to zapisać w sposób matematyczny
\(\displaystyle{ 1-2(1- 2^{p}) >229}\)
\(\displaystyle{ 1- 2^{p} <-114}\)
\(\displaystyle{ 2^{p}>115 }\)
\(\displaystyle{ 2^{7} >115> 2^{6} }\)
A więc element 229 leży na poziomie 7.