Treap

Treap

En Ciències de la Computació, el treap i el arbre binari de busca aleatori són dos formes d'arbre binari de busca estretament relacionades que mantenen un conjunt dinàmic de claus ordenades i permeten busca binaria sobre les claus almagasenades. Despuix d'una seqüència d'insercions i borrats de claus, la forma del treap és una variable aleatòria en la mateixa distribució de provabilitat que un arbre binari de busca aleatori; en particular, en alta provabilitat, la seua altura és proporcional al logaritme del número de claus, de modo que cada operació de busca, inserció, o borrat pren temps logarítmic.

Descripció

Un treap en claus alfabètiques i prioritats numèriques en un heap de màxim.

El treap va ser descrit per primera volta per Cecilia R. Aragó i Raimund Seidel en 1989; el seu nom es deu a la composició de tree (arbre) en heap. És un Arbre Cartesiano en el qual cada clau és un número triat aleatoriamente. Com qualsevol arbre binari de busca el recorregut in-orde és el mateix que les claus ordenades. L'estructura de l'arbre està determinada per l'orde d'un heap màxim: açò és, el número de prioritat per a qualsevol nodo intern és major o igual que la prioritat dels seus fills.

Una manera equivalent de descriure el treap, és insertant els nodos en major prioritat primer en un arbre binari de busca sense balancejar. Per tant, si les prioritats són números aleatoris independents (d'una distribució sobre un espai suficientment gran com per a assegurar que dos nodos no compartixquen la mateixa prioritat en una alta provabilitat) llavors la forma d'un treap té la mateixa distribució de provabilitat que un arbre binari de busca aleatori, un arbre de busca format per insertar les claus de forma aleatòria sense realisar balancege. Degut a que els arbres de busca aleatoris tenen altura logarítmica en alta provabilitat, igual ocorre per al treap.

Aragon i Seidel sugerixen assignar prioritats més altes als nodos en major freqüència d'accessos, com a eixemple, en cada accés, es tria un número aleatori i es reemplaça la prioritat del nodo en dit número si este és major que la prioritat del nodo. Esta modificació provoca que l'arbre perga la seua forma aleatòria; en canvi, els nodos accedits més freqüentment estaran en major provabilitat prop de la raïl, provocant busques més ràpides.

Naor i Nissim descriuen una aplicació del treap per a mantindre certificats d'autorisació i criptosistemas de clau pública.

Operacions

El treap soporta les següents operacions bàsiques:

• Per a buscar un valor d'una clau donada, s'aplica l'algoritme de busca estàndar sobre un arbre binari de busca ignorant les prioritats.
• Per a insertar una nova clau x al treap, es genera una prioritat aleatòria i per a x. Després s'inserta x aplicant l'algoritme estàndar d'inserció sobre un arbre binari de busca. Després, mentres x no siga la raïl de l'arbre i tinga prioritat major que el seu pare z, realisar una rotació que intercanvie la relació pare-fill entre x i z.
• Per a eliminar un nodo x del treap, si x és un full de l'arbre, senzillament ho borrem. Si x té solament un fill z, borrem x de l'arbre i fem z fill del pare de x (o establim z com a raïl de l'arbre si x no té pare). Finalment, si x té dos fills, intercanvi la seua posició en l'arbre en la posició del seu successor immediat z quan les claus són ordenades, resultant en un dels casos anteriors. En este cas final, l'intercanvi pot violar la propietat d'heap para z, aixina que rotacions adicionals seran necessàries per a restaurar dita propietat.

Operacions Massives

En adició a les operacions de inserció, borrat i busca d'un sol element; s'han definit algunes operacions "massives" sobre el treap: unió, intersecció i diferència de conjunt. Totes estes operacions es basen en l'implementació d'atres dos rutines: split (dividir) i merge (mesclar).

• Per a dividir un treap en dos treaps més menuts, un a on apareguen tots els elements menors que x, i un atre contenint els elements majors que x; s'inserta x en màxima prioritat - prioritat major que qualsevol atra en el treap. Després de l'inserció, x serà la raïl del treap i tots els elements en el subárbol esquerre seran menors que x i tots en el subárbol dret seran majors. El cost d'esta operació és com a molt el cost d'una inserció simple en el treap.

• Per a mesclar dos treaps resultants d'una divisió en la rutina split (podem assumir que el major valor en el primer treap és menor que el valor més chicotet del segon), vàrem crear un nodo nou en valor x, tal que x és més gran que el major valor del primer treap, i més chicotet que el menor valor en el segon treap, li assignem prioritat mínima i fem el primer treap fill esquerre de x i el segon treap el seu fill dret. Rotamos com siga necessari per a mantindre l'orde del heap de màxims en el treap. Després de fer les rotacions i establir l'orde correcte, x serà un full del treap (perque té prioritat mínima) i es podrà eliminar fàcilment. El resultat és la mescla dels dos treaps originals en un sol treap.

L'unió de dos t₁reaps t1 i t2, representant els conjunts A i B és un treap t que representa A A ∪ B B. L'algoritme recursivo següent computa l'unió:

function union(t1, t2):
    if t1 = nil:
        return t2
    if t2 = nil:
        return t1
    if priority(t1) < priority(t2):
        swap t1 and t2
    t<, t> ← split t2 on key(t1)
    return new node(key(t1),
                    union(left(t1), t<),
                    union(right(t1), t>))

S'assumix que la rutina split torna dos arbres: un contenint els elements en clau menor que la proporcionada, i un atre en els majors.

L'algoritme per a l'intersecció és similar, pero requerix una rutina extra cridada join. La complexitat de cada d'unió, intersecció i diferència és O(mlog(n/m)) per a treaps de tamany m i n, en m <= n. Adicionalment, com els cridats recursivos en l'unió són independents uns d'uns atres, poden eixecutar-se en paralel.