data structures - ejercicios - ¿Se permiten claves duplicadas en la definición de árboles de búsqueda binarios?

arboles binarios ejemplos

Question

Estoy tratando de encontrar la definición de un árbol de búsqueda binaria y sigo encontrando definiciones diferentes en todas partes.

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

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

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

1) left <= root <right

2) left <root <= right

3) left <root <right, de modo que no existen claves duplicadas.

Answer 1

1.) left <= root <right

2.) left <root <= right

3.) left <root <right, de modo que no existen claves duplicadas.

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 surgen cuando comienzas a permitir nodos duplicados y pones nodos duplicados en el árbol mismo (en lugar del nodo que contiene una lista).

Answer 2

Al trabajar en una implementación de árbol rojo-negro, tuve problemas para validar el árbol con varias claves hasta que me di cuenta de que con la rotación de inserción rojo-negro, debe aflojar la restricción para

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.

Answer 3

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.

Answer 4

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

"Las claves en un árbol de búsqueda binaria siempre se almacenan de tal forma que satisfacen la propiedad del árbol de búsqueda binaria: Sea x 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 y:key >= x:key . "

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

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

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

Answer 5

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í. De manera similar, todos los valores que descienden en el lado derecho de un nodo son mayores que (igual a) el valor de los nodos ^(a) .

Algunas BST pueden optar por permitir valores duplicados, por lo tanto, 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: puede ver que para encontrar un valor, comienza en el nodo raíz y baja por el subárbol izquierdo o derecho según si el valor de búsqueda es menor o mayor que el valor del nodo.

Esto se puede hacer recursivamente 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)

Los duplicados agregan un poco de complejidad, ya que es posible que deba seguir buscando una vez que haya encontrado su valor para otros nodos del mismo valor.

^(a) En realidad, podría clasificarlos en la dirección opuesta si así lo desea siempre que ajuste cómo busca una clave específica. Un BST solo necesita mantener un orden ordenado, ya sea ascendente o descendente no es relevante.

Answer 6

Esas tres cosas que dijiste son todas verdaderas.

• Las llaves son únicas
• A la izquierda hay teclas menos que esta
• A la derecha hay claves mayores que esta

Supongo que podrías invertir tu árbol y colocar las teclas más pequeñas 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 una izquierda o bien, entonces realmente no importa.

Answer 7

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

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

Ciertamente, permitir duplicados agrega complejidad. Si usa la definición "left <= root <right" y tiene un árbol como:

      3
    /   /
  2       4

luego agregar una clave duplicada "3" a este árbol dará como resultado:

      3
    /   /
  2       4
    /
     3

Tenga en cuenta 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 cantidad de niveles, por lo que la verificación de la existencia de duplicados no es tan simple como la verificación de elementos secundarios 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 un árbol como:

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

y después de la inserción de la clave duplicada "3" se convertirá en:

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

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

Answer 8

Los elementos que ordenan la relación <= es un orden total, por lo que la relación debe ser reflexiva, pero comúnmente 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 o más veces la misma función de eliminación.

Answer 9

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 en ese lado para colocar el nodo como hijo, o el nodo se coloca como un gran -child, 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 ve con lo que dijo tu libro de estructuras de datos!

Editar:

La definición universal de un árbol de búsqueda binaria implica almacenar y buscar una clave basada en atravesar 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 abordaba el concepto de "definición universal", ya que los duplicados son realmente tema (algo que trata después de una búsqueda exitosa, no como parte de la búsqueda binaria).

Answer 10

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. Imagina que tu regla de árbol es esta:

left <root <= right

Ahora imagina un árbol simple cuya raíz es 5, el hijo izquierdo es nil y el derecho es 5. Si haces una rotación hacia la izquierda en la raíz, terminarás con un 5 en el hijo izquierdo y un 5 en la raíz con el hijo correcto siendo nil. Ahora algo en el árbol de la izquierda es igual a la raíz, pero la regla anterior asumió left <root.

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!

Answer 11

Teclas duplicadas • ¿Qué ocurre si hay más de un elemento de datos con la misma clave? - Esto presenta un ligero problema en árboles rojo-negro. - Es importante que los nodos con la misma clave se distribuyan en ambos lados de otros nodos con la misma clave. - Es decir, si las claves 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 deben encontrar todos los elementos con la misma clave. • Es más simple proscribir artículos con la misma llave. - En esta discusión asumiremos que los duplicados no están permitidos

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