/* ------------------------------ c401.c ------------------------------------ */
/* Téma: Rekurzivní implementace operací nad BVS (Dynamické pridel.pam.)
**                           Vytvořil: Petr Přikryl, listopad 1994
**                           Úpravy:   Andrea Němcová, prosinec 1995
**                                     Petr Přikryl, duben 1996
**                                     Petr Přikryl, listopad 1997
**           Přepracované do jazyku c: Martin Tuček, rijen 2005
**
** Implementujte rekurzivním způsobem operace nad binárním vyhledávacím
** stromem (BVS; v angličtině BST -- Binary Search Tree).
**
** Klíčem uzlu stromu je jeden znak (obecně jím může být cokoliv, podle
** čeho se vyhledává). Užitečným (vyhledávaným) obsahem je zde integer.
** Uzly s menším klíčem leží vlevo, uzly s větším klíčem leží ve stromu
** vpravo. Využijte dynamického přidělování paměti.
** Rekurzivním způsobem řešte následující procedury a funkce:
**
**   BSTInit ...... inicializace vyhledávacího stromu
**   BSTSearch .... vyhledávání hodnoty uzlu zadaného klíčem
**   BSTInsert .... vkládání nové hodnoty
**   BSTDelete .... rušení uzlu se zadaným klíčem
**   BSTDispose ... rušení celého stromu
**
** Přesnou definici typů naleznete v souboru c401.h; pro přehled --
** ADT BVS je reprezentováno kořenovým ukazatelem stromu typu tBSTNodePtr.
** Uzel stromu (struktura typu tBSTNode) obsahuje ukazatele LPtr a RPtr na levý
** a pravý podstrom, složku char KEY -- klíč, podle kterého se vyhledává,
** a int BSTNodeCont -- obsah uzlu (demonstrativne integer).
**
** !Upozorneni! Je treba, abyste spravne rozlisovali, kdy pouzit dereferencni 
** operator * na samotny ukazatel (tj. kdyz budeme chtit zapsat urcitou hodnotu 
** do tohoto pointeru, typicky modifikacni operace) a kdy budeme pracovat pouze 
** se samotnym ukazatelem (vyhledavaci fce). V techto ulohach poznate tuto
** skutecnost predevsim pomoci prototypu techto fci. V situaci, kdy pracujeme 
** s ukazatelem na ukazatel, je treba pouzit dereferenci.
**
** Poznámka: nepoužívejte nestandardní příkazy (exit(),...) a operace.
*/

#include "c401.h"
int solved;
int errflg;

void BSTInit (tBSTNodePtr *RootPtr) {
/* Počáteční inicializace stromu před prvním použitím datové struktury.
** Počáteční testování ukazatele není možné, protože obsahuje nedefinovanou
** (tj. libovolnou) hodnotu, která ovšem neodráží reálný stav.
** 
** Všimněte si, ze zde se poprvé v hlavičce objevuje typ ukazatel na ukazatel,
** proto je treba pri práci s RootPtr(přiřazení) použít dereferenční operátor.
** Ten bude ještě třeba použít v procedurách BSTDelete, BSTInsert a BSTDispose.
**/

	*RootPtr = NULL; //prazdny strom

}


int BSTSearch (tBSTNodePtr RootPtr, char K, int *Content) {
/* Vyhledávání uzlu v BVS podle zadaného klíče K. Pokud je nalezen, vrací
** funkce hodnotu TRUE a v proměnné Content se vrací obsah příslušného uzlu.
** Pokud příslušný uzel není nalezen, vrací funkce hodnotu FALSE a obsah
** proměnné Content není definován (to znamená, že do ní nebudete nic
** přiřazovat). Při vyhledávání v binárním stromu bychom typicky použili
** cyklus ukončený testem zahrnujícím stav dosažení listu nebo nalezení
** uzlu s klíčem. V tomto případě ovšem test nepoužijte a problém řešte
** rekurzivním volání této funkce (nedeklarujte žádnou pomocnou proceduru
** nebo funkci).
**/

	if (RootPtr == NULL) { //kdy je prazdny strom
		return FALSE; //neni co hledat
	} else if (RootPtr -> Key != K) { //jinak kdyz klic neni hledanym
		if (RootPtr -> Key > K) { //kdyz je aktualni klic vetsi nez hledany
			return BSTSearch(RootPtr -> LPtr, K, Content); //zanor se doleva
		} else {
			return BSTSearch(RootPtr -> RPtr, K, Content); //a kdyz mensi tak doprava
		}
	} else {
		*Content = RootPtr -> BSTNodeCont; //nasel jsem a precetl obsah
		return TRUE; //a nasel jsem
	}

}


void BSTInsert (tBSTNodePtr* RootPtr, char K, int Content) {
/* Vloží do stromu hodnotu Content s klíčem K. Pokud již uzel
** se zadaným klíčem existuje, nahradí se obsah uzlu novou hodnotou.
** Nově vytvořený uzel nechť je vždy listem stromu. Řešte rekurzivně.
**
** Tato rekurzivní implementace je poněkud neefektivní, protože se při
** každém rekurzivním zanoření musí kopírovat celý integer "Content" (obecně
** obsah uzlu). V praxi by se tento problém řešil například jedním
** z těcho způsobů:
**  - předáváním proměnné "Content" odkazem (v tom případě je nutné dosazovat
**    při volání proměnnou a není možné přímo zapsat hodnotu);
**  - deklarací vnitřní procedury, které by se parametr předal odkazem;
**    vnější procedura by sloužila jen jako obal (nevolala by se
**    rekurzivně);
**  - při využití předchozí varianty by se do rekurzivní procedury předával
**    předem naplněný nový uzel, který by se na závěr zrušil v případě,
**    že se uzel nepodařilo zařadit (pokud už uzel s tímto klíčem existoval,
**    přepsal by se jen obsah, případně by se uzly vyměnily a ke zrušení
**    by se předal starý uzel);
**
** Nerekurzivní varianta by v tomto případě byla efektivnější jak z hlediska
** rychlosti, tak z hlediska paměťových nároků. Zde však jde o školní
** příklad. Nedeklarujte žádnou pomocnou proceduru nebo funkci, problém
** řešte rekurzivním voláním procedury samé.
**
** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím
** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na 
** ukazatel). Správné zavolání např. na levý podstrom:
** BSTInsert(&((*RootPtr)->LPtr), K, Content)
*/

	if (*RootPtr == NULL) { //kdyz vkladam do prazdnyho stromu
		tBSTNodePtr uzel; //novy uzel
		if ((uzel = malloc(sizeof(struct tBSTNode))) == NULL) { //zkusime ho alokovat
			return; //nebo umrem
		}
		uzel -> Key = K; //vloz kliv
		uzel -> BSTNodeCont = Content; //vloz obsah
		uzel -> LPtr = NULL; //prazdny strom nema listy
		uzel -> RPtr = NULL;
		*RootPtr = uzel; // a konecne ho vloz
	} else if (K < (*RootPtr) -> Key) { //nebo kdyz klic je mensi
			BSTInsert(&((*RootPtr) -> LPtr), K, Content); //chci vkladat doleva
	} else if (K > (*RootPtr) -> Key) { //kdyz vetsi
		BSTInsert(&((*RootPtr) -> RPtr), K, Content); //vlozit doprava
	} else {
		(*RootPtr) -> BSTNodeCont = Content; //kdyz uz se nemam kam norit, nalezl jsem a vloz obsah
	}

}


/* POZOR NASLEDUJÍCÍ PROCEDURA BUDE POUŽITA DÁLE, 
** PREČTĚTE SI PROTO PODROBNĚ NEJPRVE KOMENTÁŘ K PROCEDUŘE BSTDELETE(),
** NEŽ ZAČNETE VYTVÁŘET REPLACEBYRIGHTMOST().
*/
void ReplaceByRightmost (tBSTNodePtr PtrReplaced,tBSTNodePtr *RootPtr) {
/* Pomocná procedura pro vyhledání, přestěhování a uvolnění nejpravějšího
** uzlu v podstromu určeném ukazatelem RootPtr. Na vstupu se předpokládá
** hodnota ukazatele RootPtr různá od NULL (zajistěte to testováním před
** volání procedury). Dále se předpokládá, že pomocný ukazatel PtrReplaced
** ukazuje na uzel, který se má naplnit hodnotami vyhledaného uzlu.
*/
  tBSTNodePtr ptr; /* používejte tento pomocný ukazatel */
  ptr = NULL;

	if ((*RootPtr) -> RPtr != NULL) { //kdyz vravo neco je
		ReplaceByRightmost(PtrReplaced, &((*RootPtr) -> RPtr)); //bez doprava
	} else { //no a kdyz tam nic neni
		PtrReplaced -> BSTNodeCont = (*RootPtr) -> BSTNodeCont; //nahrad obsah
		PtrReplaced -> Key = (*RootPtr) -> Key; //nahrad klic
		ptr = *RootPtr; //zalohuj koren
		*RootPtr = (*RootPtr) -> LPtr; //novy koren
		free(ptr); //uvolni stary koren
	}

}


void BSTDelete (tBSTNodePtr *RootPtr, char K) {
/* Zruší uzel stromu, který obsahuje klíč K. Pokud uzel se zadaným klíčem
** neexistuje, nedělá nic. Veškeré manipulace řešte rekurzivně.
**
** Pokud má rušený uzel jen jeden podstrom, pak jej zdědí otec. Pokud má
** oba podstromy, pak je rušený uzel nahrazen nejpravějším uzlem levého
** podstromu. Pozor! Nejpravější uzel nemusí být listem. Pro tuto operaci
** jsme deklarovali proceduru ReplaceByRightmost -- viz. její komentář
** uveden výše.
** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím
** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na 
** ukazatel). Správné zavolání např. na levý podstrom:
** BSTDelete(&((*RootPtr)->LPtr), K).
** Podobně je tomu tak i u ReplaceByRightMost().  
** Například: ReplaceByRightmost(*RootPtr, (&((*RootPtr)->LPtr)))
*/
  tBSTNodePtr ptr;  /* používejte tento pomocný ukazatel */
  ptr=NULL;

	if (*RootPtr != NULL) { //kdyz je co mazat
		if (K < (*RootPtr) -> Key) { //kdyz je klic mensi
			BSTDelete(&((*RootPtr) -> LPtr), K); //bez doleva
		} else {
			if (K > (*RootPtr) -> Key) { //kdyz je klic vetsi
				BSTDelete(&((*RootPtr) -> RPtr), K); //bez doprava
			} else {
				ptr = *RootPtr; //zalohuj koren
				if (ptr -> RPtr == NULL) { //kdyz koren vpravo nic nema
					(*RootPtr) = ptr -> LPtr; //koren bude levej
					free(ptr); //uvolni starej koren
				} else {
					if (ptr -> LPtr == NULL) { //kdyz koren vlevo nic nema
						(*RootPtr) = ptr -> RPtr; //koren bude prvej
						free(ptr); //uvolni starej koren
					} else {
						ReplaceByRightmost(*RootPtr, (&((*RootPtr) -> LPtr))); //jinak kouzli
					}
				}
			}
		}
	}
  
} 


void BSTDispose (tBSTNodePtr *RootPtr) {
/* Korektně zruší celý binární vyhledávací strom. Zvolte nejvýhodnější
** druh rekurzívního průchodu stromem. Nedeklarujte žádné pomocné procedury
** nebo funkce.
** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím
** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na 
** ukazatel). Správné zavolání např. na levý podstrom:
** BSTDispose(&(*RootPtr)->LPtr).
*/

	if (*RootPtr != NULL) { //kdyz je co sidposovat
		BSTDispose(&(*RootPtr) -> RPtr); //disposuj doprava
		BSTDispose(&(*RootPtr) -> LPtr); //dsposuj doleva
		free(*RootPtr); //uvolni
		*RootPtr = NULL; //a oznac za prazdny
	}

//solved = FALSE;
}

/* --------------------------- konec c401.c -------------------------------- */