AA drvo

AA drvo u računarskim naukama je forma balansiranog drveta koje se koristi za čuvanje i vraćanje složenih podataka efikasno. AA drva se nazvana po Arne Andersson, njihovom pronalazaču.

AA drva su varijacija crveno-crnih drva, forma binarno pretraživačkog stabla koje podržava efikasno dodavanje i brisanje ulaza. Za razliku od crveno-crniog drveta, crveni čvorovi na AA drvetu mogu jedino da budu dodata kao desna deca. Drugim rečima, nijedan crveni čvor ne može da bude levo dete. Ovo rezultuje simulaciji 2-3 drveta umesto 2-3-4 drveta, što vrlo pojednostavljuje operacije za održavanje. Algoritmi za održavanje u crveno-crnom drvetu su zahtevale uzimanje u obzir sedam različitih oblika da bi se pravilno balansiralo drvo:

AA drvo u drugu ruku samo treba da uzme u obzir dava oblika s obzirom na striktnu potrebu da samo desne veze mogu da budu crvene:

Balansirajuće rotacije

Dok crveno-crno drvo zahteva jedan deo balansirajućih meta podataka po čvoru (boju), AA drva zahtevaju O(log(N)) delova meta podataka po čvoru; u formi celog broja "nivoa". Sledeće invarijante postoje za AA drva:

1. Nivo svakog čvora koji je list je jedan.
2. Nivo svakog levog deteta je tačno za jedan manji od roditelja.
3. Nivo svakog desnog deteta je jednak ili manji za jedan od njegovog roditelja.
4. Nivo svakog desnog unuka je striktno manji od nivoa roditelja roditelja.
5. Svaki čor nivoa većeg od jedan ima dvoje dece.

Veza gde je nivo deteta jednak roditeljevom se zove horizontalna veza, i analogna je crvenoj vezi u crveno-crnom drvetu. Individualne desne horizontalne veze su dozvoljene, ali uzastopne su zabranjene; sve lefe horizontalne veze su zabranjene. Ovo su stroža ograničenja od analognih ograničenja crveno-crnog drveta, sa rezultatom da je rebalansiranje AA drveta proceduralno mnogo jednostavnije od rebalansiranja crveno-crnog drveta.

Ubacivanja i brisanja mogu prolazno da izazovu da AA drvo postane nebalansirano (što znači, da prekrše invarijante AA drveta). Samo dve slične operacije su potrebne za rebalansiranje "skew" i "split". Skew je desna rotacija koja zamenjuje poddrvo koje sadrži levu horizontalnu vezu sa onim koje sadrži desnu horizontalnu vezu. Split je leva rotacija i povećanje nivoa da se zameni poddrvo koje sadrži dve ili više uzastopnih desnih horizontalnih veza sa onim koje sadrži manje uzastopnih desnih horizontalnih veza. Implementacija ubacivanja i brisanja koji održavaju balans je pojednostavljeno uvođenjem skew i split operacija za modifikaciju drveta samo ako je potrebno, umesto pravljenjem njihovih poziva da li da rade skew ili split.

function skew is
    input: T, a node representing an AA tree that needs to be rebalanced.
    output: Another node representing the rebalanced AA tree.

    if nil(T) then
        return Nil
    else if nil(left(T)) then
        return T
    else if level(left(T)) == level(T) then
        Swap the pointers of horizontal left links.
        L = left(T)
        left(T) := right(L)
        right(L) := T
        return L
    else
        return T
    end if
end function

Skew:

function split is
    input: T, a node representing an AA tree that needs to be rebalanced.
    output: Another node representing the rebalanced AA tree.

    if nil(T) then
        return Nil
    else if nil(right(T)) or  nil(right(right(T))) then
        return T
    else if level(T) == level(right(right(T))) then
        We have two horizontal right links.  Take the middle node, elevate it, and return it.
        R = right(T)
        right(T) := left(R)
        left(R) := T
        level(R) := level(R) + 1
        return R
    else
        return T
    end if
end function

Split:

Dodavanje

Ubacivanje počinje sa normalnim binarnim pretraživačkim drvetom i procedurom ubacivanja. Zatim, kako se stek zvanja razvija (pretpostavljajući rekurzivnu implementaciju pretraživanja), lako se proverava tačnost drveta i izvodi bilo koja rotacija ako je potrebno. Ako horizontalna leva veza nastane, izvešće se skew, i ako dve horizontalne desne veze nastanu, izvešće se split, moguće inkrementirajući nivo novog čvora koji je koren trenutnog podstabla. Primetimo, u gore datom kodu, inkrementacija nivoa (T). Ovo čini neophodnim nastavljanje proveravanja tačnosti drveta kako modifikacije izranjaju iz listova.

function insert is
    input: X, the value to be inserted, and T, the root of the tree to insert it into.
    output: A balanced version T including X.

    Do the normal binary tree insertion procedure. Set the result of the
    recursive call to the correct child in case a new node was created or the
    root of the subtree changes.
    if nil(T) then
        Create a new leaf node with X.
        return node(X, 1, Nil, Nil)
    else if X < value(T) then
        left(T) := insert(X, left(T))
    else if X > value(T) then
        right(T) := insert(X, right(T))
    end if
    Note that the case of X == value(T) is unspecified. As given, an insert
    will have no effect. The implementor may desire different behavior.

    Perform skew and then split. The conditionals that determine whether or
    not a rotation will occur or not are inside of the procedures, as given
    above.
    T := skew(T)
    T := split(T)

    return T
end function

Brisanje

Kao u većini balansiranih binarnih drveća, brisanje unutrašnjeg čvora može biti pretvoreno u brisanje čvora koji je list zamenjujući unutrašnji čvor sa ili najbližim pretkom ili naslednikom, zavisno od toga koji su u drvetu ili implementatorskim hirovima. Vraćanje pretka je jednostavno stvar praćenja jedne leve veze i onda svih preostaliih desnih veza. Isto, naslednik može da se pronađe idući jednom desno i levo dok se ne stigne do pokazivača na nulu. Zbog karakteristike AA da svi čvorovi nivoa većeg od jedan koji imaju dvoje dece, naslednik ili predak će biti u nivou 1, što čini njihovo uklanjanje trivijalnim.

Da bi se rebalansiralo drvo, postoji nekoliko pristupa. Jedan opisan od strane Andersson u njegovom originalnom radu je najjednostavniji, i opisan je ovde, međutim stvarna implementacija može da se odluči za optimizovaniji pristup. Nakon uklanjanja, prvi korak za održavanje validnosti drveta je da se smanji nivo svakog čvora čija su deca dva nivoa ispod njih, ili kojima nedotaju deca. Onda, Ceo nivo mora da se skewed i split. Ovaj pristup je favorizovan, jer kada se prikaže konceptualno, ima tri jednostavno razumljivih odvojenih koraka:

1. Smanji nivo, ako je potrebno.
2. Skew nivo.
3. Split nivo.

Međutim, moramo da skew i split ceo nivo ovaj put umesto samo čvora, komplikujući naš kod.

function delete is
    input: X, the value to delete, and T, the root of the tree from which it should be deleted.
    output: T, balanced, without the value X.
   
    if nil(T) then
        return T
    else if X > value(T) then
        right(T) := delete(X, right(T))
    else if X < value(T) then
        left(T) := delete(X, left(T))
    else
        If we're a leaf, easy, otherwise reduce to leaf case. 
        if leaf(T) then
            return Nil
        else if nil(left(T)) then
            L := successor(T)
            right(T) := delete(value(L), right(T))
            value(T) := value(L)
        else
            L := predecessor(T)
            left(T) := delete(value(L), left(T))
            value(T) := value(L)
        end if
    end if

    Rebalance the tree. Decrease the level of all nodes in this level if
    necessary, and then skew and split all nodes in the new level.
    T := decrease_level(T)
    T := skew(T)
    right(T) := skew(right(T))
    if not nil(right(T))
        right(right(T)) := skew(right(right(T)))
    end if
    T := split(T)
    right(T) := split(right(T))
    return T
end function

function decrease_level is
    input: T, a tree for which we want to remove links that skip levels.
    output: T with its level decreased.

    should_be = min(level(left(T)), level(right(T))) + 1
    if should_be < level(T) then
        level(T) := should_be
        if should_be < level(right(T)) then
            level(right(T)) := should_be
        end if
    end if
    return T
end function

Dobar primer brisanja ovim algoritmom se nalazi u Andersson paper.

Performanse

Performanse AA drveta su ekvivalentne performansama crveno-crnog drveta. Dok AA drvo pravi više rotacija nego crveno-crno drvo, jednostavniji algoritmi teže da budu brži, i sve ovo balansira do sličnih performansi. Crveno-crno drvo je konzistentnije u peformansama nego AA drvo, ali AA drvo teži da bude ravnije, što rezultuje za nijansu bržem vremenu pretraživanja.

Vidi još

• Red-black tree
• B-tree
• AVL tree
• Scapegoat tree

Spoljašnje veze

• A. Andersson. Balanced search trees made simple
• A. Andersson. A note on searching in a binary search tree
• AA-Tree Applet Arhivirano na sajtu Wayback Machine (4. mart 2015) by Kubo Kovac
• BSTlib Arhivirano na sajtu Wayback Machine (7. avgust 2011) - Open source AA tree library for C by trijezdci
• AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures
• Thorough tutorial Julienne Walker with lots of code, including a practical implementation
• Object Oriented implementation with tests
• A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75) - Comparison of AA trees, red-black trees, treaps, skip lists, and radix trees
• An Objective-C implementation