-
Notifications
You must be signed in to change notification settings - Fork 0
/
treaps-implementacao.tex
96 lines (88 loc) · 3.42 KB
/
treaps-implementacao.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
\subsection{Inserção e remoção}
Esta seção descreve uma implementação de inserção e remoção de valores numa treap.
Os algoritmos estão em pseudocódigo.
Estes algoritmos foram baseados no artigo de Seidel e Aragon~%
\cite[p.~450]{SeidelAragon1996},
que contém uma discussão mais completa sobre aspectos práticos da implementação de treaps.
Ignoraremos tanto a etapa da geração aleatória de prioridades
quanto casos de uso como mapeamentos e filas de prioridade;
portanto,
o nó da treap contém quatro membros:
uma chave, uma prioridade,
e dois ponteiros para as subárvores.
Assumiremos, nesta seção,
que a passagem de parâmetros ocorre por referência.
Em ambos os casos,
trabalharemos recursivamente.
Para a inserção,
após inserir o novo elemento na subárvore esquerda (digamos),
pode ser que a raiz da subárvore esquerda
tenha ficado com prioridade maior do que o nó atual.
Neste caso,
rotacionando o nó atual para a direita promove o outro nó a raiz,
sem alterar a ordem das chaves
(que é preservada pela rotação)
nem das prioridades
(pois apenas um novo nó foi inserido na subárvore esquerda).
A inserção na subárvore direita é simétrica.
\begin{codebox}
\Procname{$\proc{Treap-Insert}(T, \id{key}, \id{priority})$}
\li \If $T == \id{null}$
\li \Then
$T \gets \proc{New-Node(\id{key}, \id{priority})}$
\li \ElseIf $\id{key} < \attrib{T}{key}$
\li \Then
$\proc{Treap-Insert}(\attrib{T}{lchild}, \id{key}, \id{priority})$
\li \If $\attribb{T}{lchild}{priority} > \attrib{T}{priority}$
\li \Then $\proc{Rotate-Right}(T)$
\End
\li \ElseIf $\attrib{T}{key} < \id{key}$
\li \Then
$\proc{Treap-Insert}(\attrib{T}{rchild}, \id{key}, \id{priority})$
\li \If $\attribb{T}{rchild}{priority} > \attrib{T}{priority}$
\li \Then $\proc{Rotate-Left}(T)$
\End
\li \ElseNoIf
\li \Comment A chave já aparece na árvore.
\End
\end{codebox}
Para a remoção,
faremos em duas partes:
primeiro, localizar a subárvore na treap
que possui o elemento a ser removido como raiz.
\begin{codebox}
\Procname{$\proc{Treap-Remove}(T, \id{key})$}
\li \If $T == \id{null}$
\li \Then \Comment Elemento não aparece na árvore.
\li \ElseIf $\id{key} < \attrib{T}{key}$
\li \Then $\proc{Treap-Remove}(\attrib{T}{lchild}, \id{key})$
\li \ElseIf $\attrib{T}{key} < \id{key}$
\li \Then $\proc{Treap-Remove}(\attrib{T}{rchild}, \id{key})$
\li \ElseNoIf
\li $\proc{Root-Remove}(T)$
\End
\end{codebox}
E, agora, excluiremos a raiz desta subárvore.
Se algum dos nós filhos da raiz não estiver presente,
basta substituí-lo pelo outro nó (que pode ser nulo);
caso contrário,
rotacionaremos a raiz para baixo
e chamaremos o procedimento recursivamente.
Em algum momento,
o nó a ser removido se tornará folha,
caindo no caso anterior.
\begin{codebox}
\Procname{$\proc{Root-Remove}(T)$}
\li \If $\attrib{T}{lchild} == \id{null}$
\li \Then $T \gets \attrib{T}{rchild}$
\li \ElseIf $\attrib{T}{rchild} == \id{null}$
\li \Then $T \gets \attrib{T}{lchild}$
\li \ElseIf $\attribb{T}{lchild}{priority} < \attribb{T}{rchild}{priority}$
\li \Then
$\proc{Rotate-Left}(T)$
\li $\proc{Root-Remove}(\attrib{T}{lchild})$
\li \ElseNoIf
\li $\proc{Rotate-Right}(T)$
\li $\proc{Root-Remove}(\attrib{T}{rchild})$
\End
\end{codebox}