¿Cuál es la diferencia entre un árbol de búsqueda binario y un montón binario?


Respuesta 1:

Orden. La dirección del orden.

Observar.

Un montón binario tiene la propiedad de que el padre de cualquier nodo hijo es externo. Qué significa eso? Eso significa que, si es un montón máximo, cada hijo de cualquier nodo será menor que el padre. Eso es. Las relaciones dentro de los padres no tienen importancia. En un montón mínimo, es todo lo contrario.

En un BST, la propiedad es la del orden transversal en orden. Es decir, el valor del hijo izquierdo debe ser menor que el valor del padre debe ser menor que el valor del hijo derecho. Y en realidad puede romper el igual a la cosa introduciendo un contador y decir: todos los nodos tienen contador y eso cuenta cuántas veces aparece el valor de un nodo.

Ellos son diferentes.

El primero te permite encontrar top-k en un sistema muy grande.

El segundo, le permite encontrar ... a través del recorrido en orden un valor ordenado de todos los elementos, y en casos generales, sí, ¡puede buscar porque, por supuesto, es el Árbol de búsqueda!


Respuesta 2:

La principal diferencia es que en un montón binario, cada nodo es al menos tan grande (alternativamente: al menos tan pequeño) como todos sus descendientes (si los hay), mientras que en un árbol de búsqueda binario, cada nodo es al menos tan grande como todos sus descendientes a la izquierda, pero no más grandes que ninguno a la derecha.

Si bien un árbol de búsqueda binario es útil para la búsqueda (y relativamente difícil de ordenar), un montón es de gran ayuda para ordenar elementos.


Respuesta 3:

El almacenamiento dinámico binario suele ser una cola prioritaria (tiene el elemento menor o mayor en la parte superior). Esta propiedad se mantiene cada vez que se elimina o agrega un elemento al almacenamiento dinámico binario.

Por otro lado, el propósito del árbol de búsqueda binario es más o menos como se esperaba. Indice varios registros y realice búsquedas. En este caso, generalmente el valor medio es la raíz del árbol, el subárbol izquierdo contiene elementos menores y el subárbol derecho contiene elementos mayores.