Cvičení 7

Témata

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

Průběh

• zopakovali jsme si základní myšlenky červeno-černých stromů
• psala se první zápočtová písemka

Úkoly

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.