Vícecestné stromy

vícecestné stromy, 2-3-4 stromy, 2-3 stromy, B stromy, B+ stromy, popis, použití

Tato otázka navazuje na otázku binární vyhledávací stromy.

  • vícecestné stromy se liší tím, že každý uzel může mít více než dva potomky
  • jedná se o samovyvažující se stromy, stejně jako v případě AVL stromů
  • řeší problém ukládání velkého množství dat -> čím hlubší strom, tím delší doba k provedení operace
    • vícecestné stromy mohou mít více potomků pro jeden uzel
    • každý uzel může v sobě mít uložených více hodnot

B stromy

Těmto stromům se budeme věnovat nejpodrobněji, neboť jsou generalizací (obecným případem vícecestného stromu), ze kterého vycházejí i všechny ostatní.

Jedná se o vícecestné stromy, kde každý uzel může mít n potomků a v každém uzlu může být uloženo n-1 hodnot nebo klíčů.

  • pokud má uzel 4 potomky, tak tento uzel v sobě může mít uložené 3 hodnoty
  • každý uzel může mít jinou, řekněme velikost (počet v něm uložených hodnot)
  • stále platí, že menší hodnoty jdou doprava a větší doleva, proto n-1
  • podívejte se na obrázek pod a pokuste se s touto logikou přidat čtvrtého potomka, nepůjde to
Příklad B stromu
obr. 1: Příklad B stromu, uzel má 3 hodnoty a tím pádem 4 potomky
převzato z: https://www.youtube.com/watch?v=SI6E4Ma2ddg

Abychom mohli strom označit za B strom, tak musí splňovat 3 podmínky:

  • každý uzel, musí mít minimálně m/2 potomků, kde m je hloubka stromu (toto neplatí pro listy)
    • pravidlo nám zaručuje, že všechny vnitřní uzly jsou vždy alespoň poloplné
    • můžeme tedy dva uzly spojit v jeden celý uzel, nebo celý uzel rozdělit na dva poloplné
      • hodí se při operacích mazání a vkládání
  • každý uzel může mít n potomků a v každém uzlu může být uloženo n-1 hodnot nebo klíčů (viz výše)
  • všechny listy musí být na stejném patře

Shrnutí:

  • každý B strom má svoji výšku (počet pater, značíme m, jedná se výšku celého stromu)
  • každý uzel obsahuje n hodnot
  • uzel musí mít minimálně m/2 potomků a maximálně n-1 potomků (s vyjimkou listů)
  • všechny listy se musejí nacházet na stejné úrovni
Příklad B stromu
obr. 2: Příklad B stromu, vnitřní uzly splňují požadavek na počet potomků
převzato z: https://www.youtube.com/watch?v=SI6E4Ma2ddg

Operace nad B stromem (vkládání, mazání)

Vícecestné stromy umožňují stejné operace, jako binární vyhledávací stromy. Liší se procesem vyvažování.

Operace vkládání

  1. vložíme prvek na jeho místo
  2. zkontrolujme, zdali jsme nepřekročili limit uzlu (o limitu uzlu se dozvíme na konci kapitoly)
  3. pokud ano, rozdělíme rovnoměrně uzel, kam jsme prvek přidali na 2 (na dva různé uzly)
  4. vezmeme jeden z původních prvků nového uzlu a přidáme ho do rodičovského uzlu
  5. zkontrolujeme rodičovský uzel zdali jsme nepřekročili limit uzlu
  6. pokud ano, opakujeme postup

Operace mazání

  1. nalezneme prvek a smažeme ho
  2. pokud dostaneme nevyvážený strom, řešením jsou rotace stejné jako binárních vyhledávacích stromů s tím rozdílem, že se podíváme na sousední listy a vybereme ten, který má dostatečné množství prvků (smazání prvku neporuší vlastnosti)
    • provedeme rotaci -> kořen posuneme na místo smazaného prvku a nyní prázdný kořen nahradíme nejvyšším prvkem tohoto listu, pokud se jedná o levého souseda (pravá rotace)
    • pokud se jedná o pravého souseda, kořen posuneme na místo smazaného prvku a nyní prázdný kořen nahradíme nejnižším prvkem souseda (levá rotace)
  3. pokud je porušena podmínka minimálního počtu potomků tak vezmeme nejvyšší hodnotu z rodiče, nahradíme touto hodnotou smazanou hodnotu a spojíme levé listy tohoto rodiče do jednoho
  4. pokud mažeme rodiče, tak nahradíme mazanou hodnotu nejvyšší hodnotu levého potomka, nebo nejnižší hodnotou pravého potomka (volba je na nás)
    • nyní je dosti velká šance, že dostaneme nevyvážený strom -> rotujeme jako v 1. bodě

Shrnutí:

Proces mazání se liší podle toho, z jakého uzlu prvek mažeme:

  • list
  • rodič

Po smazání kontrolujeme zdali strom splňuje vlastnosti B stromu a na základě toho volíme vhodný postup, tak aby tyto vlastnosti byly zachovány.

  • rotace neprovádíme s celými uzly, ale s prvky uzlů

Vyhledávání ve stromu

Stejný jako v případě binární vyhledávací stromů.

Průchod stromem

Provádí se průchod do šířky nebo také in-order.

  1. začínáme na levé straně u potomka kořene (jdeme prvek po prvku)
  2. pokud narazíme na potomka, uzlu, prohledáme ho
  3. pokud dorazíme na konec uzlu, vracíme se do rodiče
  4. prohledávání končí, jakmile jsme prohledali poslední prvek nejvíce pravého uzlu

Krásné, 12 minutové video ohledné B stromů lze nalézt zde.

Co je to limit prvků uzlu?

Jak již bylo řečeno, B stromy jsou generickým případem. Co se týče limitů tak víme že:

  • uzel může mít tolik potomků, kolik je počet jeho prvků - 1
  • uzel může mít minimálně tolik prvků, kolik je hloubka stromu/2
  • jaký je ale maximální počet (limit) prvků uzlu?

2-3 a 2-3-4 stromy

Jedná se o b stromy, kde mohou mít uzly:

  • minimálně 2 a a maximálně 3 prvky v případě 2-3 stromu
  • minimálně 2 a maximálně 4 prvky v případě 2-3-4 stromu
  • strom s minimálně 2 prvky a maximálně 5 prvky by byl 2-3-4-5 strom

B+ stromy

B+ stromy jsou variací B stromů ve které jsou všechny hodnoty (tedy i hodnoty ne-listových uzlů) uložené v listech.

Příklad B+ stromu
obr. 3: Příklad B+ stromu, listy obsahují všechny hodnoty
převzato z: https://www.youtube.com/watch?v=49P_GDeMDRo&list=PLsEFMZUL5KsOqKHhxquVleVkM9LFLFSo0
  • sousedi stejného rodiče se nazývají sourozenci
  • sousedi jiného rodiče (stejná úroveň, ale jiný rodič) se nazývají bratranci
  • maximální počet potomků uzlů je stejný jako v případě B stromů (o jednoho více než je počet prvků v uzlu)
  • minimální počet je také stejný jako v případě B stromů (maximální počet/2) -> vztahuje se i na listy
  • hodnoty v listech jsou seřazené podle pořadí od nejnižší po nejvyšší

Operace

Vkládání

  1. prvek přidáváme do listu na jeho místo
  2. pokud je list plný, tak se pokusíme přesunout nejvyšší prvek do sourozence vlevo, pokud to nejde tak nejnižší prvek do sourozence vlevo -> prostě do jiného sourozence
  3. pokud žádné sourozence nemáme, tak rozdělíme list na dvě části a vytvoříme nový list, který obsahuje polovinu vyšších hodnot (list tedy půjde vpravo)
    • pokud máme lichý počet prvků, vezmeme n+1 prvků z původního listu
  4. hodnota v rodiči vždy udává minimum daného listu - aktualizujeme tedy hodnotu v rodiči
  5. pokud dostáváme větší počet listů, než je povoleno (narušíme vlastnosti B stromů), tak se podíváme na levého sourozence tohoto uzlu a pokud má místo, předáme mu nejvíce levý (nejnižší list)
    • je také možné podívat se na pravého sourozence a předat mu nejvíce pravý (nejvyšší list)
    • pokud místo nemá, provedeme předchozí kroky a rodičovský uzel rozdělíme na dva, přičemž každý má pod sebou patřičné listy

Mazání

  1. zkontrolujeme, zdali má uzel minimální počet hodnot, pokud ano, je vše v pořádku
  2. pokusíme se vzít si maximální hodnotu od levého sourozence
  3. pokud to nejde (máme plno nebo ho nemáme), spojíme uzel s levým sourozencem -> přesuneme do něj všechny hodnoty
  4. pokud ho nemá, nebo je sourozenec plný, pokusíme se vzít si minimální hodnotu od pravého sourozence
    • toto se stane pouze u uzlů, které nemají levého sourozence
  5. pokud to nejde, spojíme uzel s pravým sourozencem

Příklad ohledně mazání prvků je uveden zde.

Já osobně bych se raději popisu operací vyhnul.

Využití vícecestných stromů

Využití klasických B stromů (2-3,2-3-4...):

  • v oblasti slovníků
  • oblasti externích disků, kde velikost uzlu/listu je stejně velká, jako velikost čteného bloku (indexace bloku)

Využití B+ stromů:

  • při indexování velkého množství dat, které se nevejdou do RAM, například záznamů v tabulkových databázích
    • strom je uložen v RAM (kromě listů)
    • listy stromu, jsou uložené na disku

Zdroje