kod źródłowy c++ drzewa czerwono czarne RBTree 0.00v

#pragma once

/////////////////////////////////////////////////////////////////////////////////
//
// RBTree, beta 0.00v
//
/////////////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////////////
// To jest kod open-source, jest jednak rozprowadzany na
// innej licencji niż typowe licencje open-source. Jeśli
// poniższa licencja Tobie nie odopowiada, to skasuj ten
// kod ze swojego komputera.
//
//
//
// Możesz ten kod pobrać z mojej strony internetowej, możesz go czytać
// możesz go używać nieodpłatnie w swoich programach, możesz go zmieniać,
// jednak pod kilkoma warunkami i w określonych poniżej ramach.
// 0) Zanim zaczniesz cokolwiek robić z wykorzystaniem tego kodu,
//    zapoznaj się z opisem. Niektóre (dobre) cechy tego kodu,
//    można łatwo uznać za błędy.
// 1) Możesz ten kod pobrać z mojej strony internetowej, nie możesz
//    rozprowadzać tego kodu ani w oryginalne, ani po zmianach, ani w
//    całości, ani we fragmentach, ani obcym, ani znajomym.
// 2) Jeśli rozprowadzasz wesję skompilowaną tego kodu, nie musisz
//    udostępniać źródła, ani mnie informować, ani nic płacic. Jeśli
//    jednak mnie poinformujesz, to zrobię Ci małą reklamę, napiszę
//    że Twój program korzysta z tego kodu, opublikuję Twój e-mail i
//    link do strony Twojego programu.
// 3) Jeśli będziesz publikował fragmenty kodu który rozumiany jako
//    całość w publikowanych lub w innych fragmetach wykorzystuje mój
//    kod, to musisz także opublikować link do mojej strony.
// 4) Jeśli w trakcie czytania lub używania znajdziesz błąd, musisz
//    natychmiast mnie o tym poinformować wysyłając wiadomość na e-mail
//    mmarszik@gmail.com
// 5) Jeśli w trakice czytania lub używania będziesz miał pomysł na
//    zwiększenie efektywności tego kodu, musisz mnie również
//    poinformować.
// 6) Jeśli z kodu usuniesz błędy lub przyspieszysz działanie, to
//    musisz wysłać mi wersję ulepszonego kodu, jednak bez Twojego
//    kodu specyficznego dla Twojej aplikacji.
// 7) Możesz kod dowolnie modyfikować w innym sensie niż punkt 6 i
//    wtedy nie musisz mnie, ani informować, ani nic mi wysyłać.
// 8) Jeśli dokonałeś drobnych zmian optymalizacyjnych, np. poprzez
//    odkomentowanie wersji RBTNode z polami bitowymi, lub przez
//    zastąpienie typu int, typem short, to proszę bądź tak łaskaw i
//    nie zaśmiecaj mi skrzynki e-mail ;-)
// 9) Jeśli rozszerzysz funkcjonalność tego kodu o operacje powszechnie
//    przydatne, np. o jakąś odmianę wyszukiwania, to nie musisz
//    mnie informować, ani przysyłać nowej wersji kodu, ale będę
//    Ci bardzo wdzięczny gdy to zrobisz. Zwróć uwagę, że ja cały kod
//    udostępniam za darmo nawet od zastosowań komercyjnych.
//10) Jeśli uznam Twoje zmiany w kodzie lub Twoje sugestie za ważne
//    to zamieszczę je na stronie na tej samej licencji lub na
//    jej nowszej wersji. Zamieszczę jednak w komentarzu, że przyczyniłeś
//    się do powstania fragmentów kodu, mogę np. podać Twój e-mail
//    lub adres Twojej strony www.
//11) Używasz tego kodu tylko i wyłącznie na WŁASNE RYZYKO, kod może
//    zawierać błędy, może np. skasować Ci wszystkie dane z wszystkich
//    komputerów w domu i w pracy - jest to jednak bardzo mało
//    prawdopodobne. Kod był testowany, w niektórych wersjach RBTree było
//    testowane kilkadziesiąt godzin i jak narazie żadne błedy nie zostały
//    wykryte.
/////////////////////////////////////////////////////////////////////////////////


#include <QVector>
#include <QVarLengthArray>
#include <QTextStream>
#include <vector>

#define RBT_NULL ((CTNODE)0)


// Asercje wyłączone
#define EXCP( __expr__ )


// Kolroy węzłów
enum RBTColor {
    RBTC_RED,
    RBTC_BLACK,
};

// Zamiast trzech pól: left, right i parent, można dać
// tablicę trójelementową. Dzięki takiej tablicy można
// zmniejszyć rozmiar kodu. Niestety jeszcze nie zaimplementowane.
enum RBTLeaf {
    RBTL_RIGHT,
    RBTL_LEFT,
    RBTL_PARENT,
    RBTL_SIZE
};

// Sposób zachowania drzewa czerwono-czarnego. Przetestowane
// było tylko last, co jest zgodne z zachowaniem std::set i QMap.
enum RBTReplace {
    RBTR_NOT,        // Wstawiaj zwielokrotnione
    RBTR_FIRST,      // Pozostaw pierwszy gdy wstawia się takie same dane
    RBTR_LAST        // Pozostaw ostatni gdy wstawia się takie same dane
};


// Szablon węzła
template<class TD,class TNODE=int>
class RBTNode {
public:
    TD       data;      // dane w węźle
    TNODE    parent;    // rodzic
    TNODE    left;      // mniejszy
    TNODE    right;     // większy
    RBTColor color;     // kolor
};


/*
// W moich testach poniższa optymalizacja nie sprawdziła się.
// Prawdopodobnie procesor za dużo czasu tracił na wyłuskanie
// liczb z pól bitowych.
#pragma pack(push)
#pragma pack(1)
template<class TD,class TNODE=int>
class RBTNode {
public:
    TD       data;      // dane w węźle
    unsigned    parent:21;    // rodzic
    unsigned    left:21;      // mniejszy
    unsigned    right:21;     // większy
    unsigned    color:1;     // kolor
};
#pragma pack(pop)
*/

// Allocator bazujący na QVector
template<class TD,class TDF=TD,typename TNODE=int>
class RBTQVAllocator : public QVector< RBTNode<TD,TNODE> > {
public:
};

// Allocator bazujący na std::QVarLengthArray - raczej przydatne
// tylko do testów.
template<class TD,class TDF=TD,typename TNODE=int>
class RBTQADAllocator : public QVarLengthArray< RBTNode<TD,TNODE> > {
public:
};

// Allocator bazujący na std::vector - okazał się najszybszy w
// testach.
template<class TD,class TDF=TD,typename TNODE=int>
class RBTSVAllocator : public std::vector< RBTNode<TD,TNODE> > {
public:
    void operator += (const RBTNode<TD,TNODE> &node) {
        std::vector<RBTNode<TD,TNODE>>::push_back(node);
    }
    void remove(int i,int n=0) {
        std::vector<RBTNode<TD,TNODE>>::erase( std::vector<RBTNode<TD,TNODE>>::begin()+i , std::vector<RBTNode<TD,TNODE>>::begin()+i+n );
    }
    const RBTNode<TD,TNODE>* constData() const {
        return std::vector<RBTNode<TD,TNODE>>::data();
    }
    const RBTNode<TD,TNODE>& last() const {
        return std::vector<RBTNode<TD,TNODE>>::at( std::vector<RBTNode<TD,TNODE>>::size()-1 );
    }
    void removeLast() {
        std::vector<RBTNode<TD,TNODE>>::pop_back();
    }
    void squeeze() {
        std::vector<RBTNode<TD,TNODE>>::shrink_to_fit();
    }
};

/*
//#define RBT_SWAP( __x__ , __y__ )      \
//    {                                  \
//    const auto __swp__ = __x__;        \
//    __x__ = __y__;                     \
//    __y__ = __swp__;                   \
//    }
*/

// Drzewko działa trochę szybciej, gdy użyje się std::swap, zamiast
// powyższego kodu ze zmienną pomocniczą __swp__. Dlaczego? Nie
// mam pojęcia, może robi wstawkę asemblerową? Jednak std::swap nie
// działa na polach bitowych. Więc jak chcesz użyć wersji z RBTNode z
// polami bitowymi, to musisz odkomentować powyższą wersję
// RBT_SWAP, a tę zakomentować.
#define RBT_SWAP( __x__ , __y__ ) std::swap( __x__ , __y__ )

// Szablon drzewa czerwono-czarnego
// TD -        typ przechowywany w drzewie, dla tego typu muszą być
//             przedefiniowane operatory porównywania.
//
// TDF -       dodatkowy typ, może przydać sie do porównywania. Gdy
//             np. przechowujesz strukturę {x,y}, a porządwek wyznacza
//             tylko x, to niewygodne będzie każdorazowe podawanie
//             całej struktury {x,y} w metodach takich jak search lub
//             upperBound. Zamiast całej struktury, wygodniej jest podawać
//             tylko {x}. Aby to bylo możliwe, zdefiniuj TDF jako typ x.
//             Wiem, że klasyczne rozwiązanie tego problemu polega na
//             przechowywaniu dwóch tablic: jednej z x (jako klucz), drugiej y
//             jako wartość. Może w przyszłości przygotuję taką wersję
//             drzew czerwono-czarnych.
// TNODE -     gdy będziesz miał bardzo dużo małych drzew, to w celu
//
//             zaoszczędzenia pamięcy, zdefiniuj TNODE jako int8 lub int16 -
//             może dzięki temu Twój program przyspieszy, może dzięki temu
//             znieści się w pamięci.
//
// Allocator - możesz eksperymentować z różnymi allocatorami. Domyślnie
//             calość jest oparta na std::vector. Ale nic nie stoi
//             na przeszkodzie, abyś napisał swój Allocator, może dzięki
//             temu Twój program bedzie dzialał szybciej.
//
// LOOKUP -    eksperymentuj z tą wartością, aby nieznacznie przyspieszyć
//             metody search, lowerBound, upperBound. Dla typu unsigned
//             int, na moim komputerze, najszybsza była wartość 70. Dla
//             dużych struktur zapewne mniejsza wartość będzie dawała
//             lepsze wyniki.
template<class TD, typename TDF=TD, typename TNODE=int, typename Allocator=RBTSVAllocator<TD,TDF,TNODE>, int LOOKUP=70, RBTReplace REPLACE=RBTR_FIRST>
class RBTree {
public:
    typedef const TNODE CTNODE;
private:
    Allocator nodes;   // węzły
    TNODE     root;    // numer roota lub RBT_NULL gdy drzewo puste

private:

public:

    bool isEmpty() const { return root == RBT_NULL; }
    void clear() { nodes.remove( 1 , nodes.size()-1 ); root = RBT_NULL; }
    TNODE getRoot() const { return root; }
    TNODE size() const { return nodes.size()-1; }

    void squeeze() { nodes.squeeze(); }

    RBTree( CTNODE reserved = 32 ) {
        nodes.reserve(reserved);
        RBTNode<TD,TNODE> null;
        null.left  = null.right = null.parent = RBT_NULL;
        null.color = RBTC_BLACK;
        nodes += null;
        root = RBT_NULL;
    }

    TNODE rawInsert( const TD &data ) {
        RBTNode<TD,TNODE> node;               // węzeł do wstawienia
        node.data  = data;       // kopiujemy dane
        node.left  = RBT_NULL;   // liście nowego węzła zawsze wskazują na null
        node.right = RBT_NULL;   // ------------------||----------------------
        TNODE parent = RBT_NULL;
        {
            TNODE tmp = root;
            while( tmp != RBT_NULL ) {
                parent = tmp;
                if( data < nodes[tmp].data ) {
                    tmp = nodes[tmp].left;
                } else {
                    if( REPLACE == RBTR_FIRST && ! (nodes[tmp].data < data) ) { // nigdy nie było testowane
                        return -tmp;
                    }
                    if( REPLACE == RBTR_LAST && ! (nodes[tmp].data < data) ) { // nigdy nie było testowane
                        nodes[tmp].data = data;
                        return -tmp;
                    }
                    tmp = nodes[tmp].right;
                }
            }
        }
        node.parent = parent;
        if( parent == RBT_NULL ) {
            root = nodes.size();
            EXCP( root == 1 );
        } else if( data < nodes[parent].data ) {
            nodes[parent].left = nodes.size();
        } else {
            nodes[parent].right = nodes.size();
        }
        nodes += node;
        return nodes.size()-1;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE min( TNODE node ) const {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        while( nodes[node].left != RBT_NULL ) {
            node = nodes[node].left;
            EXCP( node < nodes.size() );
            EXCP( node > RBT_NULL );
        }
        return node;
    }
    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE min() const {
        return min(root);
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE max( TNODE node ) const {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        while( nodes[node].right != RBT_NULL ) {
            node = nodes[node].right;
            EXCP( node < nodes.size() );
            EXCP( node > RBT_NULL );
        }
        return node;
    }
    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE max() const {
        return max(root);
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE next( TNODE node ) const {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        if( nodes[node].right != RBT_NULL )
            return min( nodes[node].right );
        TNODE parent = nodes[node].parent;
        while( parent != RBT_NULL && node == nodes[parent].right ) {
            node = parent;
            parent = nodes[parent].parent;
        }
        return parent;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE prev( TNODE node ) const {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        if( nodes[node].left != RBT_NULL )
            return max( nodes[node].left );
        TNODE parent = nodes[node].parent;
        while( parent != RBT_NULL && node == nodes[parent].left ) {
            node = parent;
            parent = nodes[parent].parent;
        }
        return parent;
    }

    static bool isNull( CTNODE node ) {
        return node == RBT_NULL;
    }

    const TD& cData( CTNODE node ) const {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        return nodes[node].data;
    }

    // Uwaga, zmiany danych mogą zaburzyć strukturę drzewa.
    // Nie zmieniaj danych tak, żeby zaburzyły porządek.
    // Bezpieczniej użyć cData.
    TD& data( CTNODE node ) {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        return nodes[node].data;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE search( const TDF& data , TNODE node ) {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        while( node != RBT_NULL && !(data == nodes[node].data) ) {
            if( data < nodes[node].data ) {
                node = nodes[node].left;
            } else {
                node = nodes[node].right;
            }
            EXCP( node < nodes.size() );
            EXCP( node >= RBT_NULL );
        }
        return node;
    }
    
    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE search( const TDF& data ) {
        return search( data , root );
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE upperBound( const TDF& data , TNODE node ) {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        TNODE bound = RBT_NULL;
        while( node != RBT_NULL ) {
            if( data < nodes[node].data ) {
                if( bound == RBT_NULL || nodes[node].data < nodes[bound].data )
                    bound = node;
                node = nodes[node].left;
            } else {
                node = nodes[node].right;
            }
        }
        return bound;
    }
    TNODE upperBound( const TDF& data ) {
        return upperBound( data , root );
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE lowerBound( const TDF& data , TNODE node ) {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        TNODE bound = RBT_NULL;
        while( node != RBT_NULL ) {
            if( data <= nodes[node].data ) {
                if( bound == RBT_NULL || nodes[node].data < nodes[bound].data )
                    bound = node;
                node = nodes[node].left;
            } else {
                node = nodes[node].right;
            }
        }
        return bound;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() )
    TNODE lowerBound( const TDF& data ) {
        return lowerBound( data, root );
    }

    // zwraca prawdę jeśli węzeł ma dwóch potomków
    bool twoChildren( CTNODE node ) const {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );
        return nodes[node].left != RBT_NULL && nodes[node].right != RBT_NULL;
    }

    // Zwraca potomka który nie jest nullem, o ile węzeł ma takiego potomka
    TNODE notNullChild( CTNODE node ) const {
       return qMax( nodes[node].left , nodes[node].right ); // sztuczka: null jest zdefiniowane jako najmniejszy indeks
    }

    void removeFixup( TNODE p ) {
        while( p != root && nodes[p].color == RBTC_BLACK ) {
            if( p == nodes[nodes[p].parent].left ) {
                TNODE s = nodes[nodes[p].parent].right;
                if( nodes[s].color == RBTC_RED ) {
                    nodes[s].color = RBTC_BLACK;
                    nodes[nodes[p].parent].color = RBTC_RED;
                    rotateLeft(nodes[p].parent);
                    s = nodes[nodes[p].parent].right;
                }
                if( nodes[nodes[s].left].color == RBTC_BLACK && nodes[nodes[s].right].color == RBTC_BLACK ) {
                    nodes[s].color = RBTC_RED;
                    p = nodes[p].parent;
                } else {
                    if( nodes[nodes[s].right].color == RBTC_BLACK ) {
                        nodes[nodes[s].left].color = RBTC_BLACK;
                        nodes[s].color = RBTC_RED;
                        rotateRight( s );
                        s = nodes[nodes[p].parent].right;
                    }
                    nodes[s].color = nodes[nodes[p].parent].color;
                    nodes[nodes[p].parent].color = RBTC_BLACK;
                    nodes[nodes[s].right].color = RBTC_BLACK;
                    rotateLeft(nodes[p].parent);
                    p = root;
                }
            } else {
                TNODE s = nodes[nodes[p].parent].left;
                if( nodes[s].color == RBTC_RED ) {
                    nodes[s].color = RBTC_BLACK;
                    nodes[nodes[p].parent].color = RBTC_RED;
                    rotateRight(nodes[p].parent);
                    s = nodes[nodes[p].parent].left;
                }
                if( nodes[nodes[s].right].color == RBTC_BLACK && nodes[nodes[s].left].color == RBTC_BLACK ) {
                    nodes[s].color = RBTC_RED;
                    p = nodes[p].parent;
                } else {
                    if( nodes[nodes[s].left].color == RBTC_BLACK ) {
                        nodes[nodes[s].right].color = RBTC_BLACK;
                        nodes[s].color = RBTC_RED;
                        rotateLeft( s );
                        s = nodes[nodes[p].parent].left;
                    }
                    nodes[s].color = nodes[nodes[p].parent].color;
                    nodes[nodes[p].parent].color = RBTC_BLACK;
                    nodes[nodes[s].left].color = RBTC_BLACK;
                    rotateRight(nodes[p].parent);
                    p = root;
                }
            }
        }
        nodes[p].color = RBTC_BLACK;
    }

    void remove( CTNODE node ) {
        EXCP( node < nodes.size() );
        EXCP( node > RBT_NULL );

        CTNODE y = twoChildren(node) ? next(node) : node; // który węzeł naprawdę usunąć? (nigdy nie usuwamy węzła z dwoma potomkami)
        CTNODE x = notNullChild( y );                     // potomek węzła usuwanego lub null gdy węzeł usuwany potomków nie ma.

        nodes[x].parent = nodes[y].parent;                 // potomek bierze rodzica od węzła usuwanego

        if( y == root ) {
            root = x;
        } else if( y == nodes[ nodes[y].parent ].left ) {        // jeśli węzeł usuwany jest lewym potomkiem swojego rodzica
            nodes[ nodes[y].parent ].left = x;                   // to teraz lewym potomkiem rodzica będzie dziecko usuwango węzła
        } else {                                                 // a jeśli węzeł usuwany jest prawym potomkiem swojego rodzica
            EXCP( y == nodes[ nodes[y].parent ].right );
            nodes[ nodes[y].parent ].right = x;                  // to teraz prawym potomkiem rodzica będzie dziecko usuwango węzła
        }                                                        // teraz na nodes[del] nie wskazuje żaden węzeł.

        if( y != node ) {                        // jeśli usuwaliśmy inny węzeł niż zadany parametrem 'node', to
            nodes[node].data = nodes[y].data;    // z węzła usuniętego kopiujemy dane do tego który był zadany do usunięcia.
        }


        if( nodes[y].color == RBTC_BLACK ) {
            removeFixup( x );
        }


        // trzeba także usunąć węzeł z wektora. usuwamy poprzez kopiowanie
        // ostatniego elementu na element usuwany.
        if( y != nodes.size() - 1 ) {
            if( root == nodes.size() - 1 )
                root = y;
            nodes[y] = nodes.last();                         // kopiujemy ostatni element na usuwany
            CTNODE parent = nodes[ y ].parent;               // tylko skrót
            if( parent != RBT_NULL ) {
                if( nodes[ parent ].left == nodes.size()-1 ) {
                    nodes[ parent ].left = y;
                } else {
                    EXCP( nodes[ parent ].right == nodes.size()-1 );
                    nodes[ parent ].right = y;
                }
            }
//            if( nodes[y].left  != RBT_NULL )          // może lepiej zostawić tego ifa? dużo nie spowolni, a węzeł-null nie bedzie tknięty
                nodes[ nodes[y].left ].parent = y;
//            if( nodes[y].right != RBT_NULL )          // -------------------------------||-------------------------------------------------
                nodes[ nodes[y].right ].parent = y;
        }
        nodes.removeLast();                              // usuwamy ostatni
    }

    void rotateLeft( CTNODE x ) {
        CTNODE y = nodes[x].right;
        nodes[x].right = nodes[y].left;
        if( nodes[y].left != RBT_NULL )
            nodes[ nodes[y].left ].parent = x;
        if( y != RBT_NULL )
            nodes[y].parent = nodes[x].parent;
        if( x == root ) {
            root = y;
        } else if( x == nodes[ nodes[x].parent ].left ) {
            nodes[ nodes[x].parent ].left = y;
        } else {
            nodes[ nodes[x].parent ].right = y;
        }
        nodes[y].left = x;
        if( x != RBT_NULL )
            nodes[x].parent = y;
    }
    
    void rotateRight( CTNODE x ) {
        CTNODE y = nodes[x].left;
        nodes[x].left = nodes[y].right;
        if( nodes[y].right != RBT_NULL )
            nodes[ nodes[y].right ].parent = x;
        if( y != RBT_NULL )
            nodes[y].parent = nodes[x].parent;
        if( x != root ) {
            if( x == nodes[ nodes[x].parent ].left ) {
                nodes[ nodes[x].parent ].left = y;
            } else {
                nodes[ nodes[x].parent ].right = y;
            }
        } else {
            root = y;
        }
        nodes[y].right = x;
        if( x != RBT_NULL )
            nodes[x].parent = y;
    }


    TNODE insert( const TD& data ) {
        TNODE x = rawInsert( data );
        if( REPLACE && x < 0 )
            return -x;
        nodes[x].color = RBTC_RED;
        while( x != root && nodes[nodes[x].parent].color == RBTC_RED ) {
            if( nodes[x].parent == nodes[nodes[nodes[x].parent].parent].left ) {
                CTNODE y = nodes[nodes[nodes[x].parent].parent].right;
                if( nodes[y].color == RBTC_RED ) {
                    nodes[ nodes[x].parent ].color = RBTC_BLACK;
                    nodes[y].color = RBTC_BLACK;
                    nodes[ nodes[ nodes[x].parent ].parent ].color = RBTC_RED;
                    x = nodes[ nodes[x].parent ].parent;
                } else {
                    if( x == nodes[nodes[x].parent].right ) {
                        x = nodes[x].parent;
                        rotateLeft(x);
                    }
                    nodes[ nodes[x].parent ].color = RBTC_BLACK;
                    nodes[ nodes[ nodes[x].parent ].parent ].color = RBTC_RED;
                    rotateRight( nodes[ nodes[x].parent ].parent );
                }
            } else {
                CTNODE y = nodes[nodes[nodes[x].parent].parent].left;
                if( nodes[y].color == RBTC_RED ) {
                    nodes[ nodes[x].parent ].color = RBTC_BLACK;
                    nodes[y].color = RBTC_BLACK;
                    nodes[ nodes[ nodes[x].parent ].parent ].color = RBTC_RED;
                    x = nodes[ nodes[x].parent ].parent;
                } else {
                    if( x == nodes[nodes[x].parent].left ) {
                        x = nodes[x].parent;
                        rotateRight(x);
                    }
                    nodes[ nodes[x].parent ].color = RBTC_BLACK;
                    nodes[ nodes[ nodes[x].parent ].parent ].color = RBTC_RED;
                    rotateLeft( nodes[ nodes[x].parent ].parent );
                }
            }
        }
        nodes[root].color = RBTC_BLACK;
        return 0;
    }

    // Sortowanie danych, po posortowaniu można używać metod z przedrostkiem sortXXX, aż
    // do czasu modyfikacji danych.
    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] ); // zamień węzły

            if( nodes[node].parent == nodes[pos].parent ) { // bracia
                RBT_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 ) { // syn i ojciec
                if( nodes[pos].left == pos ) {
                    RBT_SWAP( nodes[pos].left , nodes[node].parent );
                    if( nodes[pos ].right != RBT_NULL ) nodes[nodes[pos ].right].parent = pos ;
                } else {
                    RBT_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 ) { // ojciec i syn
                if( nodes[node].left == node ) {
                    RBT_SWAP( nodes[node].left , nodes[pos].parent );
                    if( nodes[node].right != RBT_NULL ) nodes[nodes[node].right].parent = node ;
                } else {
                    RBT_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 { // brak bezpośredniego spokrewnienia
                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;

            // procedura next by nie zadziałała bez tej operacji, bo pod 'node'
            // jest już inny węzeł z innymi danymi.
            node = pos;
        }
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() ) i posortowanym.
    TNODE sortMin() const {
        return size() == 0 ? RBT_NULL : 1;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() ) i posortowanym.
    TNODE sortMax() const {
        return size(); // sztuczka, powinno być return size() == 0 ? RBT_NULL : size()
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() ) i posortowanym.
    TNODE sortPrev( CTNODE node ) const {
        return node-1;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() ) i posortowanym.
    TNODE sortNext( CTNODE node ) const {
        return node < size() ? node+1 : RBT_NULL;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() ) i posortowanym.
    TNODE sortLowerBound( const TDF &data ) {
        EXCP( ! isEmpty() );

        const RBTNode<TD> *begin = nodes.constData() + 1;
        const RBTNode<TD> *const copy = begin;
        const RBTNode<TD> *end = begin + size() - 1;

        while( end - begin > LOOKUP ) {
            const RBTNode<TD> *const middle = begin + (end - begin)/2;
            if( middle->data < data ) {
                begin = middle + 1;
            } else {
                end = middle;
            }
        }
        while( begin <= end && begin->data < data ) {
            begin ++ ;
        }
        if( begin <= end )
            return (TNODE)(begin - copy) + 1;
        return RBT_NULL;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() ) i posortowanym.
    TNODE sortUpperBound( const TDF &data ) {
        EXCP( ! isEmpty() );

        const RBTNode<TD> *begin = nodes.constData() + 1;
        const RBTNode<TD> *const copy = begin;
        const RBTNode<TD> *end = begin + size() - 1;

        while( end - begin > LOOKUP ) {
            const RBTNode<TD> *const middle = begin + (end - begin)/2;
            if( middle->data <= data ) {
                begin = middle + 1;
            } else {
                end = middle;
            }
        }
        while( begin <= end && begin->data <= data ) {
            begin ++ ;
        }
        if( begin <= end )
            return (TNODE)(begin - copy) + 1;
        return RBT_NULL;
    }

    // Używać tylko na niepustym drzewie if( ! isEmpty() ) i posortowanym.
    TNODE sortSearch( const TDF& data ) {
        EXCP( ! isEmpty() );

        const RBTNode<TD,TNODE> *begin = nodes.constData() + 1;
        const RBTNode<TD,TNODE> *const copy = begin;
        const RBTNode<TD,TNODE> *end = begin + size() - 1;

        while( end - begin > LOOKUP ) {
            const RBTNode<TD,TNODE> *const middle = begin + (end - begin)/2;
            if( middle->data < data ) {
                begin = middle + 1;
            } else {
                end = middle;
            }
        }
        while( begin <= end && begin->data < data ) {
            begin ++ ;
        }
        if( begin <= end && data == begin->data )
            return (TNODE)(begin - copy) + 1;
        return RBT_NULL;
    }

    // jeśli nie chce Ci się przeładowywać operatora << dla Twoich
    // danych, a kompilator wywali błedy, to zakomentuj metodę print.
    void print() const {
        QTextStream out(stdout);
        out << "{{{{" << endl;
        for( int i=0 ; i<nodes.size() ; i++ ) {
            out << "    pos:" << i << endl;
            out << "   left:" << nodes[i].left << endl;
            out << "  right:" << nodes[i].right<< endl;
            out << " parent:" << nodes[i].parent<< endl;
            out << "   data:" << nodes[i].data<<endl;
            out << "--------------------------" << endl;
        }
        out << "}}}}" << endl;
    }


};
Szukaj na tym blogu

Drzewa Czerwno Czarne [Red Black Trees]

kod źródłowy c++ drzewa czerwono czarne RBTree 0.00v

Komentarze

Prześlij komentarz

Popularne posty z tego bloga

benchmark 00 tablicowej implementacji drzew czerwono czarnych

metodyka testowania implementacji drzew czerwono czarnych na bazie tablicy

Do jakich zastosowań nadają się drzewa czerwono-czarne?
