Diferencia entre árbol binario y árbol de búsqueda binario

322

¿Alguien puede explicar la diferencia entre el árbol binario y el árbol de búsqueda binaria con un ejemplo ?

data-structures tree binary-tree binary-search-tree Neel
fuente

567

Árbol binario: árbol donde cada nodo tiene hasta dos hojas.

  1
 / \
2   3

Árbol de búsqueda binaria: se utiliza para buscar . Un árbol binario donde el elemento secundario izquierdo contiene solo nodos con valores inferiores al nodo primario, y donde el elemento secundario derecho solo contiene nodos con valores mayores o iguales que el elemento primario.

  2
 / \
1   3

usuario541686
fuente

14

@pete: Es algo conceptual, no necesariamente harás uno que no tenga restricciones. Sin embargo, hay muchos árboles binarios sin búsqueda que son especiales de alguna otra manera, por ejemplo, montones binarios.

user541686

19

@pete birary trees no necesariamente tiene que contener datos comparables, muchos árboles binarios (sin búsqueda) se utilizan para analizar la expresión algebraica, el árbol binario es perfecto para escribir un analizador de notación infijo, colocando el operador como nodo (s) y valores numéricos como hojas

JBoy

2

@JBoy: Sin embargo, no serán árboles binarios en ese caso. (por ejemplo, los operadores unarios no pueden tener dos hijos). Realmente no puedo pensar en un caso de uso práctico para árboles binarios sin restricciones, es por eso que hice ese comentario.

user541686

2

Genial y simple. +1 por ejemplo visual :)

Andrei Konstantinov

@Mehrdad Un árbol binario tiene uno o dos hijos por nodo. Los árboles de expresión son un ejemplo perfecto. Un árbol de búsqueda binario también tiene uno o dos hijos por nodo, a menos que esté lleno, lo que solo puede ocurrir con ciertos números de elementos.

Marqués de Lorne

56

Binary Tree es una forma especializada de árbol con dos hijos (hijo izquierdo y niño derecho). Es simplemente una representación de datos en la estructura de árbol.

Binary Search Tree (BST) es un tipo especial de árbol binario que sigue la siguiente condición:

el nodo secundario izquierdo es más pequeño que su nodo primario
el nodo secundario derecho es mayor que su nodo primario

Jayzcode
fuente

23

Estas condiciones no son suficientes. El subárbol izquierdo completo no debe contener claves solo inferiores a las primarias, y el subárbol derecho completo debe contener nodos mayores.

Marqués de Lorne

1

@EJP, ¿puedes elaborar tu comentario, por favor? ¿Qué quieres decir con subárbol completo? ¿Quiere decir que todos los valores de subárbol deben ser menores que la raíz en el lado izquierdo? y todos los valores deben ser mayores que el valor raíz en el lado derecho?

Asif Mushtaq

Siguiendo el segundo enlace, lea la sección sobre "Verificación" y quedará claro.

Rob

38

Un árbol binario está hecho de nodos, donde cada nodo contiene un puntero "izquierdo", un puntero "derecho" y un elemento de datos. El puntero "raíz" apunta al nodo superior del árbol. Los punteros izquierdo y derecho apuntan recursivamente a "subárboles" más pequeños a cada lado. Un puntero nulo representa un árbol binario sin elementos: el árbol vacío. La definición recursiva formal es: un árbol binario está vacío (representado por un puntero nulo) o está hecho de un solo nodo, donde los punteros izquierdo y derecho (definición recursiva adelante) apuntan a un árbol binario.

Un árbol de búsqueda binaria (BST) o "árbol binario ordenado" es un tipo de árbol binario donde los nodos están ordenados en orden: para cada nodo, todos los elementos en su subárbol izquierdo son menores al nodo (<), y todos los elementos en su subárbol derecho son mayores que el nodo (>).

El árbol que se muestra arriba es un árbol de búsqueda binario: el nodo "raíz" es un 5, y sus nodos de subárbol izquierdos (1, 3, 4) son <5, y sus nodos de subárbol derechos (6, 9) son> 5. Recurrentemente, cada uno de los subárboles también debe obedecer la restricción del árbol de búsqueda binario: en el subárbol (1, 3, 4), el 3 es la raíz, el 1 <3 y 4> 3.

Tenga cuidado con la redacción exacta de los problemas: un "árbol de búsqueda binario" es diferente de un "árbol binario".

Emmanuel Oddy
fuente

@GabrielStaples Se agregó estructura de árbol.

Gaurav Borole

14

Como todos los anteriores han explicado la diferencia entre el árbol binario y el árbol de búsqueda binario, solo estoy agregando cómo probar si el árbol binario dado es un árbol de búsqueda binario.

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 te ayude. Lo siento si me estoy desviando del tema porque siento que vale la pena mencionar esto aquí.

Molesto
fuente

1

El subárbol izquierdo o derecho puede estar vacío. Su código no maneja ese caso correctamente.

Marqués de Lorne

11

Binary Tree representa una estructura de datos que está formada por nodos que solo pueden tener dos referencias secundarias.

El árbol de búsqueda binaria ( BST ), por otro lado, es una forma especial de estructura de datos del árbol binario donde cada nodo tiene un valor comparable, y los niños de menor valor unidos a la izquierda y los niños de mayor valor a la derecha.

Por lo tanto, todos los BST son Binary Tree, sin embargo, solo algunos Binary Tree pueden ser también BST . Notifique que BST es un subconjunto del árbol binario .

Entonces, Binary Tree es más una estructura de datos general que Binary Search Tree . Y también debe notificar que el Árbol de búsqueda binaria es un árbol ordenado , mientras que no existe un conjunto de reglas para el Árbol binario genérico .

Árbol binario

A Binary Treeque no es a BST;

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

Árbol de búsqueda binaria (árbol ordenado)

Un árbol de búsqueda binaria que también es un árbol binario ;

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

Propiedad de nodo de árbol de búsqueda binaria

También notifique eso para cualquier nodo padre en el BST ;

Todos los nodos izquierdos tienen un valor menor que el valor del nodo padre. En el ejemplo superior, los nodos con valores {20, 25, 30} que están ubicados a la izquierda ( descendientes izquierdos ) de 50, son menores que 50.
Todos los nodos correctos tienen un valor mayor que el valor del nodo primario. En el ejemplo superior, los nodos con valores {70, 75, 80} que están ubicados a la derecha ( descendientes derechos ) de 50, son mayores que 50.

No existe una regla para el nodo del árbol binario . La única regla para el nodo de árbol binario es tener dos hijos, por lo que se explica por sí mismo por qué se llama binario .

Levent Divilioglu
fuente

¿Podemos implementar el árbol binario simple? ¿hay alguna implementación disponible? ¿Y para qué sirve este árbol?

Asif Mushtaq

@UnKnown Puede usar el Árbol de búsqueda binaria para ordenar y buscar. Puede encontrar la implementación del Árbol de búsqueda binaria aquí: github.com/bzdgn/data-structures-in-java/blob/master/src/…

Levent Divilioglu

Sé sobre eso, pero ¿existe alguna existencia de Simple Tree o Simple Binary Tree? o alguna implementación de Simple Binary Tree?

Asif Mushtaq

No tiene sentido usar eso, pero puede agregar instancias de Nodo arbitrarias a la raíz y a los hijos.

Levent Divilioglu

10

Un árbol de búsqueda binario es un tipo especial de árbol binario que exhibe la siguiente propiedad: para cualquier nodo n, el valor de cada nodo descendente en el subárbol izquierdo de n es menor que el valor de n, y el valor de cada nodo descendente en el subárbol derecho es mayor que el valor de n.

Kaushik Lele
fuente

8

Árbol binario

El árbol binario puede ser cualquier cosa que tenga 2 hijos y 1 padre. Se puede implementar como una lista o matriz vinculada, o con su API personalizada. Una vez que comience a agregarle reglas más específicas, se convertirá en un árbol más especializado. . La implementación conocida más común es que, agregue nodos más pequeños a la izquierda y más grandes a la derecha.

Por ejemplo, un árbol binario etiquetado de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 2. El árbol no está equilibrado y no está ordenado . https://en.wikipedia.org/wiki/Binary_tree

Por ejemplo, en el árbol de la izquierda, A tiene los 6 hijos {B, C, D, E, F, G}. Se puede convertir en el árbol binario de la derecha.

Búsqueda binaria

La búsqueda binaria es una técnica / algoritmo que se utiliza para encontrar elementos específicos en la cadena de nodos. La búsqueda binaria funciona en matrices ordenadas .

La búsqueda binaria compara el valor objetivo con el elemento central de la matriz; si son desiguales, se elimina la mitad en la que el objetivo no puede mentir y la búsqueda continúa en la mitad restante hasta que tenga éxito o la mitad restante esté vacía. https://en.wikipedia.org/wiki/Binary_search_algorithm

Un árbol que representa la búsqueda binaria . La matriz que se busca aquí es [20, 30, 40, 50, 90, 100], y el valor objetivo es 40.

Árbol de búsqueda binaria

Esta es una de las implementaciones del árbol binario. Esto está especializado para la búsqueda .

El árbol de búsqueda binaria y las estructuras de datos del árbol B se basan en la búsqueda binaria .

Los árboles de búsqueda binarios (BST), a veces llamados árboles binarios ordenados u ordenados, son un tipo particular de contenedor : estructuras de datos que almacenan "elementos" (como números, nombres, etc.) en la memoria. https://en.wikipedia.org/wiki/Binary_search_tree

Un árbol de búsqueda binario de tamaño 9 y profundidad 3, con 8 en la raíz. Las hojas no están dibujadas.

Y, por último, un gran esquema para comparar el rendimiento de estructuras de datos y algoritmos conocidos:

Imagen tomada de Algorithms (4th Edition)

Teoman shipahi
fuente

4

Un árbol binario es un árbol cuyos hijos nunca son más de dos. Un árbol de búsqueda binario sigue la invariante de que el elemento secundario izquierdo debe tener un valor menor que la clave del nodo raíz, mientras que el elemento secundario derecho debe tener un valor mayor que la clave del nodo raíz.

nana yaah
fuente

4

Árbol de búsqueda binaria: cuando se realiza un recorrido en orden en el árbol binario, se obtienen valores ordenados de los elementos insertados
Árbol binario: no se encuentra ningún orden ordenado en ningún tipo de recorrido

AlienOnEarth
fuente

No se necesita encontrar un orden ordenado . Un árbol de búsqueda binaria también es un árbol binario. No son mutuamente exclusivos. BST es un subconjunto adecuado de BT.

Marqués de Lorne

3

Para verificar si un árbol binario determinado es un árbol de búsqueda binario, aquí hay un enfoque alternativo.

Traverse Tree Inorder Fashion (es decir, Child izquierdo -> Parent -> Right Child), almacenar los datos del nodo atravesado en una variable temporal , digamos temp , justo antes de almacenar en temp , verificar si los datos del nodo actual son más altos que el anterior o no . Luego, solo divídalo , el árbol no es un árbol de búsqueda binaria, sino atraviese hasta el final.

A continuación se muestra un ejemplo con 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;
}

Mantener la variable temporal afuera

Neeraj Jain
fuente

Cualquiera de los subárboles puede ser nulo. Su algoritmo no maneja ese caso correctamente.

Marqués de Lorne

1

En un árbol de búsqueda binaria, todos los nodos están ordenados en un orden específico: los nodos a la izquierda de un nodo raíz tienen un valor menor que su raíz, y todos los nodos a la derecha de un nodo tienen valores mayores que el valor de raíz.

Spencer Cheng
fuente

0

Se puede llamar a un árbol como árbol binario si y solo si el número máximo de hijos de cualquiera de los nodos es dos.

Se puede llamar a un árbol como árbol de búsqueda binario si y solo si el número máximo de hijos de cualquiera de los nodos es dos y el hijo izquierdo siempre es más pequeño que el hijo derecho.

jith912
fuente

Diferencia entre árbol binario y árbol de búsqueda binario

Respuestas:

Árbol binario

Árbol de búsqueda binaria (árbol ordenado)

Propiedad de nodo de árbol de búsqueda binaria