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

Alguém pode explicar a diferença entre a árvore binária e a árvore de pesquisa binária com um exemplo ?

Á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

Á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

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".

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.

Á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 nó 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 .

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.

Á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

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

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

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.

Á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.

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

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

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.

• Á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

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

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.

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.