Função potencial da árvore Splay: por que somar os logs dos tamanhos?

16

Estou ministrando um curso sobre estruturas de dados e abordarei as árvores espalhadas no início da próxima semana. Já li o artigo sobre árvores abertas e estou familiarizado com a análise e intuição por trás da estrutura de dados. No entanto, não consigo encontrar uma intuição sólida para a função potencial que Sleator e Tarjan usam em suas análises.

A análise funciona atribuindo a cada elemento da árvore um peso arbitrário , em seguida, configurando o tamanho s ( x ) de um nó como a soma dos pesos dos nós na subárvore com raiz em x . Eles então pegam o log desse valor para obter a classificação r ( x ) do nó, então r ( x ) = log s ( x ) . Finalmente, a função potencial da árvore é definida como a soma das classificações de todos os nós.WEus(x)xr(x)r(x)=registros(x)

Entendo que essa função potencial funciona corretamente e posso acompanhar a análise, mas não vejo por que eles escolheriam esse potencial. A ideia de atribuir um tamanho a cada nó faz sentido para mim, pois se você resumir os tamanhos, obterá o comprimento do caminho ponderado da árvore. No entanto, não consigo entender por que eles decidiram pegar os toros dos pesos e, em seguida, resumir esses pesos - não vejo nenhuma propriedade natural da árvore a que isso corresponda.

A função potencial da árvore espalhada corresponde a alguma propriedade natural da árvore? Existe uma razão específica, além de "funciona", que eles escolheriam esse potencial? (Estou especificamente curioso, porque esse conjunto de anotações menciona que a "análise é magia negra. [Não] faço ideia de como foi descoberta")

Obrigado!

templatetypedef
fonte
Já ouvi essa explicação de "é magia negra" antes. Você tentou enviar um email para o Sleator e Tarjan?
Jbapple 26/04
@jbapple Eu ainda não os enviei por e-mail, pois esperava que "a comunidade em geral" pudesse ajudar. Também imaginei que fazer ping em alguém sobre o trabalho que eles fizeram 30 anos atrás pode não necessariamente provocar uma resposta. :-)
templatetypedef
Eu não estou muito familiarizado com isso, mas apenas olho o artigo de forma mais aproximada, acho que a única razão é que eles querem fazer pequenas alterações nas funções em potencial após a operação splay, por exemplo, se substituirmos o pelo log de log ou por l o g * parece ainda tudo funciona bem (eu não prová-lo, mas parece só precisa de um mathwork simples). Porém, se deixarmos como s , a amortização será analisada enquanto estiver correta, mas não é um bom limite superior (algo como ( m + n ) 2 ). Não está relacionado a nenhuma propriedade da árvore. registroregistroregistroeuogs(m+n)2
Saeed
Eu sempre coloquei na caixa preta a classificação de x como "a profundidade da árvore de pesquisa binária ideal que contém os descendentes de x", mas isso é mais uma intuição mnemônica do que útil.
Jeffε

Respostas:

13

Como criar um potencial de soma de logs

Vamos considerar o algoritmo BST que, para cada acesso ao elemento x , ele reorganiza apenas elementos no caminho de pesquisa P de x chamado before-path, em alguma árvore chamada after-tree. Para qualquer elemento a , sejam s ( a ) e s ( a ) o tamanho da subárvore enraizada em um antes e depois do rearranjo, respectivamente. Assim s ( um ) e s ' ( um ) podem diferir sse um P .UMAxPxumas(uma)s(uma)umas(uma)s(uma)umaP

Além disso, UMA apenas reorganiza constantemente muitos elementos no caminho de pesquisa a qualquer momento. Vamos chamar esse tipo de algoritmo de algoritmo "local". Por exemplo, a árvore splay é local. Reorganiza apenas no máximo 3 elementos por vez em zig, zigzig e zig-zag.

Agora, qualquer algoritmo local que crie "muitas" folhas na árvore posterior, como a árvore splay, tem a seguinte propriedade legal.

Podemos criar um mapeamento tal quef:PP

  1. Existem linearmente muitos , onde s ( f ( a ) ) s ( a ) / 2 .umaPs(f(uma))s(uma)/2
  2. Há constantemente muitos , onde s ( f ( a ) ) pode ser grande, mas trivialmente no máximo n .umaPs(f(uma))n
  3. Outros elementos , s ( f ( a ) ) s ( a ) .umaPs(f(uma))s(uma)

Podemos ver isso desdobrando a mudança do caminho da pesquisa. O mapeamento é realmente bastante natural. Este artigo, Uma visão geométrica global da distribuição , mostra precisamente os detalhes de como ver a observação acima.

Depois de conhecer esse fato, é muito natural escolher o potencial da soma de logs. Porque podemos usar a alteração potencial dos elementos do tipo 1 para pagar todo o rearranjo. Além disso, para elementos de outro tipo, temos que pagar pela alteração potencial no máximo logarítmica. Portanto, podemos derivar o custo amortizado do logaritmo.

Acho que a razão pela qual as pessoas pensam que isso é "magia negra" é que a análise anterior não "desdobra" a mudança geral do caminho de pesquisa e vê o que realmente acontece em uma única etapa. Em vez disso, eles mostram a mudança de potencial para cada "transformação local" e mostram que essas mudanças em potencial podem ser magicamente telescópicas.

PS O artigo ainda mostra algumas limitações do potencial da soma de logs. Ou seja, pode-se provar a satisfação do lema do acesso via potencial soma-de-logs apenas para o algoritmo local.

Interpretação do potencial da soma dos logs

Existe outra maneira de definir o potencial do BST no artigo de Georgakopoulos e McClurkin, que é essencialmente o mesmo que o potencial da soma de logs no artigo de Sleator Tarjan. Mas isso me dá uma boa intuição.

Agora mudo para a notação do papel. Atribuímos um peso a cada nó u . Seja W ( u ) a soma do peso da subárvore de u . (Esse é apenas o tamanho da subárvore de u quando o peso de cada nó é um.)W(você)vocêW(você)vocêvocê

Agora, em vez de definir a classificação nos nós, definimos a classificação nas arestas, que eles chamaram de fator de progresso .

pf(e)=registro(W(você)/W(v)).

E o potencial da árvore éS

Φ(S)=eSpf(e).

Esse potencial tem uma interpretação natural: se durante uma pesquisa atravessamos uma aresta (você,v) , reduzimos o espaço de pesquisa dos descendentes de para os descendentes de v , uma redução franca de W ( u ) / W ( v ) . Nosso fator de progresso é uma medida logarítmica desse 'progresso', daí seu nome. [Da seção 2.4]vocêvW(você)/W(v)

Observe que esse é quase o potencial do Sleator Tarjan e é aditivo nos caminhos.

editar: Acontece que essa definição alternativa e a intuição por trás dela foram descritas há muito tempo por Kurt Mehlhorn. Veja seu livro "Estruturas de dados e algoritmos" Volume I, Seção III. 6.1.2 Árvores de exibição, páginas 263 - 274.

Thatchaphol
fonte