Please enable JavaScript.

Coggle requires JavaScript to display documents.

Estructura de datos (Unidad 3 (Árboles y árboles binarios (Árboles…

- - - - conjunto de elementos de n elementos unidos por referencias de un elemento al siguiente.
    - - estructura donde el primero en entrar es el ultimo en salir.
    - - Estructura donde el ultimo elemento agregado es el ultimo en salir.
  - - - Puede definir como una secuencia de instrucciones que representan un modelo de solución para determinado tipo de problemas. O bien un conjunto de instrucciones que realizadas en orden que conducen a obtener la solución de un problema.
      - Características
        
        Preciso, Indica todas las características de los elementos que se emplearan en el desarrollo del algoritmo; ejemplos: .
        
        Si hablamos de números, se debe definir qué tipo de número (Entero, fraccionario, negativo, positivo, etc.).
        
        Si hablamos de una pila, indica de que tipo, tamaño, calidad, etc
        
        Finito, Debe terminar en algún momento.
        
        Definido, si se sigue un algoritmo dos veces, se obtendrá el mismo resultado.
      - Partes de un algoritmo
        
        Proceso. serie de pasos para resolver el problema.
        
        Salida. El resultado solución del problema.
        
        Entrada. se indican todos los elementos (variables, constantes y sus características) que se van a utilizar para resolver el problema
- - - - Método, compara e intercambia (negrita) pares de elementos contiguos hasta clasificar todos los elementos. Hace varios pases sobre el arreglo, y en cada recorrido desplaza el elemento más pequeño (cursiva) del conjunto restante hacia el extremo final del subarreglo ya ordenado (subrayado).
      - Ventajas
        
        Es un método popular y de ordenación simple
        .
        En la clasificación de burbuja, los elementos se intercambian en su lugar sin utilizar almacenamiento temporal adicional.
        El requisito de espacio es mínimo
      - Desventajas
        
        La principal desventaja de la clasificación de burbuja es el hecho de que no trata bien con una lista que contiene una gran cantidad de elementos. Es un algoritmo lento O(n^2).
        Es el hecho de que no trata bien con una lista que contiene una gran cantidad de elementos.
        El tipo de burbuja es principalmente adecuado para la enseñanza académica pero no para aplicaciones de la vida real.
    - - Este método es ampliamente usado por los jugadores de naipes. Los elementos (naipes) se dividen conceptualmente en una secuencia destino a1...ai-1 y en una secuencia fuente ai...an. En cada paso, comenzando con i = 2 y aumentando i en una unidad, el i-ésimo elemento de la secuencia fuente se toma y se transfiere a la secuencia destino insertándolo en el lugar apropiado.
      - Ventajas
        
        La principal ventaja de la clasificación por selección es que se desempeña bien en una pequeña lista.
        Debido a que es un algoritmo de clasificación en el lugar, no se requiere almacenamiento temporal adicional más allá de lo que se necesita para mantener la lista original.
        Su desempeño es fácilmente influenciado por el orden inicial de los artículos antes del proceso de clasificación.
      - Desventajas
        
        La principal desventaja del tipo de selección es su poca eficiencia cuando se trata de una gran lista de artículos.
        La ordenación de selección requiere n^2 cuadrados de pasos para clasificar n elementos.
    - - Este método se basa en el siguiente principio:
        Seleccionar el elemento con la llave menor de la sublista ai ... an. Intercambiarlo con el primer elemento ai de la sublista ai ... an. Repítase las anteriores operaciones con los n-1 elementos restantes, luego con los n-2 elementos, hasta que no quede más que un elemento (el más grande).
      - Ventajas
        
        La principal ventaja de la clasificación por selección es que se desempeña bien en una pequeña lista.
        Debido a que es un algoritmo de clasificación en el lugar, no se requiere almacenamiento temporal adicional más allá de lo que se necesita para mantener la lista original.
        Su desempeño es fácilmente influenciado por el orden inicial de los artículos antes del proceso de clasificación.
      - Desventajas
        
        La principal desventaja del tipo de selección es su poca eficiencia cuando se trata de una gran lista de artículos.
        La ordenación de selección requiere n^2 cuadrados de pasos para clasificar n elementos.
    - - Como primer paso, el algoritmo selecciona como “pivote” a uno de los elementos del arreglo que hay que ordenar. A continuación, el arreglo se parte a ambos lados del pivote: se desplazan los elementos de tal manera que los que sean mayores que el pivote queden a su derecha, mientras que los demás (menores o iguales) quedan a su izquierda.
        Enseguida, las partes del arreglo a ambos lados del pivote se ordenan independientemente mediante llamadas recursivas del algoritmo. El resultado final es un arreglo ordenado.
      - Desventajas
        
        La pequeña desventaja de la clasificación rápida es que su desempeño en el peor de los casos es similar al desempeño promedio de las clasificaciones de burbuja, inserción o selección.
      - Ventajas
        
        La clasificación rápida es considerada como el mejor algoritmo de clasificación.
        Es capaz de lidiar bien con una gran lista de artículos.
        Debido a que se ordena en su lugar, tampoco se requiere almacenamiento adicional
    - - Un refinamiento de la inserción directa fue propuesto por D. L. Shell en 1959.
        El método se explica con un ejemplo. Primero, todos los elementos que estén cuatro posiciones aparte se agrupan y se ordenan por separado. Este proceso es llamado una ordenación-4. En el ejemplo de ocho elementos, cada grupo contiene exactamente dos elementos.
        Después de este primer pase, los elementos se reagrupan en grupos con los elementos colocados dos posiciones aparte y luego se ordenan otra vez. Este proceso recibe el nombre de ordenación-2.
        Por último, en un tercer pase, todos los elementos se ordenan con una ordenación normal u ordenación-1
      - Ventajas
        
        El algoritmo de clasificación de shell solo es eficaz para un número finito de elementos en una matriz.
        El algoritmo de clasificación de shell es 5.32 x más rápido que el algoritmo de clasificación de burbujas.
      - Desventajas
        
        El algoritmo de clasificación de shell es complejo en estructura y un poco más Difícil de entender.
        El algoritmo de clasificación de shell.
        Es significativamente más lento que los algoritmos de clasificación de combinación, clasificación rápida y ordenación de pila.
- - - - Definición
        
        El árbol binario de búsqueda es una estructura sobre la cual se pueden realizar eficientemente las operaciones de búsqueda, inserción y eliminación.
        Formalmente se define un árbol binario de búsqueda de la siguiente manera: “Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del subárbol izquierdo de T deben ser menores o iguales al valor del nodo T. De forma similar, todos los valores de los nodos el subárbol derecho de T debe ser mayores o iguales al valor del nodo T”.
      - Ejemplo
    - - Definición
        
        Un árbol ordenado es aquel en el cual la distribución de las ramas sigue cierto orden.
        Los árboles ordenados de grado 2 son de especial interés puesto que representan una de las estructuras de datos más importante en computación, conocida como árboles binarios.
        En un árbol binario cada nodo puede tener como máximo dos subárboles; y siempre es necesario distinguir entre el subárbol izquierdo y el subárbol derecho.
      - Ejemplo
    - - Definición
        
        un árbol como un conjunto de nodos y líneas. Un nodo es un elemento de información que reside en el árbol. Una línea es un par de nodos ordenados <u,v>, y a la secuencia de líneas se le denomina ruta (path).
      - Ejemplo
    - - Definición
        
        Se define un árbol binario balanceado como un árbol en el que todos sus nodos internos, excepto los de último nivel, tienen dos hijos; el subárbol izquierdo y el subárbol derecho.
      - Ejemplo