B drevo

Dodajanje elementa

1. Najprej poiščemo vozlišče, kamor naj bi bil element vstavljen. Ko ga vstavimo se lahko vozlišče razraste čez dovoljenih 2d elementov. V tem primeru izvršimo še naslednji korak (drugače smo končali).
2. Če ima vozlišče preveč elementov (2d + 1) potem ga razdelimo v dve vozlišči tako, da vsako izmed njiju vsebije d elementov en element (sredinjski glede na urejenost) pa pomaknemo na parent vozlišče in ga ustrezno umestimo v seznam. V primeru, da pride tudi to vozlišče v ilegalno stanje, postopek ponovimo tudi tu. To počenmo, dokler ne pridemo do najvišjega (root) vozlišča. V primeru, da tudi to vozlišče preide v ilegalno stanje, ga razdelimo, sredinjski element pa vstavimo v novo vrhnje vozlišče (stopnja drevesa se poveča za ena).

Brisanje elementa

1. Poiščemo element in ga odstranimo. Če nobeno vozlišče ni v ilegalnem stanju (število elementov pade pod d), potem smo končali, drugače nadaljujemo.
2. Ilegalno stanje vozlišča lahko popravimo na dva načina:
   1. Sosednje vozlišče lahko prenese enega ali več elementov v vozlišče, ki mu elementov trenutno primanjkuje. To lahko stori le v primeru da tudi samo ne zaide v ilegalno stanje.
   2. Če sosednje vozlišče nima zadosti elementov za popravilo stanja po prvi metodi, se vozlišči združita v eno vozlišče. S tem lahko pokvarimo parent vozlišče, zato se rekurzivno dvignemo in postopek ponovimo tam. Če pride v ilegalno stanje tudi najvišje (root) vozlišče, spojimo njegova children vozlišča, tako nastalo vozlišče postane novi root, starega pa odstranimo.

Povezave

• Lušten animiran applet
• Wikipedia
• Applet z možnostjo brisanja elementov