Muchos algoritmos especificarán que los duplicados están excluidos. Por ejemplo, los algoritmos de ejemplo en el libro de Algoritmos MIT generalmente presentan ejemplos sin duplicados. Es bastante trivial implementar duplicados (ya sea como una lista en el nodo, o en una dirección particular).
La mayoría (que he visto) especifican los niños de la izquierda como < = y los niños de la derecha como>. En términos prácticos, una BST que permita que cualquiera de los niños derecho o izquierdo sea igual al nodo raíz, requerirá pasos computacionales adicionales para terminar una búsqueda donde se permiten nodos duplicados.
Lo mejor es utilizar una lista en el nodo para almacenar duplicados, ya que insertar un valor '=' en un lado de un nodo requiere volver a escribir el árbol de ese lado para colocar el nodo como hijo, o el nodo colocado como un nieto, en algún punto a continuación, lo que elimina parte de la eficiencia de búsqueda.
Debe recordar que la mayoría de los ejemplos de clase se simplifican para retratar y entregar el concepto. No vale la pena sentadillas en muchas situaciones del mundo real. Pero la afirmación, "cada elemento tiene una clave y ningún elemento tiene la misma clave", no se viola al usar una lista en el nodo del elemento.
¡Así que vaya con lo que dice el libro de estructuras de datos!
Editar:
definición universal de un árbol de búsqueda binaria implica el almacenamiento y la búsqueda de una clave basada en recorrer una estructura de datos en una de dos direcciones. En el sentido pragmático, eso significa que si el valor es <>, recorre la estructura de datos en una de las dos "direcciones". Entonces, en ese sentido, los valores duplicados no tienen ningún sentido.
Esto es diferente de BSP, o partición de búsqueda binaria, pero no tan diferente. El algoritmo de búsqueda tiene una de las dos direcciones para "viajar", o está hecho (con éxito o no). Por lo tanto, me disculpo porque mi respuesta original no abordó el concepto de "definición universal", ya que los duplicados son realmente distintos. tema (algo que lidiar con éxito después de una búsqueda, no como parte de la búsqueda binaria.)
si tiene un conjunto de datos que contiene claves duplicadas, entonces esos elementos deberían almacenarse dentro del 1 nodo en el árbol a través de un método diferente (lista vinculada, etc.). el árbol solo debe contener claves únicas. – nickf
Quizás debería, pero no es necesario para las propiedades de un árbol de búsqueda. – SoapBox
# 1 condición de una BST: "cada nodo (elemento en el árbol) tiene un valor distinto;" http: //en.wikipedia.org/wiki/Binary_search_tree – nickf