Diferença entre um LinkedList e uma árvore binária Pesquisa

https://stackoverflow.com/questions/270080

06-07-2019
|

Pergunta

Quais são as principais diferenças entre uma lista encadeada e uma BinarySearchTree? BST é apenas uma maneira de manter um LinkedList? Meu instrutor falou sobre LinkedList e depois BST mas did't compará-los ou não disse quando a preferir um sobre o outro. Esta é provavelmente uma pergunta idiota, mas eu estou realmente confuso. Agradecia que se alguém pode esclarecer isso de uma forma simples.

Solução

lista vinculada:

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

Binary árvore:

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

Em uma lista ligada, os itens estão ligados entre si através de um único ponteiro próximo. Em uma árvore binária, cada nó pode ter 0, 1 ou 2 subnós, onde (no caso de uma árvore de busca binária) a chave do nó esquerda é menor do que a chave do nó ea chave do nó direito é mais do que o nó. Enquanto a árvore é equilibrada, a SearchPath para cada item é muito mais curto do que em uma lista ligada.

searchpaths:

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

Por estruturas maiores do caminho de pesquisa média torna-se significativa menor:

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------

Outras dicas

A Binary Pesquisa Árvore é uma árvore binária em que cada nó interno x armazena um elemento de tal forma que o elemento armazenado na subárvore esquerda de x são menos do que ou igual a x e elementos armazenados na subárvore direita de x são maiores do que ou igual a x .

Agora, um Linked Lista consiste de uma sequência de nós, cada um contendo valores arbitrários e uma ou duas referências que apontam para os próximos e / ou nodos anteriores.

Em ciência da computação, um busca binária árvore (BST) é uma estrutura de dados árvore binária que tem as seguintes propriedades:

cada nó (item na árvore) tem um valor distinto;
tanto a esquerda e para a sub-árvores direito também deve ser árvores de busca binária;
subárvore esquerda de um nó contém apenas valores menores que o valor do nó;
subárvore direita de um nó só contém valores maior ou igual ao valor do nó.

Em ciência da computação, um ligada lista é uma das estruturas de dados fundamentais, e pode ser usado para implementar outras estruturas de dados.

Assim, uma árvore binária de busca é um conceito abstrato que pode ser implementada com uma lista ligada ou um array. Enquanto a lista ligada é uma estrutura de dados fundamental.

Eu diria que a principal diferença é que uma árvore de busca binária está classificada. Quando você insere em uma árvore de busca binária, onde esses elementos acabar sendo armazenado na memória é uma função do seu valor. Com uma lista ligada, os elementos são cegamente adicionado à lista, independentemente do seu valor.

imediatamente você pode alguns trade-offs: listas ligadas preservar a ordem de inserção e de inserção é menos caro Árvores binárias de pesquisa são geralmente mais rápido para procurar

A vinculado lista é um número sequencial de "nós" ligadas entre si, ou seja:

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

A pesquisa binária árvore usa uma estrutura de nó semelhantes, mas em vez de ligar para o próximo nó, liga-se dois nós filhos:

public class BSTNode
{
    Object Data
    BSTNode LeftNode;
    BSTNode RightNode;
}

Ao seguir regras específicas ao adicionar novos nós a um BST, você pode criar uma estrutura de dados que é muito rápido para atravessar. Outras respostas aqui ter detalhado essas regras, eu só queria mostrar ao nível do código a diferença entre classes nó.

É importante notar que, se você inserir dados classificados em uma BST, você vai acabar com uma lista ligada, e você perde a vantagem de usar uma árvore.

Devido a isso, uma ListaLigada é um O (N) de estrutura de dados de passagem, ao passo que um BST é um O (N) estrutura de dados de percurso, no pior caso, e um grupo O (log N) na melhor das hipóteses.

As listas vinculadas e BSTs realmente não têm muito em comum, exceto que ambos são estruturas de dados que atuam como recipientes. Listas ligadas basicamente permitem que você inserir e elementos remover eficazmente em qualquer local na lista, mantendo a ordem da lista. Esta lista é implementado usando ponteiros de um elemento para a próxima (e muitas vezes o anterior).

A binário árvore de pesquisa por outro lado é uma dados estrutura de uma abstração mais elevado (ou seja, não está especificado como isso é implementado internamente) que permite pesquisas eficientes (ou seja, a fim de encontrar um elemento específico que você não tem que olhar para todos os elementos.

Observe que uma lista ligada pode ser pensado como um degenerado árvore binária, árvore ou seja, um em que todos os nós têm apenas um filho.

É realmente muito simples. Uma lista ligada é apenas um monte de itens encadeados, em nenhuma ordem particular. Você pode pensar nisso como uma árvore muito magro, que nunca ramos:

1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (esse último é uma tentativa ascii-art em um nulo de terminação)

A pesquisa binária árvore é diferente de 2 maneiras: os meios parte binária que cada nó possui 2 crianças, não um, e os meios de Pesquisa de que as crianças estão dispostas para acelerar as pesquisas - única pequenos itens para a esquerda, e aqueles única maiores para a direita:

9 tem nenhuma criança à esquerda, e 1, 2, e 12 "folhas" -. Eles não têm filiais

faz sentido?

Para a maioria dos tipos "de pesquisa" de utilizações, o BST é melhor. Mas por apenas "manter uma lista de coisas para lidar com mais tarde Últimos-In-First-Out First-In-First-Out ou" tipos de coisas, uma lista ligada pode funcionar bem.

O problema com uma lista ligada é pesquisar dentro dele (seja para recuperação ou inserção).

Para obter uma lista única ligada, você tem que começar na cabeça e procurar sequencialmente para encontrar o elemento desejado. Para evitar a necessidade de digitalizar toda a lista, você precisa de referências adicionais para nós dentro da lista, caso em que, ele não é mais um simples ligada lista.

A árvore binária permite a busca mais rápida e inserção por ser intrinsecamente ordenadas e navegável.

Uma alternativa que eu tenho utilizado com sucesso no passado é uma SkipList. Isso proporciona algo semelhante a uma lista ligada, mas com referências extras para permitir o desempenho da pesquisa comparável a uma árvore binária.

Uma lista ligada é apenas isso ... uma lista. É linear; cada nó tem uma referência para o próximo nó (e do anterior, se você está falando de uma lista duplamente vinculada). A galhos de árvores --- cada nó tem uma referência para vários nós filho. Uma árvore binária é um caso especial em que cada nó tem apenas dois filhos. Assim, em uma lista ligada, cada nó tem um nó anterior e um nó seguinte, e em uma árvore binária, um nó tem um filho esquerdo, direito da criança e dos pais.

Estas relações podem ser bi-direcional ou unidirecional, dependendo de como você precisa ser capaz de atravessar a estrutura.

Eles têm semelhanças, mas a principal diferença é que uma pesquisa binária árvore é projetado para suportar uma pesquisa eficiente para um elemento, ou "chave".

A árvore de busca binária, como uma lista duplamente vinculada, aponta para dois outros elementos da estrutura. No entanto, ao adicionar elementos à estrutura, ao invés de apenas acrescentando-as ao final da lista, a árvore binária é reorganizada de modo que elementos ligados ao nó "esquerda" são menos do que o nó atual e elementos ligados ao "direito" nó são maiores do que o nó atual.

Em uma implementação simples, o novo elemento é comparado com o primeiro elemento da estrutura (a raiz da árvore). Se for menos, o ramo "esquerda" é tomada, caso contrário, o ramo "direito" é examinado. Isto continua com cada nó, até que um ramo é encontrado para estar vazia; o novo elemento preenche essa posição.

Com esta abordagem simples, se os elementos são adicionados em ordem, você acaba com uma lista ligada (com o mesmo desempenho). Existem diferentes algoritmos para manter alguma medida de equilíbrio na árvore, reorganizando os nós. Por exemplo, árvores AVL fazer mais trabalho para manter a árvore mais equilibrada possível, dando os melhores tempos de busca. árvores rubro-negro não manter a árvore como equilibrada, resultando em pesquisas um pouco mais lentas, mas fazer menos trabalho, em média, como as chaves são inseridas ou removidas.

Linked Lista é dados lineares rectas com os nós adjacentes ligadas umas com as outras, por exemplo, A-> B> C. Você pode considerá-lo como uma cerca em linha reta.

BST é uma estrutura hierárquica como uma árvore com o tronco principal ligado a ramos e os ramos em-sua vez ligado a outros ramos e assim por diante. A palavra "binária" aqui significa cada ramo é conectado a um máximo de dois ramos.

Você usa lista ligada para representar dados diretamente apenas com cada item ligado a um máximo de um item; ao passo que você pode usar BST para conectar um item para dois itens. Você pode usar BST para representar um conjunto de dados, como a árvore de família, mas que vai se tornar árvore de busca n-ary como não pode haver mais do que dois filhos para cada pessoa.

A árvore de busca binária pode ser implementado de qualquer forma, ele não precisa de usar uma lista ligada.

A vinculado lista é simplesmente uma estrutura que contém nós e ponteiros / referências a outros nós dentro de um nó. Dado o nó principal de uma lista, você pode navegar para qualquer outro nó em uma lista ligada. listas duplamente ligadas tem dois ponteiros / referências: a referência normais para o próximo nó, mas também uma referência ao nó anterior. Se o último nó em um referências lista duplamente ligados o primeiro nó na lista como o próximo nó, e as primeiras referências de nós o último nó como nó anterior, diz-se ser uma lista circular.

A árvore de busca binária é uma árvore que se divide sua entrada em duas metades aproximadamente iguais, com base em um algoritmo de comparação de busca binária. Assim, ele só precisa de muito poucas pesquisas para encontrar um elemento. Por exemplo, se você tivesse uma árvore com 1-10 e você necessário para procurar três, primeiro o elemento no topo seria verificado, provavelmente a 5 ou 6. Três seria menos do que isso, portanto, apenas a primeira metade do árvore, então, ser marcada. Se o próximo valor é 3, você tem que, de outra forma, a comparação é feita, etc, até que ele não é encontrado ou seus dados são devolvidos. Assim, a árvore é rápido para pesquisa, mas não nessecarily rápido para inserção ou exclusão. Estes são descrições muito ásperas.

Linked Lista da wikipedia, e Binary Pesquisa Árvore , também da wikipedia.

Eles são estruturas de dados totalmente diferentes.

Uma lista ligada é uma sequência de elemento, em que cada elemento está ligado a próxima, e, no caso de uma lista duplamente ligado, que o anterior.

A árvore de busca binária é algo totalmente diferente. Ele tem um nó raiz, o nó raiz tem até dois nós filhos, e cada nó filho pode ter até duas notas criança etc etc. É uma estrutura de dados muito inteligente, mas seria um pouco tedioso para explicá-lo aqui. Confira o Wikipedia artcle nele.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow