Existe uma estrutura de árvore binária com acesso rápido aos elementos acessados ​​recentemente e a pior complexidade ?

A idéia das árvores de exibição é muito boa, pois elas movem elementos acessados ​​com frequência para o topo, o que pode aumentar consideravelmente a velocidade em muitos aplicativos. A desvantagem é que, na pior das hipóteses, uma operação pode ter complexidade . (Embora os limites amortizados sejam se realizarmos pelo menos operações .)$O(n)$$O(n\log n)$ $n$

Existe uma estrutura de árvore de pesquisa autoajustável que possui ambos? Favorecendo elementos acessados ​​recentemente e com pior complexidade de para uma única operação?$O(\log n)$

Parece que você está procurando uma árvore de pesquisa binária com a propriedade do conjunto de trabalho ; isso é um pouco mais fraco que a otimização dinâmica . De fato, não existem árvores de pesquisa binária conhecidas com otimização dinâmica, de acordo com "Em busca da conjectura de otimização dinâmica" de Iacono, de junho de 2013 .

Mas, se você está procurando a propriedade mais simples do conjunto de trabalho, está com sorte! A propriedade do conjunto de trabalho é que o tempo para acessar um item$x$ é proporcional ao log do número de itens acessados ​​desde $x$ foi acessado pela última vez.

Há uma variedade de estruturas com a propriedade do conjunto de trabalho. Existe até uma árvore binária que atende ao limite logarítmico do pior caso e à propriedade do conjunto de trabalho no pior caso, não apenas ao caso amortizado: "Árvores em camadas do conjunto de trabalho" de Bose et al .

O custo amortizado de inserir um elemento na árvore de exibição é $O(\log n)$ no pior dos casos $n$ operações faria $O(n\log n)$passos. Existe uma conjectura sobre a árvore splay que diz que ela é tão ideal quanto uma árvore de pesquisa binária até um fator constante chamado conjectura de otimização dinâmica .

As árvores de tango estão online, árvores adjacentes que atingem$O(\log \log n)$ relação competitiva em comparação com a árvore de pesquisa binária ideal offline, que é a mais conhecida.

Não tenho muita certeza do que você deseja alcançar com sua estrutura de dados. De fato, as árvores de jogo são uma estrutura de dados interessante. Eles são conhecidos por terem a propriedade de otimização estática . Isso significa que, se você conhece a distribuição das consultas de pesquisa com antecedência e constrói a árvore de pesquisa binária ideal para essa distribuição, uma árvore de reprodução (sem conhecer a distribuição) terá um desempenho assintoticamente tão bom quanto a árvore de pesquisa binária. Obviamente, você pode dizer que isso é trapaça, pois a árvore de pesquisa binária não pode ser reajustada, mas ainda é uma propriedade muito impressionante. As pessoas também esperam que as árvores dispersas sejam tão boas quanto qualquer estrutura de dados autoajustável (conhecida como conjectura dinâmica ideal ) - mas essa é uma das questões em aberto mais proeminentes na área de estruturas de dados.

Voltando à sua pergunta, como as árvores de estacas são estaticamente ótimas, você precisa sacrificar alguma coisa. Isso significa que, se você acessar um elemento com baixa probabilidade, poderá ter que executar uma operação mais expansiva. No entanto, isso se justifica, pois o elemento raramente é solicitado - e toda estrutura de dados ótima estática mostrará esse comportamento. É claro que você sempre pode usar uma árvore de pesquisa binária equilibrada, mas perde a otimização estática.

Que tal esse procedimento (funciona apenas para BSTs estáticos).

Em cada nó, você mantém um ponteiro para outro nó, que existe na subárvore enraizada nesse nó. Junto com o ponteiro, você também mantém o número do nível do nó que está sendo apontado (junto com o número do seu nível). A raiz está no nível 0 e os níveis aumentam à medida que você desce pela árvore. Inicialmente, o ponteiro de um nó aponta para o próprio nó. A invariante é que você sempre apontará para um nó em um nível inferior ou igual ao número do nível do nó.

Quando você procura um elemento na árvore, ele:

1. Be found at its location in the BST, or
2. Be found along a path to its location because some node along the node to root path has a pointer to this node, or
3. Not be found at all.

Em ambos os casos, primeiro fazemos um encaminhamento para encontrar o nó e, se for encontrado, fazemos bolhas nos nós apontados ao longo do caminho raiz para o nó do nó encontrado. Se o nó foi encontrado como resultado do caso-2, apenas fazemos bolhas até o nó que estava apontando para o nó de destino (isso nos permite ser rápidos nos nós acessados ​​recentemente).

Se um nó for alterado para um nível maior que o próprio, excluímos o nó do conjunto de mapeamento.

Se um nó que não possui mapeamento for acessado, criamos um novo mapeamento para esse nó e o configuramos para substituir o mapeamento existente no nó e realizamos a bolha progressivamente.

Quando um nó é acessado, ele é borbulhado até o topo.