En ciencias da computación, o treap e a árbore binaria de busca aleatorizada son dúas formas moi relacionadas de estruturas de datos de árbore binaria de busca que manteñen un conxunto dinámico de chaves ordenadas e permiten buscas binarias entre as chaves. Despois de calquera secuencia de insercións e borrados de chaves, a forma da árbore é unha variable aleatoria coa mesma distribución de probabilidade cá dunha árbore binaria aleatoria; en particular, con alta probabilidade a súa altura é proporcional ao logaritmo do número de chaves, de modo que cada busca, inserción ou borrado leva tempo logarítmico.
Descrición miniatura|esquerda|alt=Un treap con chave alfabética e orde de montículo máximo numérica.|Un treap con chave alfabética e orde de montículo máximo numérica. O treap foi descrito por primeira vez por Raimund Seidel e Cecilia R. Aragon en 1989; o seu nome é un acrónimo combinado de tree (árbore) e heap (montículo).
É unha árbore cartesiana na que a cada chave se lle dá unha prioridade numérica (escollida aleatoriamente). Como en calquera árbore binaria de busca, a orde do percorrido en orde dos nós é a mesma que a orde ordenada das chaves. A estrutura da árbore vén determinada polo requisito de estar ordenada como montículo: é dicir, o número de prioridade de calquera nó non folla debe ser maior ou igual cá dos seus fillos. Así, como nas árbores cartesianas en xeral, o nó raíz é o de máxima prioridade, e as súas subárbores esquerda e dereita fórmanse do mesmo xeito a partir das subsecuencias da orde ordenada á esquerda e á dereita dese nó.
Unha forma equivalente de describir o treap é que se pode formar inserindo os nós de maior prioridade primeiro nunha árbore binaria de busca sen facer ningún reequilibrado. Por tanto, se as prioridades son números aleatorios independentes (dunha distribución sobre un espazo de prioridades suficientemente grande para que dous nós teñan moi pouca probabilidade de coincidir), a forma dun treap ten a mesma distribución de probabilidade cá forma dunha árbore binaria de busca aleatoria, unha árbore de busca formada inserindo os nós sen reequilibrar nunha orde de inserción escollida ao azar. Como se sabe que as árbores binarias de busca aleatorias teñen altura logarítmica con alta probabilidade, o mesmo é certo para os treaps. Isto reflicte o argumento da árbore binaria de busca de que o quicksort execútase en tempo esperado . Se as árbores binarias de busca son solucións á versión de problema dinámico da ordenación, os treaps corresponden concretamente ao quicksort dinámico, onde as prioridades guían a elección do pivote.
Aragon e Seidel tamén suxiren asignar prioridades máis altas aos nós accedidos con frecuencia, por exemplo cun proceso que, en cada acceso, escolle un número aleatorio e substitúe a prioridade do nó por ese número se é maior ca a anterior. Esta modificación faría que a árbore perdese a súa forma aleatoria; no canto diso, os nós accedidos con frecuencia terían máis probabilidade de estar preto da raíz, o que faría máis rápidas as buscas.
Naor e Nissim describen unha aplicación para manter certificados de autorización en criptosistemas de chave pública.
Operacións Operacións básicas Os treaps admiten as seguintes operacións básicas: Para buscar unha chave dada, aplícase un algoritmo de busca binaria estándar nunha árbore binaria de busca, ignorando as prioridades. Para inserir unha nova chave x no treap, xérase unha prioridade aleatoria y para x. Búscase x na árbore e créase un novo nó na posición de folla onde a busca binaria determine que debe estar. Despois, mentres x non sexa a raíz da árbore e teña un número de prioridade maior cá do seu pai z, realízase unha rotación que invirte a relación pai-fillo entre x e z. Para borrar un nó x, facelo descender mediante rotacións ata convertelo nunha folla e retiralo. Se ten dous fillos, ascende o de maior prioridade; se só ten un, ascende ese fillo. Así consérvase a orde de busca e, ao retirar x, queda restablecida a orde de montículo. As prioridades dos nós restantes non cambian.
Construción dun treap Para construír un treap pódense inserir n valores con prioridades aleatorias independentes. O custo esperado é ; non é unha garantía para o peor caso.
Operacións en bloque Ademais das operacións dun só elemento (inserción, borrado e busca), definíronse varias operacións «en bloque» rápidas sobre os treaps: unión, intersección e diferenza. Apoianse en dúas operacións auxiliares, split e join.
Para dividir un treap en dous treaps, un coas chaves menores que x e outro coas maiores, pódese inserir temporalmente x cunha prioridade maior cá de calquera nó, se a chave non estaba presente. Se xa existía, elévase temporalmente a súa prioridade por riba das demais. En ambos os casos, faise ascender x mediante rotacións ata a raíz; só entón se retira ese nó e se devolven por separado as súas subárbores esquerda e dereita. As prioridades dos nós restantes consérvanse. O custo é proporcional á lonxitude do camiño de busca. O pseudocódigo de split seguinte realiza a división por recursión, sen precisar este cambio temporal de prioridade. Para unir dous treaps coas chaves do primeiro menores ca todas as do segundo, pódese crear provisionalmente unha árbore binaria de busca cun novo nó separador x na raíz, de prioridade menor ca a de todos os nós existentes, e coas dúas árbores como fillas. Esta árbore provisional aínda non cumpre a orde de montículo: rótase x cara abaixo, ascendendo en cada paso o fillo de maior prioridade, ata que x sexa unha folla e se poida retirar. O resultado é un treap sen o separador. Se se quere conservar unha chave x de prioridade arbitraria, úsase a operación join(L, k, R) descrita a continuación. miniatura|Unión realizada sobre os treaps e . O fillo dereito de tras a unión defínese como unha unión do seu antigo fillo dereito e .
No pseudocódigo seguinte, k é un rexistro que conserva a chave e a prioridade. root_item(T) devolve o rexistro da raíz de T, e prior(a,b) comproba se a prioridade de a é maior ca a de b. A prioridade de root_item(nil) defínese como menos infinito. Suponse unha orde total de prioridades, con desempate se é necesario. O algoritmo de unión de dúas árbores separadas por k é: function join(L, k, R) if prior(k, root_item(L)) and prior(k, root_item(R)) return Node(L, k, R) if prior(root_item(L), root_item(R)) return Node(left(L), root_item(L), join(right(L), k, R)) return Node(join(L, k, left(R)), root_item(R), right(R)) miniatura|Para dividir por , faise unha chamada recursiva de división ao fillo esquerdo ou ao dereito de . O algoritmo de división é o seguinte: function split(T, k) if (T = nil) return (nil, false, nil) (L, (m, c), R) = expose(T) if (k = m) return (L, true, R) if (k < m) (L', b, R') = split(L, k) return (L', b, join(R', (m, c), R)) if (k > m) (L', b, R') = split(R, k) return (join(L, (m, c), L'), b, R')
A unión de dous treaps e , que representan os conxuntos e , é un treap que representa . O seguinte algoritmo recursivo calcula a unión: function union(t1, t2): if t1 = nil: return t2 if t2 = nil: return t1 if priority(t1) < priority(t2): swap t1 and t2 (t<, found, t>) ← split(t2, key(t1)) return join(union(left(t1), t<), root_item(t1), union(right(t1), t>))
Aquí split devolve unha árbore coas chaves menores, un indicador de presenza e outra coas maiores. union descarta o indicador porque a chave central xa pertence á primeira árbore. O algoritmo conserva as prioridades e pode implementarse de forma non destrutiva, creando novos nós e compartindo as subárbores intactas.
Os algoritmos para a intersección e a diferenza son similares; cando non se conserva a chave central, cómpre unir as subárbores sen esa chave. A complexidade esperada de cada unha de unión, intersección e diferenza é para treaps con prioridades aleatorias de tamaños e , con . Ademais, como as chamadas recursivas á unión son independentes entre si, pódense executar en paralelo.
Árbore binaria de busca aleatorizada A árbore binaria de busca aleatorizada, introducida por Martínez e Roura posteriormente ao traballo de Aragon e Seidel sobre os treaps, almacena os mesmos nós coa mesma distribución aleatoria da forma da árbore, pero mantén información distinta nos nós para conservar a súa estrutura aleatorizada.
En lugar de gardar prioridades aleatorias en cada nó, a árbore binaria de busca aleatorizada garda un número enteiro pequeno en cada nó: o número dos seus descendentes (contándose a si mesmo como un). Estes números pódense manter durante as rotacións cun custo adicional constante por rotación. Cando hai que inserir unha chave x nunha árbore que xa ten n nós, o algoritmo de inserción escolle con probabilidade 1/(n+1) colocar x como nova raíz da árbore e, se non, chama recursivamente ao procedemento de inserción para inserir x na subárbore esquerda ou dereita (segundo se a súa chave é menor ou maior cá da raíz). Os números de descendentes úsanse para calcular as probabilidades necesarias nas eleccións aleatorias de cada paso. Colocar x na raíz dunha subárbore pódese facer como no treap, inseríndoo nunha folla e rotándoo cara arriba, ou cun algoritmo alternativo descrito por Martínez e Roura que divide a subárbore en dúas partes que se usan como fillos esquerdo e dereito do novo nó.
O procedemento de borrado dunha árbore binaria de busca aleatorizada usa a mesma información por nó cá inserción, pero, a diferenza desta, só necesita de media decisións aleatorias para unir as dúas subárbores que descenden dos fillos esquerdo e dereito do nó borrado nunha soa árbore. Isto débese a que as subárbores que se van unir están de media en profundidade ; unir dúas árbores de tamaños n e m necesita decisións aleatorias de media. Se a subárbore esquerda ou dereita do nó que se vai borrar está baleira, a operación de unión é trivial; se non, elíxese o fillo esquerdo ou dereito do nó borrado como nova raíz da subárbore cunha probabilidade proporcional ao seu número de descendentes, e a unión prosegue recursivamente.
Comparación A información gardada por nó na árbore binaria aleatorizada é máis simple cá dun treap (un número enteiro pequeno no canto dun número aleatorio de alta precisión), pero fai un maior número de chamadas ao xerador de números aleatorios ( chamadas por inserción ou borrado no canto dunha por inserción) e o procedemento de inserción é algo máis complicado pola necesidade de actualizar os números de descendentes por nó. Unha diferenza técnica menor é que nun treap hai unha pequena probabilidade de colisión (dúas chaves coa mesma prioridade) e, en ambos os casos, haberá diferenzas estatísticas entre un xerador de números aleatorios verdadeiro e o pseudoaleatorio que adoitan usar os ordenadores dixitais. Con todo, en calquera caso, as diferenzas entre o modelo teórico de eleccións perfectamente aleatorias usado para deseñar o algoritmo e as capacidades dos xeradores reais son insignificantes.
Aínda que o treap e a árbore binaria de busca aleatorizada teñen a mesma distribución aleatoria de formas tras cada actualización, a historia das modificacións realizadas por estas dúas estruturas ao longo dunha secuencia de insercións e borrados pode ser distinta. Por exemplo, nun treap, se os tres números 1, 2 e 3 se insiren na orde 1, 3, 2, e despois se borra o número 2, os dous nós restantes terán a mesma relación pai-fillo que tiñan antes de inserir o número do medio. Nunha árbore binaria de busca aleatorizada, as novas eleccións aleatorias da inserción e do borrado poden cambiar esa relación. Conservar a distribución aleatoria das formas non implica que a forma posterior sexa independente da anterior.
Notas
Véxase tamén Outros artigos Árbore binaria de busca Árbore binaria de busca auto-equilibrada Montículo Skip list Árbore cartesiana
Ligazóns externas Treaps en Wikimedia Commons Colección de referencias e información sobre treaps, de Cecilia Aragon