Diferencia entre una Lista de enlaces y un Árbol de Búsqueda Binario

Un Árbol de búsqueda binario es un árbol binario en el que cada nodo interno x almacena un elemento tal que el elemento almacenado en el subárbol izquierdo de x es menor o igual a x y los elementos almacenados en el subárbol derecho de x son mayores o iguales a x .

Ahora una Lista enlazada consiste en una secuencia de nodos, cada uno conteniendo valores arbitrarios y una o dos referencias apuntando a la siguiente y / o nodos anteriores.

En informática, un árbol de búsqueda binario (BST) es una estructura de datos de árbol binario que tiene las siguientes propiedades:

• cada nodo (elemento en el árbol) tiene un valor distinto;
• los subárboles izquierdo y derecho también deben ser árboles de búsqueda binarios;
• el subárbol izquierdo de un nodo contiene solo valores menores que el valor del nodo;
• el subárbol derecho de un nodo solo contiene valores mayores o iguales al valor del nodo.

En el ordenador science, a linked list es una de las estructuras de datos fundamentales, y se puede utilizar para implementar otras estructuras de datos.

Por lo tanto, un árbol de búsqueda binario es un concepto abstracto que puede implementarse con una lista vinculada o una matriz. Mientras que la lista enlazada es una estructura de datos fundamental.

Yo diría que la principal diferencia es que un árbol de búsqueda binario está ordenado. Cuando se inserta en un árbol de búsqueda binario, donde esos elementos terminan siendo almacenados en la memoria es una función de su valor. Con una lista vinculada, los elementos se agregan a ciegas a la lista independientemente de su valor.

De inmediato puede algunas compensaciones: Las listas vinculadas conservan el orden de inserción y la inserción es menos costosa Los árboles de búsqueda binarios son generalmente más rápidos para buscar

Una lista vinculada es un número secuencial de" nodos " vinculados entre sí, es decir:

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

Un Árbol de búsqueda Binario usa una estructura de nodos similar, pero en lugar de enlazar al siguiente nodo, enlaza a dos nodos hijos:

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

Siguiendo reglas específicas al agregar nuevos nodos a un BST, puede crear una estructura de datos que sea muy rápida de recorrer. Otras respuestas aquí han detallado estas reglas, solo quería mostrar a nivel de código la diferencia entre las clases de nodo.

It es importante tener en cuenta que si inserta datos ordenados en un BST, terminará con una lista vinculada y perderá la ventaja de usar un árbol.

Debido a esto, una LinkedList es una estructura de datos transversal O(N), mientras que una BST es una estructura de datos transversal O(N) en el peor de los casos, y una O(log N) en el mejor de los casos.

Las listas enlazadas y las BST no tienen mucho en común, excepto que ambas son estructuras de datos que actúan como contenedores. Listas vinculadas básicamente le permiten insertar y eliminar elementos de manera eficiente en cualquier lugar de la lista, manteniendo el orden de la lista. Esta lista se implementa usando punteros de un elemento al siguiente (y a menudo al anterior).

A árbol de búsqueda binario por otro lado es una estructura de datos de un mayor abstracción (es decir, no se especifica cómo esto se implementa internamente) que permite búsquedas eficientes (es decir, para encontrar un elemento específico no tiene que mirar todos los elementos.

Observe que una lista enlazada puede ser considerada como un árbol binario degenerado, es decir, un árbol donde todos los nodos solo tienen un hijo.

En realidad es bastante simple. Una lista enlazada es solo un montón de elementos encadenados entre sí, sin ningún orden en particular. Puedes pensar en él como un árbol realmente delgado que nunca se ramifica:

1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (este último es un intento ascii-art de un null de terminación)

Un Árbol de búsqueda Binario es diferente de 2 maneras: la parte binaria significa que cada nodo tiene 2 niños, no uno, y la parte de búsqueda significa que esos niños están dispuestos para acelerar las búsquedas - solo artículos más pequeños a la izquierda, y solo las más grandes a la derecha:

    5
   / \
  3   9
 / \   \
1   2   12

9 no tiene ningún hijo izquierdo, y 1, 2 y 12 son "hojas" - no tienen ramas.

¿Tiene sentido?

Para la mayoría de los tipos de "búsqueda" de usos, un BST es mejor. Pero para solo "mantener una lista de cosas con las que lidiar más tarde, Primero en Entrar Primero en Salir o Último en Entrar Primero en Salir", una lista vinculada podría funcionar bien.

El problema con una lista vinculada es buscar dentro de ella (ya sea para recuperarla o insertarla).

Para una lista con un solo enlace, debe comenzar por la cabeza y buscar secuencialmente para encontrar el elemento deseado. Para evitar la necesidad de escanear toda la lista, necesita referencias adicionales a los nodos dentro de la lista, en cuyo caso, ya no es una simple lista vinculada.

Un árbol binario permite una búsqueda e inserción más rápida al ser inherentemente ordenado y navegable.

An alternativa que he utilizado con éxito en el pasado es un SkipList. Esto proporciona algo similar a una lista vinculada pero con referencias adicionales para permitir un rendimiento de búsqueda comparable a un árbol binario.

Una lista enlazada es solo eso... lista. Es lineal; cada nodo tiene una referencia al siguiente nodo (y al anterior, si estás hablando de una lista doblemente enlazada). Un árbol ramifica - - - cada nodo tiene una referencia a varios nodos hijos. Un árbol binario es un caso especial en el que cada nodo tiene solo dos hijos. Por lo tanto, en una lista vinculada, cada nodo tiene un nodo anterior y un nodo siguiente, y en un árbol binario, un nodo tiene un hijo izquierdo, un hijo derecho y un padre.

Estas relaciones pueden ser bidireccional o unidireccional, dependiendo de cómo necesite ser capaz de atravesar la estructura.

Tienen similitudes, pero la principal diferencia es que un Árbol de Búsqueda Binario está diseñado para soportar la búsqueda eficiente de un elemento, o "clave".

Un árbol de búsqueda binario, como una lista doblemente enlazada, apunta a otros dos elementos en la estructura. Sin embargo, al agregar elementos a la estructura, en lugar de simplemente agregarlos al final de la lista, el árbol binario se reorganiza de modo que los elementos vinculados al nodo" izquierdo " sean menores que el nodo actual y los elementos vinculados al nodo el nodo "derecho" es mayor que el nodo actual.

En una implementación simple, el nuevo elemento se compara con el primer elemento de la estructura (la raíz del árbol). Si es menor, se toma la rama "izquierda", de lo contrario se examina la rama" derecha". Esto continúa con cada nodo, hasta que se encuentra una rama vacía; el nuevo elemento llena esa posición.

Con este enfoque simple, si los elementos se agregan en orden, se termina con una lista vinculada (con el mismo rendimiento). Existen diferentes algoritmos para mantener cierta medida de equilibrio en el árbol, reorganizando los nodos. Por ejemplo, los árboles AVL hacen el mayor trabajo para mantener el árbol lo más equilibrado posible, dando los mejores tiempos de búsqueda. Los árboles rojo-negro no mantienen el árbol tan equilibrado, lo que resulta en búsquedas ligeramente más lentas, pero hacen menos trabajo en promedio a medida que se insertan o eliminan las teclas.

La lista enlazada es datos lineales rectos con nodos adyacentes conectados entre sí, por ejemplo, A->B->C. Puede considerarlo como una valla recta.

BST es una estructura jerárquica al igual que un árbol con el tronco principal conectado a ramas y esas ramas a su vez conectadas a otras ramas y así sucesivamente. La palabra "Binaria" aquí significa que cada rama está conectada a un máximo de dos ramas.

Utiliza la lista vinculada para representar datos rectos solo con cada elemento conectado a un máximo de un elemento; mientras que puede usar BST para conectar un elemento a dos elementos. Puede usar BST para representar datos como el árbol genealógico, pero eso se convertirá en un árbol de búsqueda, ya que puede haber más de dos hijos por persona.

Un árbol de búsqueda binario se puede implementar de cualquier manera, no necesita usar una lista enlazada.

Una lista enlazada es simplemente una estructura que contiene nodos y punteros/referencias a otros nodos dentro de un nodo. Dado el nodo principal de una lista, puede navegar a cualquier otro nodo de una lista vinculada. Las listas doblemente enlazadas tienen dos punteros / referencias: la referencia normal al nodo siguiente, pero también una referencia al nodo anterior. Si el último nodo de una lista doblemente enlazada hace referencia al primer nodo en la lista como la siguiente nodo, y el primer nodo hace referencia al último nodo como nodo anterior, se dice que es una lista circular.

Un árbol de búsqueda binaria es un árbol que divide su entrada en dos mitades aproximadamente iguales basadas en un algoritmo de comparación de búsqueda binaria. Por lo tanto, solo necesita unas pocas búsquedas para encontrar un elemento. Por ejemplo, si tuviera un árbol con 1-10 y necesitara buscar tres, primero se verificaría el elemento en la parte superior, probablemente un 5 o 6. Tres sería menor que eso, por lo que solo se verificaría la primera mitad del árbol. Si el siguiente valor es 3, lo tiene, de lo contrario, se realiza una comparación, etc, hasta que no se encuentre o se devuelvan sus datos. Por lo tanto, el árbol es rápido para la búsqueda, pero no nessecarily rápido para la inserción o eliminación. Estas son descripciones muy ásperas.

Linked List de wikipedia, y Binary Search Tree, también de wikipedia.

Son estructuras de datos totalmente diferentes.

Una lista enlazada es una secuencia de elementos donde cada elemento está enlazado al siguiente, y en el caso de una lista doblemente enlazada, al anterior.

Un árbol de búsqueda binario es algo totalmente diferente. Tiene un nodo raíz, el nodo raíz tiene hasta dos nodos secundarios,y cada nodo secundario puede tener hasta dos notas secundarias, etc. Es una estructura de datos bastante inteligente, pero sería algo tedioso explicarlo aquí. Echa un vistazo a la Wikipedia artcle en él.