Cvičení 8

Témata

• červeno-černé stromy (red-black tree)
• opravené písemky

Průběh

• Zopakovali jsme si základní myšlenky červeno-černých stromů.
• Dostali jste opravené písemky.

Úkoly pro cvičení v C

1. Implementujte červeno-černé stromy pro ukládání čísel typu int.
2. Doporučené rozhraní
   • typ RBTree pro červeno-černý strom reprezentovaný kořenem
   • procedury:
     • RBTree* rb_create() vytvoří nový prázdný červeno-černý strom.
     • int rb_add(RBTree *tree, int data) přidává prvek do stromu. Vrací 1 pokud byl prvek přidán a 0 jinak. Nepovolujte duplicitní hodnoty.
     • int rb_search(RBTree *tree, int data) vyhledává prvek ve stromě. Vrací 1 pokud byl prvek nalezen a 0 jinak.
     • int rb_delete(RBTree *tree, int data) maže prvek ze stromu. Vrací 1 pokud byl prvek smazán a 0 jinak.
     • int rb_height(RBTree *tree) vrací výšku stromu.
     • void rb_in_order_print(RBTree *tree) vypisuje strom in order průchodem.

Poznámka: velkou část práce již máte hotovou v základních binárních vyhledávacích stromech a AVL stromech.

Úkoly pro cvičení v Pythonu

1. Implementujte struktury pro červeno-černé stromy pro ukládání čísel.
2. Implementujte pro ně:
   • vytváření nového prázdného stromu,
   • přidávání do stromu,
   • vyhledávání ve stromu,
   • výpočet výšky stromu,
   • in-order průchod stromem,
   • mazání ze stromu.

Poznámka: velkou část práce již máte hotovou v základních binárních vyhledávacích stromech a AVL stromech.