struct prvek {
		int key;
		string value;
		prvek * left;
		prvek * right;
	};

prvek * search (prvek * b, int k)
{
	while (b != nullptr && b->key != k){
	   if (k < b->key)
		  b = b->left;
	   else 
		  b = b->right;
	}
	return b;
}

void insert (prvek * & b, int k, string v)
{
	if (b == nullptr){
	    prvek * p = new prvek;
		p->key = k;
		p->value = v;
		p->left = NULL;
		p->right = NULL;
		b = p;
	}
	else if (b->key == k)
		b->value = v;
	else if (k < b->key)
		insert (b->left, k, v);
	else 
		insert (b->right, k, v);
}

prvek * odpoj (prvek * & p)
{
	if (p->right != nullptr) 
	  return odpoj (p->right);
	else {
		prvek* a = p;
		p = p->left;
		a->left = nullptr;
		return a;
	}
}

void smaz (prvek * & b,int k)
{
	if (b == nullptr)
	{ }
	else if (k < b->key)
		 smaz (b->left, k);
	else if (k > b->key)
		 smaz (b->right, k);
	else
	{
		prvek *a = b;
		if (b->left == nullptr)
			b = b->right;
		else if (b->right == nullptr)
			b = b->left;
		else
		{
			prvek * r = odpoj(b->left);
			b = r;
			r->left = a->left;
			r->right = a->right;
		}
		delete a;	
	}
}





void remove (prvek * * b, int k)
{
   bool stop = false;
   while (! stop) // cyklus hledajici mazany prvek
   {
		if (*b == nullptr)
		    stop = true; // klic neni ve stromu, neni co mazat
		else if (k < (*b)->key) // hledany klic je  mensi nez klic ve stromu
			b = & ((*b)->left);  // prehod "ukotveni" na levy podstrom
		else if (k > (*b)->key)
			b = & ((*b)->right); // prehod "ukotveni" na pravy podstrom
		else
		{   
			stop = true; // klic byl nalezen, "while" cyklus konci
			prvek * a = * b; // poznamenej si obycejny ukazatel na mazany prvek
			if (a->left == nullptr) // nema levy podstrom
				*b = a->right; // do "ukotveni" pripoj pravy podstrom
			else if (a->right == nullptr)  // nema pravy podstrom
				*b = a->left; // do "ukotveni" pripoj levy podstrom
			else
			{
				// dva podstromy, budeme hledat nejvetsi prvek z mensich prvku, 
				// tj. nahradni prvek za vymazavany prvek
				prvek * * u = & (a->left); 
				// u = "ukotveni" vetsiho z mensich 
				// prozatim ukotveni leveho podstromu mazaneho prvku
				while ((*u)->right != nullptr) // pokud prvek ma pravy podstrom
					u = & ((*u)->right); // posun u na pravy podstrom
			
				// nyni je u "ukotveni" hledaneho nahradniho prvku
				prvek * r = *u;  // poznamenej si obycejny ukazatel na nahradni prvek
				*u = r->left; // do ukotveni nahradniho prvku dej jeho levy podstrom 
				              // (pravy podstrom neni)
				r->left = nullptr; // r nyni ukazuje na uvolneny nahradni prvek

				*b = r; // do ukotveni vymazavaneho prvku vloz ukazatel na nahradni prvek
				r->left = a->left; // nahradnimu prvku pripoj levy podstrom z puvodniho mazaneho prvku
				r->right = a->right; // totez pro pravy podstrom
			}
			delete a; // nyni muzeme prvek opravdu vymazat, a potom ukazatel "a" jiz nesmime pouzivat
		}
   }
}