Diferencia entre un LinkedList y un árbol de búsqueda binario
https://stackoverflow.com/questions/270080
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cuáles son las principales diferencias entre una lista vinculada y un BinarySearchTree? ¿BST es solo una forma de mantener una LinkedList? Mi instructor habló sobre LinkedList y luego BST pero no los comparó o no dijo cuándo preferir uno sobre otro. Esta es probablemente una pregunta tonta, pero estoy realmente confundido. Le agradecería si alguien puede aclarar esto de una manera simple.
Solución
Lista vinculada:
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í mediante 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 Mientras el árbol esté equilibrado, la ruta de búsqueda a cada elemento es mucho más corta que la de una lista vinculada.
Rutas de búsqueda:
------ ------ ------
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
------ ------ ------
Otros consejos
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 son menores o iguales a x y los elementos almacenados en el subárbol derecho de x son mayores o iguales a x .
??
Ahora, una Lista vinculada consiste en una secuencia de nodos, cada uno con valores arbitrarios y una o dos referencias que apuntan a los nodos siguientes y / o anteriores.
En informática, 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 inferiores al valor del nodo;
- el subárbol derecho de un nodo contiene solo valores mayores o iguales al valor del nodo.
En informática, una lista vinculada es una de las estructuras de datos fundamentales, y puede ser usado para implementar otras estructuras de datos.
Entonces, 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.
Diría que la diferencia PRINCIPAL es que se ordena un árbol de búsqueda binario. Cuando 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 ciegamente a la lista independientemente de su valor.
Inmediatamente 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 de 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 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 un 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 a nivel de código la diferencia entre las clases de nodos.
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 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.
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 ubicación en la lista, manteniendo el orden de la lista. Esta lista se implementa utilizando punteros de un elemento al siguiente (y a menudo el anterior).
Un árbol de búsqueda binaria por otro lado es un dato estructura de una abstracción más alta (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 es necesario mirar todos los elementos.
Observe que una lista vinculada puede considerarse como un árbol binario degenerado, es decir, un árbol donde todos los nodos solo tienen un hijo.
En realidad es bastante simple. Una lista vinculada es solo un conjunto de elementos encadenados, sin ningún orden en particular. Puedes pensar en él como un árbol realmente delgado que nunca se ramifica:
Un árbol de búsqueda binaria es diferente de 2 maneras: la parte binaria significa que cada nodo tiene 2 elementos secundarios, no uno, y la parte de búsqueda significa que esos elementos están dispuestos para acelerar las búsquedas, solo elementos más pequeños a la izquierda y solo más grandes a la derecha:
5
/ \
3 9
/ \ \
1 2 12
9 no tiene hijo izquierdo, y 1, 2 y 12 son "hojas" - no tienen ramas.
¿Tiene sentido?
Para la mayoría de las "búsquedas" tipos de usos, un BST es mejor. Pero solo por "mantener una lista de cosas para tratar más tarde Primero en entrar, primero en salir o Último en entrar, primero en salir". tipo de cosas, 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 en la cabecera 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ápidas al ser inherentemente ordenado y navegable.
Una alternativa que he usado con éxito en el pasado es una 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 vinculada es solo eso ... una lista. Es lineal; cada nodo tiene una referencia al siguiente nodo (y al anterior, si está hablando de una lista doblemente vinculada). Un árbol se ramifica --- 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 nodo siguiente, y en un árbol binario, un nodo tiene un hijo izquierdo, un hijo derecho y un padre.
Estas relaciones pueden ser bidireccionales o unidireccionales, según cómo necesite atravesar la estructura.
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 a la "izquierda". Los nodos son menores que el nodo actual y los elementos vinculados a la " derecha " El nodo 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, la " izquierda " se toma la rama, de lo contrario, la derecha Se examina la rama. 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, terminará con una lista vinculada (con el mismo rendimiento). Existen diferentes algoritmos para mantener alguna medida de equilibrio en el árbol, al reorganizar los nodos. Por ejemplo, los árboles AVL hacen el mayor trabajo para mantener el árbol lo más equilibrado posible, brindando los mejores tiempos de búsqueda. Los árboles rojo-negros no mantienen el árbol tan 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 claves.
Lista enlazada son datos lineales rectos con nodos adyacentes conectados entre sí, p. A- > B- > C. Puedes considerarlo como una cerca recta.
BST es una estructura jerárquica como un árbol con el tronco principal conectado a las ramas y esas ramas a su vez conectadas a otras ramas y así sucesivamente. El " Binario " palabra 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 datos como el árbol genealógico, pero se convertirá en un árbol de búsqueda n-ario 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 vinculada.
Una lista vinculada 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 buscar 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 de 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 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 la primera mitad del El árbol sería luego 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 la búsqueda, pero no demasiado rápido para la inserción o eliminación. Estas son descripciones muy aproximadas.
Lista vinculada de wikipedia, y Árbol de búsqueda binaria , también de wikipedia.
Son estructuras de datos totalmente diferentes.
Una lista vinculada es una secuencia de elementos 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í. Consulte el el artículo de Wikipedia en él.
