Algoritmi un datu struktūras. Vairāk zaru koki

Apskatīsim trīs – četrpunktu mezglus, kur var saturēt divas vai trīs atslēgas. Trīspunktu mezglam ir trīs izejošie zari, viens zars visām ieraksta atslēgām, kuras ir mazākas nekā abas pārējās atslēgas, otrs zars visām ieraksta atslēgām, kuras ir lielākas vai vienādas ar pirmā zara ieraksta atslēgām, bet mazākas par trešā zara ieraksta atslēgām un trešais zars, kur ieraksta atslēgas ir lielākas vai vienādas ar otrā zara ieraksta atslēgām. Līdzīgi ir ar četrpunktu mezglu, kuram ir četri zari, pa vienam katram intervālam, kurš noteikts ar viņa trijām atslēgām.
Lai iekļautu 70, 2-3-4 kokā mums ir nepieciešams veikt meklēšanu un tad iekļaut to. Viegli var redzēt, kas darāms ja mezgls, kurā mēs beidzam meklēt ir divpunktu, vienkārši pārveidojam to par trīspunktu mezglu. Piemēram, 240 varētu pievienot kokā, kurš attēlots zīmējumā, pievienojot zaru mezglam, kas satur 190. Tādā pašā veidā trīspunktu mezglu var pārveidot četrpunktu mezglā. Bet kā mums būt ja jauns mezgls ir jāieliek četrpunktu mezglā? …