Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
6
Árboles
Árboles de búsqueda
Los Árboles se caracterizan por almacenar sus nodos en forma jerárquica y no en forma lineal como las Listas Ligadas, Colas, Pilas, etc.
Árboles de búsqueda
Estructura Jerárquica
Estructura
Estructura Lineal
Lineal
Tipos de nodos
Tipos
de
nodos
Nodos padre e hijo
Nodos
Caracteristicas de los arboles de busqueda
Se dividen en:
Caracteristicas
Nivel: Nos referimos como nivel a cada generación dentro del árbol. Cada generación tiene un número de Nivel distinto que las demás generaciones.
• Un árbol vacío tiene 0 niveles
• El nivel de la Raíz es 1
• El nivel de cada nodo se calcula contando cuantos nodos existen sobre él, hasta llegar a la raíz + 1, y de forma inversa también se podría, contar cuantos nodos existes desde la raíz hasta el nodo buscado + 1.
Altura: Le llamamos Altura al número máximo de niveles de un Árbol.
Nivel y altura
Ejemplo
Peso:
Conocemos como peso a el número de nodos que tiene un Árbol. Este factor es importante porque nos da una idea del tamaño del árbol y el tamaño en memoria que nos puede ocupar en tiempo de ejecución (Complejidad Espacial en análisis de algoritmos.)
Peso
Ejemplo
Orden:
El Orden de un árbol es el número máximo de hijos que puede tener un Nodo.
Orden
Ejemplo
Grado:
El grado se refiere al número mayor de hijos que tiene alguno de los nodos del Árbol y está limitado por el Orden, ya que este indica el número máximo de hijos que puede tener un nodo.
Grado
Ejemplo
Arbol binario de busqueda
un árbol binario es una estructura de datos en
la cual cada nodo siempre tiene un hijo
izquierdo y un hijo derecho. No pueden tener
más de dos hijos (de ahí el nombre "binario").
Árbol binario
Árbol binario con enraizado
Enraizado
Un árbol binario con enraizado es como
un grafo que tiene uno de sus vértices,
llamado raíz, de grado no mayor a 2.
Con la raíz escogida, cada vértice tendrá
un único padre, y nunca más de dos
hijos.
Ejemplo
Árbol binario lleno
Un árbol binario lleno es un árbol en el que cada
nodo tiene cero o dos hijos.
Lleno
Ejemplo
Árbol binario perfecto
Un árbol binario perfecto es un árbol binario
lleno en el que todas las hojas (vértices con cero
hijos) están a la misma profundidad (distancia desde
la raíz, también llamada altura).
Perfecto
Ejemplo
Árbol binario completo
Se define a un árbol
binario completo como un árbol binario lleno en el
que todas las hojas están a profundidad n o n-1, para
alguna n.
Completo
Ejemplo
Recorrido de un árbol:
Busqueda
Postorden:
Postorden
Para recorrer un árbol binario no vacío en inorden (simétrico),
hay que realizar las siguientes operaciones recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho
Ejemplo
Inorden:
Inorden
Para recorrer un árbol binario no vacío en inorden (simétrico),
hay que realizar las siguientes operaciones recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho
Ejemplo
Preorden:
Para recorrer un árbol binario no vacío en preorden, hay que
realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho
Preorden
Ejemplo
Árbol ternario
un árbol de búsqueda ternario es un tipo de trie (a veces llamado un árbol de prefijo ) donde los nodos están dispuestos de una manera similar a un árbol binario de búsqueda , pero con un máximo de tres niños en vez de límite del árbol binario de dos.
Nodo con cero o un niño
Decir que el nodo a eliminar es el nodo A. Si un nodo no tiene hijos, la eliminación se logra mediante el establecimiento de un hijo de padres de A a nulo y el padre de la A a null. Si tiene un hijo, establezca el padre del hijo de la A a la matriz de A y establecer el hijo del padre de un niño que de una
Nodo con
cero
ó
un niño
Ejemplo
Inserción:
Los nodos pueden ser insertados en los árboles ternarios en entre tres otros nodos o se añaden después de un nodo externo .
Inserción
Ejemplo
Supresión:
Un nodo se elimina del árbol.solo algunos se eliminan sin ambigüedades
Supresión
Nodo externo:
Decir que nodo externo que se añade es nodo A.Para añadir un nuevo nodo después del nodo A, A asigna el nuevo nodo como uno de sus hijos y el nuevo nodo asigna el nodo A como su padre.
Nodo externo
Ejemplo
Nodo internos:
Decir que el nodo interno es el nodo A y el nodo B es el hijo de A.
Un asigna su hijo para el nuevo nodo y el nuevo nodo asigna a su matriz A. a continuación, el nuevo nodo asigna a su hijo a B y B asigna su matriz en el nuevo nodo.
Nodo interno
Ejemplo
Árbol cuaternario
Es una generalización de los árboles binarios para el tratamiento de los datos el espacio bidimensional.
Cada registro tiene asociado un punto del espacio bidimensional que se almacena en un nodo de orden 4.
Árbol cuaternario
Caracteristicas del árbol de busqueda cuaternario
Caracteristicas
Cada nodo consta de cinco campos:
El primer campo contiene el punto, y los campos restantes señalan los cuatro cuadrantes en que se divide el subespacio NE, NO, SO y SE.
Cada nodo consta de cinco campos
Ejemplo
La raíz:
Cada subárbol divide a cada uno de estos cuadrantes en 4 subcuadrantes y el proceso se repite, recursivamente, hasta alcanzar un nodo que no tenga hijos.
La raíz
Ejemplo
Usos:
• Puntos
• Áreas
• Curvas
• Superficies
• Volúmenes.
Usos
Ejemplo
Inserción:
El proceso de inserción es similar al de los árboles binarios:
En cada nodo se hace una comparación y se elige en consecuencia el encadenamiento correspondiente para descender un nivel.
SI este nodo es nulo, se crea un nuevo nodo:
Se inserta el nuevo registro.
Inserción
Descripción en pseudocódigo:
Si la raíz es nula, P se vuelve la raíz.
Si la raíz no es GRIS, significa que hay simplemente un nodo
Se realiza una búsqueda a partir de la raíz para encontrar el cuadrante a que P pertenece
Nota: Si el nodo echa hojas y donde P debe insertarse está vacío (BLANCO), P se inserta.
Descripción en pseudocódigo
Ventajas:
La representación de imágenes por medio de esta estructura.
Ventajas
Desventajas:
Una desventaja que presenta la estructura es cuando debe almacenar gran cantidad de diferentes píxeles existentes en una imagen con muchos colores, dado que podría tomar un tamaño excesivamente grande.