2008-11-19 9 views
82

Estoy tratando de encontrar la definición de árbol de búsqueda binaria y sigo encontrando definiciones diferentes en todas partes.¿Se permiten claves duplicadas en la definición de árboles de búsqueda binarios?

Algunos dicen que para cualquier subárbol dado, la clave secundaria izquierda es menor o igual que la raíz.

Algunos dicen que para cualquier subárbol dado, la clave secundaria derecha es mayor o igual que la raíz.

Y mi viejo libro de estructuras de datos de la universidad dice que "cada elemento tiene una clave y ningún elemento tiene la misma clave".

¿Existe una definición universal de bst? Particularmente en lo que respecta a qué hacer con los árboles con varias instancias de la misma clave.

EDIT: Tal vez estaba claro, las definiciones que estoy viendo son

1) dejó < = raíz < derecho

2) dejó < raíz < = derecha

3) dejó < root < a la derecha, de modo que no existen claves duplicadas.

Respuesta

2

Cualquier definición es válida. Siempre y cuando sea coherente en su implementación (siempre ponga nodos iguales a la derecha, siempre colóquelos a la izquierda, o nunca los permita), entonces está bien. Creo que es más común no permitirlos, pero aún así es una BST si están permitidos y se colocan a la izquierda o a la derecha.

+0

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

+0

Quizás debería, pero no es necesario para las propiedades de un árbol de búsqueda. – SoapBox

+0

# 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

2

Esas tres cosas que dijiste son todas verdaderas.

  • llaves son únicos
  • A la izquierda son las teclas menos que éste
  • A la derecha están las teclas superiores a éste

supongo que se podría revertir su árbol y poner la más pequeña teclas a la derecha, pero realmente el concepto de "izquierda" y "derecha" es solo eso: un concepto visual que nos ayuda a pensar en una estructura de datos que realmente no tiene izquierda ni derecha, por lo que realmente no importa.

20

En una BST, todos los valores que descienden en el lado izquierdo de un nodo son inferiores (o iguales a, ver más adelante) al nodo en sí. Del mismo modo, todos los valores que descienden en el lado derecho de un nodo son mayores que (o iguales a) el valor de los nodos (a).

Algunas BST pueden optar por permitir valores duplicados, de ahí los calificadores "o iguales a" anteriores.

El siguiente ejemplo puede aclarar:

  | 
     +--- 14 ---+ 
     |   | 
+--- 13 +--- 22 ---+ 
|   |   | 
1   16 +--- 29 ---+ 
       |   | 
       28   29 

Esto muestra una BST que permite duplicados - se puede ver que para encontrar un valor, se inicia en el nodo raíz y bajar el subárbol izquierdo o derecho, dependiendo de si su valor de búsqueda es menor o mayor que el valor del nodo.

Esto se puede hacer de forma recursiva con algo como:

def hasVal (node, srchval): 
    if node == NULL: 
     return false 
    if node.val == srchval: 
     return true 
    if node.val > srchval: 
     return hasVal (node.left, srchval) 
    return hasVal (node.right, srchval) 

y llamándolo con:

foundIt = hasVal (rootNode, valToLookFor) 

Duplicados añadir un poco de complejidad ya que es posible que tenga que seguir buscando una vez que haya encontrado su valor para otros nodos del mismo valor.


(a) Usted podría realidad ordenarlos en la dirección opuesta en caso de que así lo deseen siempre y cuando se ajusta la forma en que la búsqueda de una clave específica. Un BST solo necesita mantener un orden ordenado, ya sea ascendente o descendente no es relevante.

+0

Para el caso duplicado, ¿puede simplemente verificar si el hijo correcto es el mismo que el nodo actual en la cláusula node.val == srchval: y si es así, ir a la derecha? – bneil

45

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.)

+1

¿Cuáles son las desventajas de usar una lista en el nodo? – Pacerier

+0

@Pacerier Creo que en lugar de mantener una lista, podemos mantener un recuento de referencias en cada nodo y actualizar el recuento cuando se produce un duplicado. Tal algoritmo sería mucho más fácil y eficiente en la búsqueda y el almacenamiento. Además, requeriría cambios mínimos en el algoritmo existente que no admite duplicados. – SimpleGuy

0

1.) queda < = raíz < derecho

2.) a la izquierda < raíz < = derecha

3.) dejado < raíz < derecho, de modo que no existan claves duplicadas S t.

Puede que tenga que ir a buscar mis libros de algoritmos, pero fuera de mi cabeza (3) es la forma canónica.

(1) o (2) solo aparecen cuando comienza a permitir nodos duplicados y pone nodos duplicados en el árbol mismo (en lugar del nodo que contiene una lista).

35

Si su árbol de búsqueda binaria es un árbol negro rojo, o tiene la intención de realizar cualquier tipo de operación de "rotación de árbol", los nodos duplicados causarán problemas. Imagine que su regla de árbol es la siguiente:

izquierda < raíz < = derecha

Ahora imagine un simple árbol cuya raíz es 5, hijo izquierdo es nulo, y el hijo derecho es 5. Si lo hace un giro izquierdo en el raíz terminas con un 5 en el niño izquierdo y un 5 en la raíz con el niño derecho siendo nulo. Ahora algo en el árbol de la izquierda es igual a la raíz, pero su regla anterior asumió raíz < izquierda.

Pasé horas tratando de descubrir por qué mis árboles rojos/negros ocasionalmente se salían de control, el problema fue lo que describí anteriormente. ¡Espero que alguien lea esto y ahorre horas de depuración en el futuro!

+2

¿Cuál es la solución? – Pacerier

+15

¡No gire cuando tenga nodos iguales! Recorre hasta el siguiente nivel y gira eso. – Rich

+0

Otras soluciones son cambiar la regla del árbol para que sea 'left <= node <= right', o solo insertar antes de la * primera * aparición de un valor. – paxdiablo

3

Trabajando en una implementación de árbol rojo-negro que estaba recibiendo problemas validar el árbol con múltiples teclas hasta que me di cuenta que con la rotación de inserción de color rojo-negro, hay que aflojar la restricción a

left <= root <= right

Como ninguno de los documentos que estaba viendo permitía duplicar claves y no quería volver a escribir los métodos de rotación para explicarlo, decidí modificar mis nodos para permitir múltiples valores dentro del nodo y no duplicar las claves en el árbol.

0

La relación de ordenación de elementos < = es total order por lo que la relación debe ser reflexiva, pero normalmente un árbol de búsqueda binario (también conocido como BST) es un árbol sin duplicados.

De lo contrario, si hay duplicados, necesita ejecutar dos veces o más la misma función de eliminación.

0

Duplicate Keys • ¿Qué sucede si hay más de un elemento de datos con la misma clave? - Esto presenta un ligero problema en los árboles rojo-negro. - Es importante que los nodos con la misma clave se distribuyan en en ambos lados de otros nodos con la misma clave. - Es decir, si las llaves llegan en el orden 50, 50, 50, • desea que el segundo 50 vaya a la derecha del primero y el tercero 50 para ir a la izquierda del primero. • De lo contrario, el árbol se desequilibra. • Esto podría manejarse mediante algún tipo de proceso de aleatorización en el algoritmo de inserción. - Sin embargo, el proceso de búsqueda se vuelve más complicado si se encuentran todos los artículos con la misma clave. • Es más fácil proscribir artículos con la misma llave. - En esta discusión asumiremos que los duplicados no están permitidos

Se puede crear una lista vinculada para cada nodo del árbol que contenga claves duplicadas y almacenar datos en la lista.

18

Las tres definiciones son aceptables y correctas. Ellos definen diferentes variaciones de una BST.

El libro de su estructura de datos de la universidad no pudo aclarar que su definición no era la única posible.

Ciertamente, permitir duplicados agrega complejidad. Si utiliza la definición de "izquierda < = raíz < bien" y que tiene un árbol como:

 3 
    / \ 
    2  4 

a continuación, añadir un "3" clave duplicada a este árbol se traducirá en:

 3 
    / \ 
    2  4 
    \ 
    3 

Nota que los duplicados no están en niveles contiguos.

Este es un gran problema al permitir duplicados en una representación BST como la anterior: los duplicados pueden estar separados por cualquier número de niveles, por lo que no es tan simple verificar que existan duplicados de un nodo.

Una opción para evitar este problema es no representar duplicados estructuralmente (como nodos separados) sino utilizar un contador que cuente el número de apariciones de la clave. El ejemplo anterior tendría entonces un árbol como:

 3(1) 
    / \ 
    2(1)  4(1) 

y después de la inserción del duplicado tecla "3" se convertirá en:

 3(2) 
    / \ 
    2(1)  4(1) 

Esto simplifica las operaciones de búsqueda, extracción e inserción, a expensas de algunos bytes adicionales y operaciones de contador.

3

En el libro "Introducción a los algoritmos", tercera edición, por Cormen, Leiserson, Rivest y Stein, un árbol de búsqueda binaria (BST) se define explícitamente como permitiendo duplicados. Esto se puede ver en la figura 12.1 y el siguiente (página 287):

"Las claves en un árbol binario de búsqueda se almacenan siempre en una forma tal que se satisface la propiedad de búsqueda de árbol binario: Vamos x haber un nodo en un árbol de búsqueda binario. Si y es un nodo en el subárbol izquierdo de x, entonces y:key <= x:key. Si y es un nodo en el subárbol derecho de x, entonces . "

Además, un rojo-negro árbol se define a continuación, en la página 308 como:

"Un árbol rojo-negro es un árbol binario de búsqueda con un bit adicional de almacenamiento por nodo: su color "

Por lo tanto, los árboles rojo-negro definidos en este libro admiten duplicados.

Cuestiones relacionadas