Arborele 2-3

Această intrare despre subiectul matematic al informației și comunicării este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia .

Arborele 2-3

Un arbore 2-3 este un tip de structură de date pentru arbore care are următoarele proprietăți:

• fiecare nod poate avea 2 sau 3 copii
• toate frunzele sunt la aceeași adâncime
• elementele sunt cuprinse în frunze
• cheile cresc în frunze de la stânga la dreapta

De sine ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">f</span></span>}}${\ displaystyle f} indică numărul de frunze și ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">h</span></span>}}${\ displaystyle h} înălțimea copacului, se menține următoarea inegalitate:

${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}^{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">h</span></span>}}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\le </span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">f</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\le </span></span>{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">3</span></span>}}^{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">h</span></span>}}}${\ displaystyle 2 ^ {h} \ leq f \ leq 3 ^ {h}}

Operațiunile de căutare, inserare și anulare au un cost, în cel mai rău caz, ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">SAU</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">(</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">L</span></span>}\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">sau</span></span>}\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">g</span></span>}\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">n</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">)</span></span>}${\ displaystyle O (logn)} .

Bibliografie

• (EN) Robert Sedgewick , Balanced Trees in Algorithms, Addison Wesley, iunie 1983, ISBN 978-0-201-06672-2 .

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere în arborele 2-3

linkuri externe

• ( RO ) 2-3 copaci ca arbori de căutare , pe cs.engr.uky.edu . Adus pe 29 august 2012 (depus de „url original 19 decembrie 2012).

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică