-
X-Received: by 10.31.136.77 with SMTP id k74mr46213vkd.4.1503047501809; Fri, 18 Aug
2017 02:11:41 -0700 (PDT)
X-Received: by 10.31.136.77 with SMTP id k74mr46213vkd.4.1503047501809; Fri, 18 Aug
2017 02:11:41 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit
0.net!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.
iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!i19no22
6586qte.1!news-out.google.com!i9ni19652qte.0!nntp.google.com!i19no226582qte.1!p
ostnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Fri, 18 Aug 2017 02:11:41 -0700 (PDT)
In-Reply-To: <3...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=77.254.35.4;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 77.254.35.4
References: <6...@g...com>
<3...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <2...@g...com>
Subject: Re: ciąg dalszy drzewa czerwono-czarne
From: "M.M." <m...@g...com>
Injection-Date: Fri, 18 Aug 2017 09:11:41 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 128
Xref: news-archive.icm.edu.pl pl.comp.programming:211182
[ ukryj nagłówki ]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
Następne wpisy z tego wątku
- 21.08.17 13:30 M.M.
Najnowsze wątki z tej grupy
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-04-28 wymiana przewodu od licznika do mieszkania
- 2024-04-28 Lustra w maszynie ASML
- 2024-04-28 Elektryk przytarł podłogę
- 2024-04-27 Nowy, "szybki "komputer AsRock nie posiada modułu TPM
- 2024-04-27 Nowy, "szybki "komputer AsRock nie posiada modułu TPM
- 2024-04-27 Warszawa => Inżynier DevOps (projekt JP) <=
- 2024-04-27 Warszawa => Senior Account Manager (on-site) <=
- 2024-04-27 Wrocław => Dyrektor Sprzedaży (branża usług/produktów IT) <=
- 2024-04-27 Warszawa => Sales Representative for Outsourcing Services <=
- 2024-04-27 Chrzanów => Administrator i wdrożeniowiec Lotus Notes/Domino <=
- 2024-04-27 Ja pierdolę...
- 2024-04-27 Ryby i kawitacja
- 2024-04-27 Zabrze => Junior HelpDesk <=
- 2024-04-27 Katowice => Administrator IT - Wirtualizacja i Konteneryzacja <=
- 2024-04-27 Bażanowice => Inżynier Industrializacji - Elektronik <=