binary tree - profundidad - Diferencia entre árbol binario y árbol binario de búsqueda.
para que sirve un arbol binario (11)
¿Puede alguien explicar la diferencia entre el árbol binario y el árbol binario de búsqueda con un ejemplo ?
Árbol binario: árbol donde cada nodo tiene hasta dos hojas
1
/ /
2 3
Árbol binario de búsqueda: se utiliza para la búsqueda . Un árbol binario donde el hijo izquierdo solo contiene nodos con valores menores que el nodo primario y donde el hijo derecho solo contiene nodos con valores mayores o iguales que el padre.
2
/ /
1 3
Como todos los anteriores han explicado acerca de la diferencia entre el árbol binario y el árbol de búsqueda binario, simplemente 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 ya que siento que vale la pena mencionar esto aquí.
En un árbol de búsqueda binario, todos los nodos se organizan en un orden específico: los nodos a la izquierda de un nodo raíz tienen un valor más pequeño que su raíz, y todos los nodos a la derecha de un nodo tienen valores mayores que el valor de raíz.
Para verificar si un árbol binario o no es un árbol de búsqueda binario, aquí hay un enfoque alternativo.
Traverse Tree Inorder Fashion (es decir, Left Child -> Parent -> Right Child), Almacenar datos de nodos recorridos en una variable temporal permite decir la temperatura , justo antes de almacenar en temp . Verifique si los datos actuales de Node son más altos que los anteriores. . Luego simplemente divídalo , el árbol no es un árbol de búsqueda binaria, sino un recorrido transversal 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 variable temporal fuera
Un árbol binario es un árbol cuyos hijos nunca son más de dos. Un árbol de búsqueda binario sigue el invariante de que el hijo izquierdo debe tener un valor más pequeño que la clave del nodo raíz, mientras que el árbol derecho debe tener un valor mayor que la clave del nodo raíz.
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.
Árbol binario
El árbol binario puede ser cualquier cosa que tenga 2 hijos y 1 padre. Puede implementarse como una lista o matriz vinculada, o con su API personalizada. Una vez que comienzas a agregar reglas más específicas en él, se convierte en un árbol más especializado . La implementación más común conocida es que, agregue nodos más pequeños a la izquierda y los 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 está desequilibrado 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 a la derecha.
Búsqueda binaria
La búsqueda binaria es una técnica / algoritmo que se utiliza para encontrar un elemento específico en la cadena de nodos. La búsqueda binaria funciona en arreglos ordenados .
La búsqueda binaria compara el valor objetivo con el elemento central de la matriz; si son desiguales, la mitad en la que el objetivo no puede mentir se elimina 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 binario de búsqueda
Esta es una de las implementaciones de árbol binario. Esto está especializado para la búsqueda .
El árbol de búsqueda binario y las estructuras de datos de á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 binario de búsqueda de tamaño 9 y profundidad 3, con 8 en la raíz. Las hojas no están dibujadas.
Y, finalmente, un gran esquema para la comparación de rendimiento de estructuras de datos bien conocidas y algoritmos aplicados:
Imagen tomada de algoritmos (4ª edición).
Árbol binario representa una estructura de datos compuesta 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 se adjuntan a los niños de valor izquierdo y más grande se unen a la derecha.
Por lo tanto, todos los BST son árboles binarios, sin embargo, solo algunos árboles binarios pueden ser también BST . Notifica que BST es un subconjunto de árbol binario .
Por lo tanto, 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 binario es un árbol ordenado , mientras que no existe tal conjunto de reglas para el Árbol binario genérico.
Árbol binario
Un Binary Tree que no es un BST ;
5
/ /
/ /
9 2
/ / / /
15 17 19 21
Árbol binario de búsqueda (árbol ordenado)
Un árbol de búsqueda binario 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 de la izquierda tienen un valor menor que el valor del nodo principal. En el ejemplo superior, los nodos con valores {20, 25, 30} que están ubicados a la izquierda ( descendientes a la izquierda ) de 50, son más pequeños que 50.
Todos los nodos correctos tienen un valor mayor que el valor del nodo principal. En el ejemplo superior, los nodos con valores {70, 75, 80} que están ubicados a la derecha ( descendientes de la derecha ) de 50, son mayores que 50.
No existe tal regla para el nodo de árbol binario . La única regla para Nodo de árbol binario es tener dos niños, por lo que se explica por sí mismo a qué se llama binario .
El árbol binario es una forma especializada de árbol con dos hijos (niño izquierdo y niño derecho). Es simplemente representación de datos en estructura de árbol.
El árbol de búsqueda binaria (BST) es un tipo especial de árbol binario que sigue la siguiente condición:
- El nodo hijo izquierdo es más pequeño que su nodo padre
- nodo secundario derecho es mayor que su nodo padre
Un árbol binario está formado por 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 en 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 binario de búsqueda (BST) o "árbol binario ordenado" es un tipo de árbol binario donde los nodos se organizan en orden: para cada nodo, todos los elementos en su subárbol izquierdo son menos que el nodo (<), y todos los elementos en su subárbol derecho son mayores que el nodo (>).
5
/ /
3 6
/ / /
1 4 9
El árbol que se muestra arriba es un árbol de búsqueda binario: el nodo "raíz" es un 5 y los nodos del subárbol izquierdo (1, 3, 4) son <5, y los nodos del subárbol derecho (6, 9) son> 5. Recursivamente, 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".
- Árbol de búsqueda binario: cuando el recorrido inorder se realiza en un árbol binario, obtiene valores ordenados de los elementos insertados
- Árbol binario: ningún orden ordenado se encuentra en ningún tipo de recorrido