AVL Stromy

  • Skoro jako BVS, ale né úplně dokonale vyvážený (je hloubkově vyvážený)
  • BVS je AVL stromem, pokud pro každý jeho vrchol platí:
  • AVL strom s vrcholy má složitost
  • Hloubka stromu vrcholy má hloubku

AVLInsert()

  • U každého vrcholu ukládám informaci o hloubkách jeho podstromů (tzv. znaménko)
  • Jakmile narazíme na jiné znaménko, provádíme rotace
  • Vložíme jako list se znaménkem 0
  • Přepočítat hloubky na cestě z rodiče do kořene, případně řešit rotací
  • Propagovat nahoru

AVLDelete()

  • Podobně jako AVLInsert()
  • Místo informace o prohloubení propagujeme info o změlčení

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