Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles.
En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles).
Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
Un árbol binario es una estructura recursiva. Cada nos es la 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 se divide en tres subconjuntos:
{R} Nodo raíz
{I1,I2,…,In} Subárbol izquierdo de R
{D1,D2,…,Dn} Subárbol derecho de R.
Equilibrio
La distancia de un nodo al nodo raíz determina la eficiencia con la que puede ser localizado.
Por ejemplo, dado cualquier nodo de un árbol, a sus hijos se puede acceder siguiendo sólo un camino de bifurcación o de ramas, el que conduce al nodo deseado. De modo similar, los nodos a nivel 2 un árbol sólo pueden ser accedidos siguiendo sólo dos ramas del árbol.
Si la altura del subárbol izquierdo es h, y la altura del subárbol derecho es hD, entonces el factor de equilibrio del árbol B se determina por la siguiente fórmula.
B= hD –hI
Un árbol está perfectamente equilibrado si su equilibrio o balance es cero, y sus subárboles son también perfectamente equilibrados. Dado que esta definición ocurre raramente se aplica una definición alternativa.
Un árbol binario está equilibrado si la altura de sus subárboles difiere en no más de uno (su factor de equilibrio es -1, 01, +1) y sus subárboles son también equilibrados.
En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles).
Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
Un árbol binario es una estructura recursiva. Cada nos es la 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 se divide en tres subconjuntos:
{R} Nodo raíz
{I1,I2,…,In} Subárbol izquierdo de R
{D1,D2,…,Dn} Subárbol derecho de R.
Equilibrio
La distancia de un nodo al nodo raíz determina la eficiencia con la que puede ser localizado.
Por ejemplo, dado cualquier nodo de un árbol, a sus hijos se puede acceder siguiendo sólo un camino de bifurcación o de ramas, el que conduce al nodo deseado. De modo similar, los nodos a nivel 2 un árbol sólo pueden ser accedidos siguiendo sólo dos ramas del árbol.
Si la altura del subárbol izquierdo es h, y la altura del subárbol derecho es hD, entonces el factor de equilibrio del árbol B se determina por la siguiente fórmula.
B= hD –hI
Un árbol está perfectamente equilibrado si su equilibrio o balance es cero, y sus subárboles son también perfectamente equilibrados. Dado que esta definición ocurre raramente se aplica una definición alternativa.
Un árbol binario está equilibrado si la altura de sus subárboles difiere en no más de uno (su factor de equilibrio es -1, 01, +1) y sus subárboles son también equilibrados.
.
No hay comentarios:
Publicar un comentario