Naskrobałem taką funkcję w realizacji drzewa splay i działa, ale (o ile się da) chciałbym ją uprościć i zredukować chociaż trochę ilość kodu, jednak jakoś brak mi pomysłów, szczególnie że zmuszenie tego fragmentu do działania nie zajęło mi mało czasu.
void splay(wezel * promowany)
{
wezel * korzen = drzewo.korzen;
if ( promowany == korzen)
{
cout << "Ten wezel juz jest korzeniem" << endl;
return;
}
wezel *pradziadek, *dziadek, *rodzic, *pozycja;
while (promowany != korzen)
{
pradziadek = NULL;
dziadek = NULL;
rodzic = NULL;
pozycja = korzen;
while (pozycja != NULL && pozycja->klucz != promowany->klucz) //szukamy elementu do wypromowania, i tutaj go tez znajdujemy
//potem sprawdzam czy istnieje ->NULLem
{
pradziadek = dziadek;
dziadek = rodzic;
rodzic = pozycja;
if(pozycja->klucz > promowany->klucz)
{
pozycja = pozycja->lewy;
}
else
{
pozycja = pozycja->prawy;
}
}
if (pozycja == NULL)
{
cout << "Promowany wezel nie jest czescia tego drzewa " << promowany->klucz << endl;
return;
}
if (dziadek != NULL) //spr czy potrzebna bedzie rotacja podwojna czy pojedyncza, jak dziadek null to jestesmy pod korzeniem, pojedyncza rotacja i jestesmy w korzeniu
{
if (pozycja == rodzic->prawy && rodzic == dziadek->prawy) //zigzig prawy prawy
{
if (pradziadek != NULL)
{
if ( dziadek == pradziadek->prawy)
{
pradziadek->prawy = pozycja;
}
else
{
pradziadek->lewy = pozycja;
}
}
else
{
korzen = pozycja;
}
rotuj(rodzic, dziadek);
rotuj(pozycja, rodzic);
}
else if (pozycja == rodzic->lewy && rodzic == dziadek->lewy) // zigzig lewy lewy
{
if (pradziadek != NULL)
{
if ( dziadek == pradziadek->prawy)
{
pradziadek->prawy = pozycja;
}
else
{
pradziadek->lewy = pozycja;
}
}
else
{
korzen = pozycja;
}
rotuj(rodzic, dziadek);
rotuj(pozycja, rodzic);
}
else if (pozycja == rodzic->lewy && rodzic == dziadek->prawy) // zigzag prawy lewy
{
if ( pradziadek != NULL)
{
if ( dziadek == pradziadek->prawy)
{
pradziadek->prawy = pozycja;
}
else
{
pradziadek->lewy = pozycja;
}
}
else
{
korzen = pozycja;
}
rodzic->lewy = pozycja->prawy;
pozycja->prawy = rodzic;
dziadek->prawy = pozycja->lewy;
pozycja->lewy = dziadek;
}
else if (pozycja == rodzic->prawy && rodzic == dziadek->lewy) // zigzag lewy prawy
{
if ( pradziadek != NULL)
{
if ( dziadek == pradziadek->prawy)
{
pradziadek->prawy = pozycja;
}
else {
pradziadek->lewy = pozycja;
}
} else
{
korzen = pozycja;
}
rodzic->prawy = pozycja->lewy;
pozycja->lewy = rodzic;
dziadek->lewy = pozycja->prawy;
pozycja->prawy = dziadek;
}
}
else
{
rotuj(pozycja, rodzic);
korzen = pozycja;
}
}
}