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.$w_i$$s(x)$$x$$r(x)$$r(x) = \log s(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!

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 .$A$$x$$P$$x$$a$$s(a)$$s'(a)$$a$$s(a)$$s'(a)$$a \in P$

Além disso, $A$ 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 que$f: P \rightarrow P$

1. Existem linearmente muitos , onde s ′ ( f ( a ) ) ≤ s ( a ) / 2 .$a \in P$$s'(f(a)) \le s(a)/2$
2. Há constantemente muitos , onde s ′ ( f ( a ) ) pode ser grande, mas trivialmente no máximo n .$a \in P$$s'(f(a))$$n$
3. Outros elementos , s ′ ( f ( a ) ) ≤ s ( a ) .$a \in P$$s'(f(a)) \le s(a)$

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(u)$$u$$W(u)$$u$$u$

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

E o potencial da árvore é$S$

Esse potencial tem uma interpretação natural: se durante uma pesquisa atravessamos uma aresta $(u,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]$u$$v$$W(u)/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.