„2-3 fa” változatai közötti eltérés
| [nem ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
37. sor:
Amennyiben a beszúrandó kulcs helyének felmenője egy 2-csúcs, a csúcs kiegészül egy 3-csúccsá. Ennek kulcsait az új levél helyzete határozza meg:
* Ha a beszúrt érték mindkét leszármazott értékénél kisebb, a régi 2-csúcs kulcsa az új csúcs jobb oldali kulcsa lesz, a bal oldali kulcs pedig a régi 2-csúcs bal oldali leszármazottának értéke.
* Ha a beszúrt érték a két leszármazott értéke közé esik, a régi 2-csúcs kulcsa az új csúcs bal vagy jobb oldali kulcsa lesz
* Ha a beszúrt érték mindkét leszármazott értékénél nagyobb, a régi 2-csúcs kulcsa az új csúcs bal oldali kulcsa lesz, a jobb oldali kulcs pedig a beszúrt érték.
====Csúcsvágás====
Ha a beszúrandó kulcs helyének felmenője egy 3-csúcs, azt nem tudjuk tovább kiegészíteni, így a csúcsvágás módszerét kell alkalmazni. A mellékelt ábrákon a csúcsvágások helyét a piros szaggatott vonalak jelölik. A csúcsvágáshoz megállapítjuk az új levél helyzetét a három, már fában levő levélhez képest. Az így kapott négy levelet két csoportra osztjuk, a két kisebbiket az első csoportba, a két nagyobbikat a másodikba. Így két 2-csúcsot tudunk létrehozni, melyeknek a kulcsa a saját csoportjuk nagyobbik eleme. A második csoport kisebbik eleme a medián - az első kulcs kisebb nála, a második nagyobb, tehát ennek a két leszármazottja lesz a két 2-csúcs. Ez többféleképpen történhet:
| |||