18_Estágio Docência - Cartesian Tree

Prévia do material em texto

Mikaela Maia
Departamento de Sistemas e Computação
Universidade Federal de Campina Grande
� Árvore Binária derivada de uma sequência de 
números 
� Introduzida por Vuillemin em 1980 no 
contexto de geometric range searching data 
structures
� Usada na definição de Treap
2
3
� Um nó para cada número de uma sequência
� Caminhar em ordem na árvore resulta na 
sequência original
◦ A árvore à esquerda de um nó consiste em valores 
anteriores a ele na ordem da sequência
◦ A árvore à direita de um nó consiste em valores 
posteriores a ele na ordem da sequência
� Heap property (Min)
◦ O pai de qualquer nó não-raiz tem um valor 
inferior que o valor de seus filhos 4
� Baseado na heap property qual o 
comportamento da raiz de uma Cartesian
Tree?
5
� Baseado na heap property qual o 
comportamento da raiz de uma Cartesian
Tree?
É o menor valor da É o menor valor da É o menor valor da É o menor valor da sequênciasequênciasequênciasequência
6
� Recursivamente
� As subárvores à esquerda e a direita da raiz são 
Cartesian Trees das subsequências à esquerda 
e à direita da raiz.
� Mas o que isso significa?
7
• Raiz da 
árvore
• Menor valor 
da sequência
8
• Raiz da 
Subárvore
• Menor valor 
da 
subsequência
9
• Raiz da 
Subárvore
• Menor valor 
da 
subsequência
10
� Lembrando as propriedades ...
◦ Um nó para cada número de uma sequência
◦ Caminhar em ordem na árvore resulta na 
sequência original
� A árvore à esquerda de um nó consiste em valores 
anteriores a ele na ordem da sequência
� A árvore à direita de um nó consiste em valores 
posteriores a ele na ordem da sequência
◦ Heap property (Min)
� O pai de qualquer nó não-raiz tem um valor inferior 
que o valor de seus filhos 11
1. Se o novo nó é maior que o último inserido, 
insere-se o novo nó como filho a direitadireitadireitadireita do 
último;
◦ X – último nó inserido na árvore
◦ Y – novo nó a ser inserido
◦ Y > X
12
xxxx
yyyy
2. Caso contrário, se o pai do último inserido é 
menor ou igual ao novo nó, inserimos o novo 
como seu filho a direita e o antigo filho a direita 
dele se torna o filho a esquerda do novo nó;
◦ X – último nó inserido na árvore
◦ Z – o pai de X
◦ Y – novo nó a ser inserido
◦ Y<= X & Z <= Y
13
zzzz
xxxx
zzzz
yyyyxxxx
3. Caso contrário, verifica se o avô do último nó inserido 
é menor ou igual ao novo nó e assim por diante até 
encontrar um nó menor ou igual ao novo, inserimos o 
novo como seu filho a direita e o antigo filho a direita 
dele se torna o filho a esquerda do novo nó;
◦ X – último nó inserido na árvore
◦ Z – avô || bisavô || tataravô ... do último nó inserido
◦ Y – novo nó a ser inserido
◦ Y<= X & Z <= Y
14
zzzz
xxxx
zzzz
yyyyxxxx...
...
4. Se não encontrar nenhum nó na árvore que o novo 
nó seja menor que ele, significa que o novo nó é o 
menor nó até então e deve se tornar a raiz da 
árvore e a antiga raiz sua filha a esquerda.
◦ R – raiz da árvore
◦ Y – novo nó a ser inserido
◦ Y<= R
15
RRRR
......
RRRR
......
YYYY
9999
16
9999
3333
Se não encontrar nenhum nó na árvore Se não encontrar nenhum nó na árvore Se não encontrar nenhum nó na árvore Se não encontrar nenhum nó na árvore 
que o novo nó seja menor que ele, que o novo nó seja menor que ele, que o novo nó seja menor que ele, que o novo nó seja menor que ele, 
significa que o novo nó é o menor nó até significa que o novo nó é o menor nó até significa que o novo nó é o menor nó até significa que o novo nó é o menor nó até 
então e deve se tornar a raiz da árvore e então e deve se tornar a raiz da árvore e então e deve se tornar a raiz da árvore e então e deve se tornar a raiz da árvore e 
a antiga raiz sua filha a esquerdaa antiga raiz sua filha a esquerdaa antiga raiz sua filha a esquerdaa antiga raiz sua filha a esquerda
17
9999
3333
7777
Se o novo nó é maior que o último Se o novo nó é maior que o último Se o novo nó é maior que o último Se o novo nó é maior que o último 
inserido, insereinserido, insereinserido, insereinserido, insere----se o novo nó como se o novo nó como se o novo nó como se o novo nó como 
filho a direita do últimofilho a direita do últimofilho a direita do últimofilho a direita do último
18
9999
3333
7777
1111
Se não encontrar nenhum nó na árvore 
que o novo nó seja menor que ele, 
significa que o novo nó é o menor nó até 
então e deve se tornar a raiz da árvore e 
a antiga raiz sua filha a esquerda
19
9999
3333
7777
1111
Se o novo nó é maior que o último 
inserido, insere-se o novo nó como filho 
a direita do último
8888
20
9999
3333
7777
1111
Se o novo nó é maior que o último 
inserido, insere-se o novo nó como filho 
a direita do último
8888
12121212
21
9999
3333
7777
1111
Se o pai do último é Se o pai do último é Se o pai do último é Se o pai do último é 
menor ou igual ao novo menor ou igual ao novo menor ou igual ao novo menor ou igual ao novo 
inserimos o novo como inserimos o novo como inserimos o novo como inserimos o novo como 
seu filho a direita e o seu filho a direita e o seu filho a direita e o seu filho a direita e o 
antigo filho a direita dele antigo filho a direita dele antigo filho a direita dele antigo filho a direita dele 
se torna o filho a se torna o filho a se torna o filho a se torna o filho a 
esquerda do novo nóesquerda do novo nóesquerda do novo nóesquerda do novo nó
8888
10101010
12121212
22
9999
3333
7777
1111 Se o novo nó é maior que 
o último inserido, insere-
se o novo nó como filho a 
direita do último
8888
10101010
12121212 20202020
23
9999
3333
7777
1111 Se o pai do último é menor 
ou igual ao novo 
inserimos o novo como 
seu filho a direita e o 
antigo filho a direita dele 
se torna o filho a esquerda 
do novo nó
8888
10101010
1515151512121212
20202020
24
9999
3333
7777
1111
8888
10101010
1515151512121212
20202020
Se o novo nó é maior que 
o último inserido, insere-
se o novo nó como filho a 
direita do último
18181818
25
9999
3333
7777
1111
8888
10101010
1515151512121212
20202020 18181818
Verifica se o avô do último 
é menor ou igual ao novo 
e assim por diante até 
encontrar um nó menor ou 
igual ao novo, inserimos o 
novo como seu filho a 
direita e o antigo filho a 
direita dele se torna o filho 
a esquerda do novo nó.
5555
26
� Range minimum query
◦ Problema envolvendo consultas que buscam o valor 
mínimo de uma subsequência de uma sequência
?
27
� Range minimum query
◦ Problema envolvendo consultas que buscam o valor 
mínimo de uma subsequência de uma sequência
28
1
� Lowest common ancestor
◦ Mais baixo (em altura) ancestral comum do valor 
mais a esquerda e mais a direita de uma
subsequência
◦ LCA entre 6 e 9 é 8
3333
0000
2222
8888
3333
4444 9999
5555
6666
LCA de uma árvore binária
29
� Numa Cartesian Tree qual o Range minimum
e o Lowest common ancestor?
‣Na subsequência
(12,10,20,15)
‣RMQ(12,15) = ?
‣LCA(12,15)= ?
30
� Numa Cartesian Tree qual o Range minimum
e o Lowest common ancestor?
‣Na subsequência
(12,10,20,15)
‣RMQ(12,15) = 10
‣LCA(12,15)= 10
31
� Questoes de implementacao
◦ Como fica a implementacao de uma Cartesian Tree?
32
Podemos reusar alguma implementação anterior?
class CartesianTree<T> {
BSTNode<T> root;
}
class BSTNode<T> {
V data;
BSTNode<T> left;
BSTNode<T> right;
BSTNode<T> parent;
}
Precisamos de algum outro dado?
� Questoes de implementacao
◦ Como fica a implementacao de uma Cartesian Tree?
33
classCartesianTree<T> extends
BSTImpl{
BSTNode<T> root;
ArrayList sequence;
}
class BSTNode<T> {
V data;
BSTNode<T> left;
BSTNode<T> right;
BSTNode<T> parent;
}
� Implementar uma Cartesian Tree e 
determinar o LCA de uma subsequencia de 
uma sequencia dada.
34
� http://community.topcoder.com/tc?module=
Static&d1=tutorials&d2=lowestCommonAnce
stor
� http://wcipeg.com/wiki/Cartesian_tree
35