4.1.6 Árboles balanceados

Para mejorar el acceso a la información, los árboles binarios ordenados deben buscar tener en sus subárboles el mismo número de componentes, garantizándose de esta manera que en cada paso de la búsqueda se descarte aproximadamente la mitad de los elementos del conjunto. Los árboles con dicha característica reciben el nombre de balanceados.

BALANCE: de un nodo en un nodo en un árbol binario, se define como la altura de su subárbol izquierdo menos la altura de su árbol derecho. Cada nodo en un árbol binario balanceado tiene balance igual a 1, -1 o 0, dependiendo si la altura de su subárbol izquierdo es mayor que, menor que o igual a la altura de su subárbol derecho.

TIPOS DE BALANCE: Existen básicamente dos tipos de balance de árboles binarios.

• Árbol balanceado por altura: en dónde todos los hijos o nodos hoja se intentan mantener a la misma distancia de la raíz.

• Árbol balanceado por peso: en dónde los nodos más visitados o utilizados se mantienen a poca distancia de la raíz.