data-structures - linked list append
Diferencia entre LinkedList y Binary Search Tree (13)
El problema con una lista vinculada es buscar dentro de ella (ya sea para recuperarla o insertarla).
Para una lista de enlace único, debe comenzar por el encabezado 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 clasificada y navegable.
Una alternativa que he utilizado con éxito en el pasado es una Lista de exclusión. Esto proporciona algo similar a una lista vinculada, pero con referencias adicionales para permitir un rendimiento de búsqueda comparable a un árbol binario.
¿Cuáles son las principales diferencias entre una lista vinculada y un BinarySearchTree? ¿BST es solo una forma de mantener LinkedList? Mi instructor habló sobre LinkedList y luego sobre BST, pero no los comparó ni dijo cuándo preferir uno sobre otro. Esta es probablemente una pregunta tonta, pero estoy muy confundido. Agradecería si alguien puede aclarar esto de una manera simple.
En ciencias de la computación, un árbol de búsqueda binaria (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 contiene solo valores mayores o iguales que el valor del nodo.
En informática, una lista vinculada es una de las estructuras de datos fundamentales y puede utilizarse para implementar otras estructuras de datos.
Por lo tanto, un árbol de búsqueda binaria es un concepto abstracto que puede implementarse con una lista vinculada o una matriz. Mientras que la lista vinculada es una estructura de datos fundamental.
En realidad es bastante simple. Una lista enlazada es solo un grupo de elementos encadenados, sin ningún orden en particular. Puedes pensar que es un árbol muy delgado que nunca se ramifica:
1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (este último es un intento de ascii-art en un nulo de terminación)
Un árbol de búsqueda binaria es diferente de 2 maneras: la parte binaria significa que cada nodo tiene 2 hijos, no uno, y la parte de búsqueda significa que esos niños están dispuestos a acelerar las búsquedas, solo elementos más pequeños a la izquierda y solo los más grandes. a la derecha:
5
/ /
3 9
/ / /
1 2 12
9 no tiene ningún hijo de la izquierda, y 1, 2 y 12 son "hojas", no tienen ramas.
¿Tener sentido?
Para la mayoría de los tipos de usos de "búsqueda", una BST es mejor. Pero por solo "mantener una lista de cosas para lidiar con los tipos de cosas del Primero en Entrar Primero o Último en Entrar Primero", una lista vinculada podría funcionar bien.
La lista enlazada es recta. Datos lineales con nodos adyacentes conectados entre sí, por ejemplo, A-> B-> C. Puedes considerarlo como una valla recta.
BST es una estructura jerárquica tal como un árbol con el tronco principal conectado a las 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 directos 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 un dato como árbol genealógico, pero se convertirá en un árbol de búsqueda n-aria ya que puede haber más de dos hijos para cada persona.
Las listas enlazadas y las BST no tienen mucho en común, excepto que ambas son estructuras de datos que actúan como contenedores. Las listas enlazadas básicamente le permiten insertar y eliminar elementos de manera eficiente en cualquier ubicación de la lista, mientras se mantiene el orden de la lista. Esta lista se implementa usando punteros de un elemento al siguiente (y a menudo el anterior).
Un árbol de búsqueda binario, por otro lado, es una estructura de datos de una abstracción más alta (es decir, no se especifica cómo se implementa internamente) que permite búsquedas eficientes (es decir, para encontrar un elemento específico no es necesario mirarlo todo) los elementos.
Tenga en cuenta que una lista vinculada se puede considerar como un árbol binario degenerado, es decir, un árbol donde todos los nodos solo tienen un elemento secundario.
Lista enlazada:
Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)
Árbol binario:
Node(1)
/
Node(2)
/ /
/ Node(3)
RootNode(4)
/ Node(5)
/ /
Node(6)
/
Node(7)
En una lista vinculada, los elementos se vinculan entre sí a través de un único puntero siguiente. En un árbol binario, cada nodo puede tener 0, 1 o 2 subnodos, donde (en el caso de un árbol de búsqueda binario) la clave del nodo izquierdo es menor que la clave del nodo y la clave del nodo derecho es más que el nodo Siempre que el árbol esté equilibrado, la ruta de búsqueda para cada elemento es mucho más corta que la de una lista vinculada.
Trayectos:
------ ------ ------
key List Tree
------ ------ ------
1 1 3
2 2 2
3 3 3
4 4 1
5 5 3
6 6 2
7 7 3
------ ------ ------
avg 4 2.43
------ ------ ------
Por estructuras más grandes, la ruta de búsqueda promedio se vuelve significativamente más pequeña:
------ ------ ------
items List Tree
------ ------ ------
1 1 1
3 2 1.67
7 4 2.43
15 8 3.29
31 16 4.16
63 32 5.09
------ ------ ------
Son estructuras de datos totalmente diferentes.
Una lista vinculada es una secuencia de elemento donde cada elemento está vinculado al siguiente, y en el caso de una lista doblemente vinculada, la 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 al artículo de Wikipedia sobre él.
Tienen similitudes, pero la principal diferencia es que un árbol de búsqueda binaria está diseñado para admitir la búsqueda eficiente de un elemento o "clave".
Un árbol de búsqueda binario, como una lista doblemente vinculada, 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 para que los elementos vinculados al nodo "izquierdo" sean menores que el nodo actual y los elementos vinculados al "derecho" nodo son mayores 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 encuentre una rama vacía; el nuevo elemento llena esa posición.
Con este enfoque simple, si los elementos se agregan en orden, terminas con una lista vinculada (con el mismo rendimiento). Existen diferentes algoritmos para mantener alguna 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, ofreciendo los mejores tiempos de búsqueda. Los árboles rojo-negro no mantienen el árbol equilibrado, lo que resulta en búsquedas un poco más lentas, pero hacen menos trabajo en promedio a medida que se insertan o eliminan las claves.
Un árbol de búsqueda binario puede implementarse de cualquier manera, no necesita usar una lista vinculada.
Una lista vinculada es simplemente una estructura que contiene nodos e indicadores / referencias a otros nodos dentro de un nodo. Dado el nodo principal de una lista, puede navegar a cualquier otro nodo en una lista vinculada. Las listas doblemente enlazadas tienen dos punteros / referencias: la referencia normal al siguiente nodo, pero también una referencia al nodo anterior. Si el último nodo en una lista doblemente vinculada hace referencia al primer nodo en la lista como el siguiente nodo, y el primer nodo hace referencia al último nodo como su 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 se necesitan unas pocas búsquedas para encontrar un elemento. Por ejemplo, si tiene un árbol con 1-10 y necesita buscar tres, primero se verificaría el elemento en la parte superior, probablemente un 5 o 6. Tres serían menos que eso, por lo que solo la primera mitad del árbol sería verificado. 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 buscar, pero no rápidamente para inserción o eliminación. Estas son descripciones muy aproximadas.
Linked List de wikipedia, y Binary Search Tree , también de wikipedia.
Un árbol de búsqueda binaria 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 que o igual a xy los elementos almacenados en el subárbol derecho de x son mayores o iguales que x .
Ahora, una lista vinculada consta de una secuencia de nodos, cada uno con valores arbitrarios y una o dos referencias que apuntan a los nodos siguientes y / o anteriores.
Una lista vinculada es solo eso ... una lista. Es lineal; cada nodo tiene una referencia al siguiente nodo (y el anterior, si estás hablando de una lista doblemente vinculada). Una ramas de árbol --- cada nodo tiene una referencia a varios nodos secundarios. 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 siguiente nodo, y en un árbol binario, un nodo tiene un elemento secundario izquierdo, secundario derecho y elemento primario.
Estas relaciones pueden ser bidireccionales o unidireccionales, según cómo necesite poder atravesar la estructura.
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 binaria utiliza una estructura de nodo similar, pero en lugar de vincularse al siguiente nodo, se vincula a dos nodos secundarios:
public class BSTNode
{
Object Data
BSTNode LeftNode;
BSTNode RightNode;
}
Al seguir reglas específicas al agregar nuevos nodos a una BST, puede crear una estructura de datos que sea muy rápida de atravesar. Otras respuestas aquí han detallado estas reglas, solo quería mostrar en el nivel de código la diferencia entre las clases de nodo.
Es importante tener en cuenta que si inserta datos ordenados en una BST, terminará con una lista vinculada y perderá la ventaja de utilizar un árbol.
Debido a esto, una lista enlazada 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.
Yo diría que la diferencia PRINCIPAL es que un árbol de búsqueda binario está ordenado. Cuando insertas en un árbol de búsqueda binaria, donde esos elementos terminan almacenados en la memoria es una función de su valor. Con una lista vinculada, los elementos se agregan ciegamente a la lista independientemente de su valor.
De inmediato puede hacer algunas concesiones: las listas vinculadas conservan el orden de inserción y la inserción es menos costosa. Los árboles de búsqueda binaria generalmente son más rápidos de buscar