Qual é o tempo de inicialização de uma árvore de corte de link?

8

A árvore de corte de link é uma estrutura de dados inventada pelo Sleator e Tarjan, que suporta várias operações e consultas em umafloresta de nós no tempo. (Por exemplo, o link de operaçãocombina duas árvores na floresta em uma, enquanto a operação cortada divide uma árvore na floresta em duas).nO(registron)

Várias aplicações são conhecidas pelo uso de árvores cortadas por link, e aqui estou particularmente interessado na decomposição do separador de Goodrich , que, dado um gráfico de plano nó é possível obter uma árvore binária correspondente em que os nós são subgráficos de e os filhos de um nó são os subgráficos de dividido pelo separador em . Essa decomposição pode ser facilmente construída no tempo (já que um separador pode ser encontrado no tempo , e como o separador divide o gráfico de maneira equilibrada, após o nível de separações as folhas da árvore são do tamanhonGGHHHO(nregistron)O(n)O(registron)O(1)) A principal contribuição de Goodrich é que ele pode construir essa decomposição no tempo , mantendo e reutilizando as estruturas de dados usadas para encontrar separadores em cada nível.O(n)

Uma das estruturas de dados usadas na construção é realmente a árvore de corte de link. Na página 7 do artigo de Goodrich, ele afirmou que a inicialização da árvore de corte de link pode ser feita no tempo . Enquanto eu passo por todos os artigos citados lá, parece-me que, se construirmos uma árvore cortada por link via link de operação , leva tempo no total.O(n)O(nregistron)

Eu entendi mal alguma coisa? A inicialização de uma árvore de corte de link pode ser feita no tempo ?O(n)

Hsien-Chih Chang 張顯 之
fonte

Respostas:

6

Muito obrigado a Hsueh-I Lu , meu professor na Universidade Nacional de Taiwan, que fornece a seguinte solução.

Acontece que a resposta é bastante simples; na inicialização de uma estrutura de dados, não precisamos construir a estrutura pelas consultas e operações que ela suporta . Obviamente, não podemos executar consultas durante a construção, como costumamos fazer se construirmos a árvore por operação de link ; mas nesta aplicação de decomposição separadora, não precisamos dela.

Ou seja, na aplicação à decomposição do separador, quando temos que construir as árvores cortadas por links L (T) para a árvore de abrangência T no gráfico de entrada G, em vez de calcular as estruturas e os valores das árvores L (T ) por operação de link , calculamos diretamente a decomposição do caminho de luz pesada da árvore T e construímos a estrutura de árvore binária correspondente para cada caminho e colamos as árvores binárias de acordo com a decomposição do caminho. Todas as etapas podem ser realizadas em tempo linear.

Para cada valor necessário nos nós de L (T), já que cada valor pode ser calculado a partir de T em tempo linear (nesta aplicação), em vez de atribuir valores em estruturas de árvores binárias e atualizar ao colar as árvores, atribuímos os valores pré-computados diretamente nos nós das árvores finais cortadas por elos L (T). Há apenas um tipo constante de valores que precisam ser atribuídos e, novamente, isso pode ser feito em tempo linear.

Hsien-Chih Chang 張顯 之
fonte
0

Capítulo 5.1 em "Estruturas de Dados e Algoritmos de Rede", que é ref. 43 no artigo que você citou, parece que pode ter a resposta:

http://books.google.com/books?id=JiC7mIqg-X4C&lpg=PP1&ots=8frbjj8vL0&dq=data%20structures%20and%20network%20algorithms&pg=PA59#v=onepage&q&f=false

... Ao discutir este problema, usaremos 'm' para indicar o número de operações e 'n' para indicar o número de vértices (operações com maketree). Uma maneira de resolver esse problema é armazenar com cada vértice seu pai e seu custo. Com essa representação, cada operação de mareeree, link ou corte leva tempo O (1), e cada operação findroot, findcost ou addcost leva tempo proporcional à profundidade do vértice de entrada, que é O (n) ...

Várias páginas mais sucessivas estão disponíveis na visualização.

s8soj3o289
fonte
Este capítulo é muito parecido com o próprio papel de árvore cortado; ver os três últimos parágrafo em p.365 de citeseerx.ist.psu.edu/viewdoc/...
Hsien-Chih Chang張顯之
O(n)O(registron)
não consegui encontrar outras informações para fazer backup dessa reivindicação, então acho que elas devem ser: a. referindo-se a essa construção "ingênua" (talvez por engano), b. referindo-se à operação 'make_tree' que simplesmente inicializa uma nova árvore de um nó, ou talvez c. confluindo os dois. caso contrário, salvo provas adicionais, estou inclinado a pensar que você está correto.
s8soj3o289