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).
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 tamanho) 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.
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.
Eu entendi mal alguma coisa? A inicialização de uma árvore de corte de link pode ser feita no tempo ?
fonte