-
Notifications
You must be signed in to change notification settings - Fork 0
/
treaps.tex
151 lines (137 loc) · 6.24 KB
/
treaps.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
\section{Aplicação: Treaps}
\label{sec:treaps}
De acordo com o Teorema~\ref{thm:average-tree-depth},
uma árvore de busca gerada aleatoriamente
possui altura esperada logarítmica.
Mais especificamente,
uma árvore de $n$ nós
deve ter profundidade pouco inferior a $3 \log_2 n$.
Árvores autobalanceadas,
como AVL e rubro-negras,
possuem profundidade inferior a $1.441 \log_2 n$ \cite[p.~460]{Knuth1998}
e $2 \log_2 n$ \cite[p.~309]{CormenLeisersonRivestStein2009},
respectivamente.
Portanto,
na média,
árvores binárias de busca geradas aleatoriamente
possuem profundidade similar às árvores autobalanceadas,
mas sem o overhead de fazer o balanceamento.
Entretanto,
tipicamente, ocorrem inserções e remoções de maneira desordenada na árvore.
Assim,
não basta permutar os nós aleatoriamente apenas uma vez,
pois a árvore e os elementos variam ao longo da execução do programa.
Sabe-se muito pouco sobre o comportamento de árvores binárias de busca
quando inserções e remoções são intercaladas%
~\cite[p.~300]{CormenLeisersonRivestStein2009},
portanto é necessário cuidado ao alterar uma árvore gerada aleatoriamente
para que sua ``aleatoriedade'' se mantenha,
o que nos permite analisá-la.
Treaps
(introduzidas por Aragon e Seidel~\cite{AragonSeidel1989})
são uma forma de preservar a aleatoriedade.
A ideia é associar cada elemento a uma prioridade aleatória,
e permutar o vetor de acordo com essa prioridade.
Como a inserção/remoção de elementos
não altera a distribuição de prioridades,
a árvore continuará sendo uma árvore binária de busca aleatória,
preservando a profundidade esperada logarítmica.
Para definir treaps, precisamos do conceito de \emph{heap}.
\begin{definition}
Uma árvore binária em que todos os nós possuem uma prioridade associada
é um \emph{heap}
se todos os nós da árvore tiverem prioridade maior do que seus filhos.
\end{definition}
É importante notar que há um conceito alternativo de heap na literatura;
em textos como o livro de Cormen et. al.~\cite[p.~152]{CormenLeisersonRivestStein2009},
um heap, além de satisfazer a exigência acima,
ainda precisa ser uma árvore binária completa ou quase completa
--- isto é, todos os níveis precisam estar completos,
com exceção do último, que pode estar incompleto,
mas precisa ser preenchido da esquerda para a direita.
Esta restrição adicional
faz com que heaps possam ser eficientemente implementadas como um vetor,
tanto acelerando acesso e modificação quanto reduzindo o espaço utilizado.
(Note que todas essas otimizações apenas mexem na constante associada.)
Alguns textos, como o livro de Sedgewick e Flajolet~\cite[p.~362]{SedgewickFlajolet2013},
chamam a condição acima de ``ordem de heap'';
então, o que eles chamam de ``árvore em ordem de heap'',
nós chamaremos simplesmente de ``heap''.
A Figura~\ref{fig:heap} contêm um exemplo de heap.
\begin{figure}[h]
\centering
\begin{tikzpicture}[binary tree layout, nodes={circle, draw}]
\node {8}
child { node {4}
child { node {2} }
child { node {3} }
}
child { node {7}
child[missing]
child { node {6}
child { node {1} }
child { node {5} }
}
};
\end{tikzpicture}
\caption{Heap correspondente à permutação $(2, 4, 3, 8, 7, 1, 6, 5)$.}
\label{fig:heap}
\end{figure}
É interessante notar que existe uma bijeção simples entre
permutações de $n$ elementos e heaps construídas com os números $\{1, \dots, n\}$.
Dada um heap, para construir a permutação correspondente,
basta percorrer os nós em ordem simétrica (in-order).
Para reconstruir o heap a partir da permutação,
tome $k$ como sendo o índice do maior elemento e coloque-o como raiz;
construa a subárvore esquerda recursivamente
usando os elementos nas posições $1, \dots, k-1$,
e a subárvore direita usando os elemento nas posições $k+1, \dots, n$.
Isso mostra que existem $n!$ heaps sobre um conjunto de elementos distintos.
De posse da definição de heap,
podemos definir treap.
\begin{definition}
Uma árvore binária cujos nós possuem tanto chaves quanto prioridades associadas
é uma \emph{treap}
se for simultaneamente uma árvore de busca de acordo com as chaves
e um heap de acordo com as prioridades.
\end{definition}
As prioridades serão escolhidas aleatoriamente.
Treaps são, portanto, árvores-heap.
As chaves impõem a ordem dos nós;
como existem $C_n$ diferentes árvores de busca possíveis para a mesma ordem,
as prioridades aleatórias forçam a escolha de uma destas árvores.
Dado um conjunto $X = \{ (k_i, p_i) \mid 1 \leq i \leq n) \}$,
se todas as prioridades forem distintas,
existe uma única treap que contém os elementos deste conjunto.
Para construí-la,
observe que a raiz da árvore necessariamente será o elemento de maior prioridade.
Depois de fixada a raiz,
a exigência do ordenamento determina quais nós ficarão na subárvore esquerda
e quais ficarão na subárvore direita.
Repita esta construção em cada subárvore;
por indução, existe uma única treap em cada caso,
o que garante a existência e unicidade da árvore atual.
Alternativamente,
podemos construir uma árvore binária de busca
inserindo os nós em ordem decrescente de prioridade.
A construção padrão sempre adiciona um novo nó como uma folha,
portanto teremos um heap;
e a ordem é garantida pelo próprio algoritmo.
Este é o ``truque'' das treaps:
ao escolher aleatoriamente uma prioridade para cada elemento,
estamos, efetivamente,
permutando os elementos e então inserindo-os na árvore.
Conforme analisado no Teorema~\ref{thm:shuffle-by-sorting},
todas as permutações dos elementos são equiprováveis.
Portanto,
as árvores binárias de busca geradas
seguem a distribuição analisada no Teorema~\ref{thm:average-tree-depth};
assim,
sabemos que a profundidade média das treaps será $3 \log_2 n$.
Operações como inserir e remover elementos
podem ser entendidos como apenas alterando o conjunto de elementos $X$;
como a treap é única e as prioridades são aleatórias,
inserção e remoção alteram diretamente a permutação subjacente,
mantendo a profundidade esperada em $3 \log_2 n$.
(Observe que a inserção de um novo elemento
exige a geração de uma nova prioridade aleatória.)