Binární vyhledávací strom

  • BVS je binární strom, v jehož každém vrcholu je uložen klíč a pro jehož každý vrchol platí:
    • Pokud , pak
    • Pokud , pak

BVSSHow(v)

  • Výpis vzestupně uspořádaných klíčů nějakého BVS
  • InOrder průchod
  • Složitost:

BVSMin(v)

  • Nalezení vrcholu s nejmenším klíčem
  • V poli vrcholů vygenerovaných pomocí InOrder průchodu je to ten nejvíce vlevo
  • Složitost: hloubka stromu/počet hladin
  • Složitost

BVSPred(v, w)

  • Klíč předchůdce prvku v (v InOrder je to levý soused )
  • Pokud má v levý podstrom , pak je předchůdce jeho maximem
  • Jinak je předchůdcem první předek, do kterého vstoupíme zprava při průchodu nahoru

BVSSucc(v, w)

  • Analogicky s BVSPred()

BVSFind(v, x)

  • - pointer na kořen
  • - co hledáme
  • Rekurzivní zanoření vlevo nebo vpravo a znovu BVSFInd()
  • Složitost

BVSInsert(v, x)

  • Něco jako BVSFind(), ale pokud prvek nenajdeme, vložíme ho na danou pozici
  • Složitost

BVSDelete(v, x)

  • Nejdříve BVSFind()
  • List triviální
  • Vrchol s jedním listem - vyměnit za list
  • Vrchol s více potomky - vyměnit za maximu z levého stromu nebo minimum z pravého stromu
  • Složitost

BVSBuild() na dokonale vyvážený

  • if n == 1
    • return x_1
  • v =
  • L(v) = BVSBuild(x_1 ... x n/2 -1)
  • R(v) = BVSBuild(x n/2 +1 ... x_n)

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25