Sisttemas Operativos


Árboles Binarios
Un árbol binario es un árbol cuyos nodos no se pueden tener más de dos subárboles. En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce como nodo izquierda como “hijo izquierdo” u el nodo derecha “hijo derecho”.





Un árbol binario es una estructura recursiva. Cada nodo raíz de su propio subárbol y tiene hijos, que son raíces deárboles. Llamados subárboles derecho e izquierdo del nodo, respectivamente. Un árbol binario de divide en tres subconjuntos.
Propiedades:
Definimos 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 , y a la secuencia de líneas se le denomina ruta (path).

Los árboles tienen las siguientes propiedades:Tienen un nodo al que se le llama raíz del árbol.
Todos los nodos, excepto la raíz, tienen una sola línea de entrada
(El nodo raíz no tiene ninguna).
Existe una ruta única del nodo raíz a todos los demás nodos del árbol.
Si hay una ruta , entonces a „b‟ se le denomina „hijo‟ de „a‟ y es el nodo raíz de un subárbol.



Características y propiedades de los árboles.

1. * NODOindica un elemento, o ítem, de información.
2. * Todo árbol que no es vacío, tiene un único nodo raíz.
3. * Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y.
4. * Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es padre de Y.
5. *Se dice que todos los nodos que son descendientes directos (hijos) de un mismonodo (padre), son hermanos.
6. * Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
7. * Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
8. * Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol.
9. * Nivel es el número de arcos que debenser recorridos para llegar a un determinado nodo. Por definición, la raíz tiene nivel 1.
10. *Altura del árbol es el máximo número de niveles de todos los nodos del árbol.


















Longitud de camino interno y externo.

Se define la longitud de camino X como el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tienelongitud de camino 1, sus descendientes directos longitud de camino 2 y así sucesivamente.









Longitud de camino interno.
La longitud de camino interno es la suma de las longitudes de camino de todos los nodos del árbol. Es importante por que permite conocer los caminos que tiene el árbol. Puede calcularse por medio de la siguiente fórmula:




Donde “i‟ representa el nivel delárbol, “h‟ su altura y “ni‟ el número de nodos en el nivel “i‟.

Longitud de camino externo.
Árbol extendido es aquel en el que el número de hijos de cada nodo es igual al grado del árbol. Si alguno de los nodos del árbol no cumple con esta condición entonces debe incorporársele al mismo nodos especiales; tantos como sea necesario para satisfacer la condición.
Los nodos especiales tienen comoobjetivo remplazar las ramas vacías o nulas, no pueden tener descendientes y normalmente se representan con la forma de un cuadrado.

Ejemplo:
El número de nodos especiales de este árbol es 25 del árbol de grado 3.









Definición LCE
Se puede definir ahora la longitud de camino externo como la suma de las longitudes de camino de todos los nodos especiales del árbol. Se calculapor medio de la siguiente fórmula:




En donde “i‟ representa el nivel del árbol, “h‟ su altura y “nei‟ el número de nodos especiales en el nivel “i‟.
La media de la longitud de camino
externo (LCEM)
Ahora bien, se calcula dividiendo LCE entre el número de nodos especiales del árbol (ne).
LCEM = LCE / ne
Y significa el número de arcos que deben ser recorridos en promedio para...