Diferença entre árvore binária e árvore de pesquisa binária

Respostas:

566

Árvore binária: Árvore em que cada nó tem até duas folhas

  1
 / \
2   3

Árvore de pesquisa binária: usada para pesquisa . Uma árvore binária em que o filho esquerdo contém apenas nós com valores menores que o nó pai e onde o filho direito contém apenas nós com valores maiores ou iguais ao pai.

  2
 / \
1   3
user541686
fonte
14
@pete: É uma coisa conceitual, você nunca necessariamente criará uma que seja completamente irrestrita. No entanto, existem muitas árvores binárias que não são de pesquisa que são especiais de alguma outra maneira, por exemplo, pilhas binárias.
user541686
19
@pete birary trees não precisam necessariamente conter dados comparáveis, muitas árvores binárias (sem pesquisa) são usadas para analisar expressões algébricas, a árvore binária é perfeita para escrever um analisador de notação de infixo, colocando o operador como nó (s) e valores numéricos como folhas
JBoy 27/05
2
@JBoy: Eles não serão árvores binárias nesse caso. (por exemplo, operadores unários não podem ter dois filhos.) Realmente não consigo pensar em um caso de uso prático para árvores binárias irrestritas, por isso fiz esse comentário.
user541686
2
Ótimo e simples. +1 para exemplo visual :) #
Andrei Konstantinov
@Mehrdad Uma árvore binária tem um ou dois filhos por nó. As árvores de expressão são um exemplo perfeito. Uma árvore de pesquisa binária também possui um ou dois filhos por nó, a menos que esteja cheio, o que só pode acontecer com certos números de elementos.
Marquês de Lorne
56

Árvore binária é uma forma especializada de árvore com dois filhos (filho esquerdo e filho direito). É simplesmente representação de dados na estrutura em árvore

A Árvore de Pesquisa Binária (BST) é um tipo especial de Árvore Binária que segue a seguinte condição:

  1. nó filho esquerdo é menor que seu nó pai
  2. nó filho direito é maior que seu nó pai
Jayzcode
fonte
23
Essas condições não são suficientes. A subárvore esquerda inteira não deve conter chaves apenas menos que as do pai e a subárvore direita inteira deve conter nós maiores.
Marquês de Lorne
1
@EJP, você pode elaborar seu comentário, por favor? o que você quer dizer com subárvore inteira? quer dizer que todos os valores da subárvore devem ser menores do que enraizar no lado esquerdo? e todos os valores devem ser maiores que o valor raiz no lado direito?
Asif Mushtaq
Após o segundo link, leia a seção "Verificação" e ela ficará clara.
Rob
38

Uma árvore binária é composta de nós, onde cada nó contém um ponteiro "esquerdo", um ponteiro "direito" e um elemento de dados. O ponteiro "raiz" aponta para o nó mais alto da árvore. Os ponteiros esquerdo e direito apontam recursivamente para "subárvores" menores em ambos os lados. Um ponteiro nulo representa uma árvore binária sem elementos - a árvore vazia. A definição recursiva formal é: uma árvore binária está vazia (representada por um ponteiro nulo) ou é composta de um único nó, onde os ponteiros esquerdo e direito (definição recursiva à frente) apontam para uma árvore binária.

Uma árvore de pesquisa binária (BST) ou "árvore binária ordenada" é um tipo de árvore binária em que os nós são organizados em ordem: para cada nó, todos os elementos em sua subárvore esquerda são menos para o nó (<) e todos os elementos em sua subárvore direita, são maiores que o nó (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

A árvore mostrada acima é uma árvore de pesquisa binária - o nó "raiz" é 5 e seus nós de subárvore esquerdo (1, 3, 4) são <5 e seus nós de subárvore direito (6, 9) são> 5. Recursivamente, cada uma das subárvores também deve obedecer à restrição da árvore de pesquisa binária: na subárvore (1, 3, 4), o 3 é a raiz, o 1 <3 e 4> 3.

Cuidado com as palavras exatas dos problemas - uma "árvore de pesquisa binária" é diferente de uma "árvore binária".

Emmanuel Oddy
fonte
@GabrielStaples Estrutura de árvore adicionada.
Gaurav Borole 8/17
14

Como todo mundo acima explicou sobre a diferença entre a árvore binária e a árvore de pesquisa binária, estou apenas adicionando como testar se a árvore binária fornecida é uma árvore de pesquisa binária.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

Espero que ajude você. Desculpe se estou me afastando do tópico, pois senti que vale a pena mencionar isso aqui.

Tentando
fonte
1
A subárvore esquerda ou direita pode estar vazia. Seu código não trata esse caso corretamente.
Marquês de Lorne
11

Árvore binária representa uma estrutura de dados composta por nós que podem ter apenas duas referências filhos .

A Árvore de Pesquisa Binária ( BST ), por outro lado, é uma forma especial da estrutura de dados da Árvore Binária , na qual cada tem um valor comparável e filhos de menor valor anexados a filhos de esquerda e maiores, à direita.

Portanto, todas as BSTs são Árvore Binária, no entanto, apenas algumas delas também podem ser BST . Notifique que o BST é um subconjunto da Árvore binária .

Portanto, a Árvore Binária é mais uma estrutura de dados geral do que a Árvore de Pesquisa Binária . E também é necessário notificar que a Árvore de pesquisa binária é uma árvore classificada , enquanto não existe um conjunto de regras para essa árvore .

Árvore binária

A Binary Treeque não é a BST;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

Árvore de pesquisa binária (árvore classificada)

Uma Árvore de Pesquisa Binária que também é uma Árvore Binária ;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

Propriedade Nó da Árvore de Pesquisa Binária

Notifique também que, para qualquer nó pai no BST ;

  • Todos os nós esquerdos têm um valor menor que o valor do nó pai. No exemplo superior, os nós com valores {20, 25, 30}, todos localizados à esquerda ( descendentes à esquerda ) de 50, são menores que 50.

  • Todos os nós certos têm um valor maior que o valor do nó pai. No exemplo superior, os nós com valores {70, 75, 80}, todos localizados à direita ( descendentes à direita ) de 50, são maiores que 50.

Não existe uma regra para o Nó da Árvore Binária . A única regra para o Nó da Árvore Binária é ter dois filhos, por isso ela se auto-explica por que se chama binário .

Levent Divilioglu
fonte
Podemos implementar a árvore binária simples? existe alguma implementação disponível? e qual é o uso dessa árvore?
Asif Mushtaq
@UnKnown Você pode usar a Árvore de Pesquisa Binária para classificar e pesquisar. Você pode encontrar a implementação de pesquisa binária árvore aqui: github.com/bzdgn/data-structures-in-java/blob/master/src/...
Levent Divilioglu
Eu sei disso, mas existe alguma árvore simples ou árvore binária simples? ou alguma implementação da Árvore Binária Simples?
Asif Mushtaq 04/04
Não há sentido em usá-lo, mas você pode adicionar instâncias arbitrárias do Nó à raiz e aos filhos.
Levent Divilioglu 04/04
10

Uma árvore de pesquisa binária é um tipo especial de árvore binária que exibe a seguinte propriedade: para qualquer nó n, o valor de cada nó descendente na subárvore esquerda de n é menor que o valor de n, e o valor de cada nó descendente na subárvore direita é maior que o valor de n.

Kaushik Lele
fonte
8

Árvore binária

Árvore binária pode ser qualquer coisa que tenha 2 filhos e 1 pai. Pode ser implementado como lista ou matriz vinculada ou com sua API personalizada. Quando você começa a adicionar regras mais específicas, torna-se uma árvore mais especializada . A implementação conhecida mais comum é que, adicione nós menores à esquerda e outros maiores à direita.

Por exemplo, uma árvore binária rotulada de tamanho 9 e altura 3, com um nó raiz cujo valor é 2. A árvore é desequilibrada e não classificada . https://en.wikipedia.org/wiki/Binary_tree

insira a descrição da imagem aqui

Por exemplo, na árvore à esquerda, A tem os 6 filhos {B, C, D, E, F, G}. Pode ser convertido na árvore binária à direita.

insira a descrição da imagem aqui

Pesquisa binária

Pesquisa binária é uma técnica / algoritmo que é usado para encontrar itens específicos na cadeia de nós. A pesquisa binária funciona em matrizes classificadas .

A pesquisa binária compara o valor alvo ao elemento do meio da matriz; se forem desiguais, a metade na qual o alvo não pode estar é eliminada e a pesquisa continua na metade restante até que seja bem-sucedida ou a metade restante esteja vazia. https://en.wikipedia.org/wiki/Binary_search_algorithm

insira a descrição da imagem aqui

Uma árvore que representa a pesquisa binária . A matriz que está sendo pesquisada aqui é [20, 30, 40, 50, 90, 100] e o valor alvo é 40.

insira a descrição da imagem aqui

Árvore de pesquisa binária

Esta é uma das implementações da árvore binária. Isso é especializado para pesquisa .

A árvore de pesquisa binária e as estruturas de dados da árvore B são baseadas na pesquisa binária .

As árvores de pesquisa binária (BST), às vezes chamadas de árvores binárias ordenadas ou classificadas, são um tipo específico de contêiner : estruturas de dados que armazenam "itens" (como números, nomes etc.) na memória. https://en.wikipedia.org/wiki/Binary_search_tree

Uma árvore de pesquisa binária de tamanho 9 e profundidade 3, com 8 na raiz. As folhas não são desenhadas.

insira a descrição da imagem aqui

E finalmente um ótimo esquema para comparação de desempenho de estruturas de dados e algoritmos conhecidos aplicados:

insira a descrição da imagem aqui

Imagem tirada de Algoritmos (4ª Edição)

Teoman shipahi
fonte
4

Uma árvore binária é uma árvore cujos filhos nunca têm mais que dois. Uma árvore de pesquisa binária segue a invariante de que o filho esquerdo deve ter um valor menor que a chave do nó raiz, enquanto o filho direito deve ter um valor maior que a chave do nó raiz.

nana yaah
fonte
4
  • Árvore de pesquisa binária: quando a travessia de pedidos é feita na árvore binária, você obtém valores classificados dos itens inseridos
  • Árvore binária: nenhuma ordem classificada é encontrada em qualquer tipo de passagem
AlienOnEarth
fonte
Nenhuma ordem classificada precisa ser encontrada. Uma árvore de pesquisa binária também é uma árvore binária. Eles não são mutuamente exclusivos. O BST é um subconjunto adequado do BT.
Marquês de Lorne
3

Para verificar quando ou não uma dada árvore binária é uma árvore de pesquisa binária, eis uma abordagem alternativa.

Atravessar a árvore de maneira inorder (por exemplo, filho esquerdo -> pai -> filho direito), armazenar dados do nó atravessado em uma variável temporária , digamos temp , antes de armazenar no temp , verifique se os dados do nó atual estão mais altos que os anteriores ou não . Em seguida, basta dividi -lo, a Árvore não é a Árvore de Pesquisa Binária;

Abaixo está um exemplo com Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Manter variável temporária fora

Neeraj Jain
fonte
Qualquer subárvore pode ser nula. Seu algoritmo não lida com esse caso corretamente.
Marquês de Lorne #
1

Em uma árvore de pesquisa binária, todos os nós são organizados em uma ordem específica - os nós à esquerda de um nó raiz têm um valor menor que sua raiz e todos os nós à direita de um nó têm valores maiores que o valor do raiz.

Spencer Cheng
fonte
0

Uma árvore pode ser chamada como uma árvore binária se e somente se o número máximo de filhos de qualquer um dos nós for dois.

Uma árvore pode ser chamada como uma árvore de pesquisa binária se e somente se o número máximo de filhos de qualquer um dos nós for dois e o filho esquerdo for sempre menor que o filho certo.

jith912
fonte