On Friday, August 18, 2017 at 10:51:33 AM UTC+2, bartekltg wrote:
> On Thursday, August 17, 2017 at 11:04:34 PM UTC+2, M.M. wrote:
> > No więc dopracowałem drzewko czerwono czarne. Może jeszcze zostały
> > jakieś błędy, ale chodziło kilkadziesiąt godzin na testach i nie
> > wywaliło się.
>
> Za szybko nie będe mógł poczytać.
Tak, wymaga przemyślenia, w poprzednim wątku od pisania na szybko
zrobiła się sieczka.

> Jak to nie tajne:), wrzuć gdzies całość (włacznie z drzewkiem).
Nic tajnego nie ma, zrobię jakiegoś bloga i wkrótce wrzucę.
Tak ogólnie, to poza sortowaniem, mam wszystko bardzo mocno
wzorowane na Cormenie, tylko zamiast wskaźników mam indeksy.

Sortowania ani w Cormenie, ani w Internecie nie znalazłem,
musiałem zastanowić się sam. Wrzucam kod, zapewne jest
za dużo ifów, zapewne można to jeszcze zoptymalizować.

Generalnie bardzo polecam to rozwiązanie, szczególnie
gdy ktoś ma bardzo dużo wyszukiwania, przeglądania
od przodu do tyłu, lub od tylu do przodu, gdy
jest dużo operacji upperBound lub lowerBound.


void sort() {
for(TNODE node=min(), pos=RBT_NULL+1 ; !isNull(node) ; node=next(node), pos++
) {
if( node == pos )
continue;

std::swap( nodes[node] , nodes[pos] );

if( nodes[node].parent == nodes[pos].parent ) {
std::swap( nodes[nodes[node].parent].left ,
nodes[nodes[node].parent].right );
if( nodes[node].left != RBT_NULL ) nodes[nodes[node].left ].parent =
node;
if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent =
node;
if( nodes[pos ].left != RBT_NULL ) nodes[nodes[pos ].left ].parent =
pos ;
if( nodes[pos ].right != RBT_NULL ) nodes[nodes[pos ].right].parent =
pos ;
} else if( nodes[node].parent == node ) {
if( nodes[pos].left == pos ) {
std::swap( nodes[pos].left , nodes[node].parent );
if( nodes[pos ].right != RBT_NULL ) nodes[nodes[pos
].right].parent = pos ;
} else {
std::swap( nodes[pos].right , nodes[node].parent );
if( nodes[pos].left != RBT_NULL ) nodes[nodes[pos].left].parent =
pos ;
}
if( nodes[node].left != RBT_NULL ) nodes[nodes[node].left ].parent =
node;
if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent =
node;
if( nodes[pos].parent != RBT_NULL ) {
if( nodes[ nodes[pos].parent ].left == node ) {
nodes[ nodes[pos].parent ].left = pos;
} else {
nodes[ nodes[pos].parent ].right = pos;
}
}
} else if( nodes[pos].parent == pos ) {
if( nodes[node].left == node ) {
std::swap( nodes[node].left , nodes[pos].parent );
if( nodes[node].right != RBT_NULL )
nodes[nodes[node].right].parent = node ;
} else {
std::swap( nodes[node].right , nodes[pos].parent );
if( nodes[node].left != RBT_NULL ) nodes[nodes[node].left].parent
= node ;
}
if( nodes[pos].left != RBT_NULL ) nodes[nodes[pos].left ].parent =
pos;
if( nodes[pos].right != RBT_NULL ) nodes[nodes[pos].right].parent =
pos;
if( nodes[node].parent != RBT_NULL ) {
if( nodes[ nodes[node].parent ].left == pos ) {
nodes[ nodes[node].parent ].left = node;
} else {
nodes[ nodes[node].parent ].right = node;
}
}
} else {
if( nodes[node].left != RBT_NULL ) nodes[nodes[node].left ].parent =
node;
if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent =
node;
if( nodes[pos ].left != RBT_NULL ) nodes[nodes[pos ].left ].parent =
pos ;
if( nodes[pos ].right != RBT_NULL ) nodes[nodes[pos ].right].parent =
pos ;
if( nodes[node].parent != RBT_NULL ) {
if( nodes[ nodes[node].parent ].left == pos ) {
nodes[ nodes[node].parent ].left = node;
} else {
nodes[ nodes[node].parent ].right = node;
}
}
if( nodes[pos].parent != RBT_NULL ) {
if( nodes[ nodes[pos].parent ].left == node ) {
nodes[ nodes[pos].parent ].left = pos;
} else {
nodes[ nodes[pos].parent ].right = pos;
}
}

}

if( root == node )
root = pos;
else if( root == pos )
root = node;

node = pos;
}
}

Pozdrawiam