Cvičení 6

Téma - AVL stromy

• přidávání
• vyvažování (bf - balance factor a výška; rotace)
• mazání
• AVL stromy jsou první částí zápočtového úkolu (více informací zde)

Písemka

• Příště nás čeká první písemka
• Více informací zde

Zápočtový úkol

• Dnešní úkoly jsou první částí zápočtového úkolu.

Úkoly pro cvičení v C

1. Implementujte AVL strom pro ukládání čísel typu int.
2. Závazné rozhraní (proti němu budu kód testovat):
   • typ AVLTree pro AVL strom reprezentovaný kořenem
   • procedury:
     • AVLTree* avl_create() vytvoří nový prázdný AVL strom.
     • int avl_add(AVLTree *tree, int data) přidává prvek do stromu. Vrací 1 pokud byl prvek přidán a 0 jinak. Nepovolujte duplicitní hodnoty.
     • int avl_search(AVLTree *tree, int data) vyhledává prvek ve stromě. Vrací 1 pokud byl prvek nalezen a 0 jinak.
     • int avl_delete(AVLTree *tree, int data) maže prvek ze stromu. Vrací 1 pokud byl prvek smazán a 0 jinak.
     • int avl_height(AVLTree *tree) vrací výšku stromu.
     • void avl_in_order_print(AVLTree *tree) vypisuje strom in order průchodem.

Doporučený postup:

1. Implementujte vhodné struktury pro AVL strom (můžete vhodně modifikovat struktury, které máte z BST).
2. Implementujte pomocné procedury pro udržování výšky AVL stromu - rotace.
3. Implementujte vyhledávání prvku v AVL stormu a přidávání prvku do AVL stromu (s využitím rotací z předchozího bodu).
4. Implementujte počítání výšky stromu a in order výpis stromu (stejné jako u BST).
5. Implementujte odebírání prvků z AVL stromu (s využitím kódu z předchozích bodů).

Poznámky:

1. Dávejte pozor na složitost implementovaných procedur. Zejména u manipulací se stromem (přidávání, mazání, hledání).
2. Taková implementace se dá snadno použít pro efektivní reprezentaci (operace v O(log(n))) množiny čisel typu int. Jak?

Úkoly pro cvičení v Pythonu

1. Implementujte AVL strom pro ukládání čísel.
2. Závazné rozhraní (proti němu budu kód testovat):
   • typ AVLTree pro AVL strom reprezentovaný kořenem
   • procedury:
     • avl_create() vytvoří nový prázdný AVL strom a vrátí jej uživateli.
     • avl_add(tree, data) přidává prvek do stromu. Vrací true pokud byl prvek přidán a false jinak. Nepovolujte duplicitní hodnoty.
     • avl_search(tree, data) vyhledává prvek ve stromě. Vrací true pokud byl prvek nalezen a false jinak.
     • avl_height(tree) vrací výšku stromu.
     • avl_in_order_print(tree) vypisuje strom in order průchodem.

Doporučený postup:

1. Implementujte vhodné struktury pro AVL strom (můžete vhodně modifikovat struktury, které máte z BST).
2. Implementujte pomocné procedury pro udržování výšky AVL stromu - rotace.
3. Implementujte vyhledávání prvku v AVL stormu a přidávání prvku do AVL stromu (s využitím rotací z předchozího bodu).
4. Implementujte počítání výšky stromu a in order výpis stromu (stejné jako u BST).

Poznámky:

1. Dávejte pozor na složitost implementovaných procedur. Zejména u manipulací se stromem (přidávání, mazání, hledání).
2. Taková implementace se dá snadno použít pro efektivní reprezentaci (operace v O(log(n))) množiny čisel typu int. Jak?