Please enable JavaScript.
Coggle requires JavaScript to display documents.
ESTRUCTURAS DE DATOS (Arbololes, [2] (Tipos (Árboles AA (Operaciones (Para…
ESTRUCTURAS DE DATOS
Tipos
Para que sea válido
El nivel de un nodo hoja es uno.
El nivel de un hijo izquierdo es estrictamente menor que el de su padre.
El nivel de un hijo derecho es menor o igual que el de su padre.
El nivel de un nieto derecho es estrictamente menor que el de su abuelo.
Cada nodo de nivel mayor que uno debe tener dos hijos.
-
-
Propiedades
- Variación del árbol rojo-negro
- Sus nodos rojos sólo pueden añadirse como hijo derecho
- Cada nodo tiene como máximo M hijos.
- Cada nodo (excepto raíz) tiene como mínimo (M)/2 claves.
- La raíz tiene al menos 2 hijos si no es un nodo hoja. (según M)
- Todos los nodos hoja aparecen al mismo nivel.
- Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
- Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas condiciones:
- El primero tiene valor menor que r1.
- El segundo tiene valor mayor que r1 y menor que r2, etc.
- El último hijo tiene valor mayor que rm.
Porpiedades
Todo nodo es o bien rojo o bien negro.
La raíz es negra.
Todas las hojas (NULL) son negras. No contienen datos y no son relevantes.
Todo nodo rojo debe tener dos nodos hijos negros.
Cada camino desde un nodo dado a sus hojas descendientes contiene el mismo número de nodos negros.
Operaciones
- Rotación
- Búsqueda
- Inserción
- Eliminación
- Variación del árbol B en el que la información está en los nodos hojas
- El número máximo de claves en un registro es llamado el orden del árbol B+.
- El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.
- El número de claves que pueden ser indexadas usando un árbol B+ está en función del orden del árbol y su altura.
- utilizado en los sistemas de ficheros HFS y Reiser4
- requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2 compartiendo sus claves con los nodos adyacentes
- No confundir con árbol B+ en el que los nodos hojas están contactados por una lista enlazada
- Siempre equilibrados
- Al insertar o borrar hay que hacer rotación
- Factor de Equilibrio (FE): FE = altura subárbol derecho - altura subárbol izquierdo
- El árbol nulo (no contiene ningún nodo) es de orden 0.
- El árbol que consta de un único nodo es de orden 1.
- Para n > 1, el árbol de Fibonacci de orden n consta de un nodo raíz con el árbol de Fibonacci de orden n-1 como hijo izquierdo y el árbol de Fibonacci de orden n-2 como hijo derecho.
- caso particular de un árbol AVL, ya que el factor de equilibrio de todo nodo es -1
- Árbol binario de búsqueda auto-balanceable
- los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores
-
-
-
- Normalmente en BBDD y sistemas de archivos
- Balanceado por altura
- todos los nodos no-terminales tienen 2 o 3 descendientes
- todos los nodos hoja tienen la misma longitud (path length) o distancia desde la raíz
- exige que el crecimiento no se haga a nivel de las hojas (aunque la inserción sigue siendo en las hojas), sino a nivel de la raíz
-
-
-
- Orden de un árbol: número máx hijos que puede tener un nodo. Un árbol binario es de orden 2
- Grado de un nodo: número mayor de hijos directos que tiene dicho nodo
- Grado de un árbol: máximo grado de todos los nodos de dicho árbol. Está limitado por el orden
- Brazo: La conexión entre un nodo y otro
- n-arios: número máximo de hijos por nodo es de N
- Nivel : 1 + numero brazos entre nodo y raiz. Por convenio raíz nivel 1. El nivel de otro nodo es 1 más el nivel de su padre
- Profundidad o altura: Máximo nivel de cualquier hoja del árbol
- Anchura: mayor valor de número de nodos en un nivel
- Equilibrado: altura de sus dos subarboles difiere como máximo en una unidad
- binario completo: cada nodo distinto de las hojas tiene dos hijos y justificados a la izquierda
- binario lleno: todas las hojas están al mismo nivel
- Otras definiciones
- binario lleno: todos los nodos tiene cero o 2 hijos
- binario perfecto: Árbol lleno en donde todos las Hojas están en el mismo Nivel.
- Peso de un árbol: número de nodos total que tiene el árbol
- Si tienen más de un padre no es un árbol
-
Recorridos
- en amplitud (anchura o a nivel)
- Se visita nivel a nivel desde la raiz
- Preorden
- Inhorden
- Postorden
-