BALANCEO DE UN ARBOL

Uriel Samano
Mind Map by Uriel Samano, updated more than 1 year ago
Uriel Samano
Created by Uriel Samano almost 4 years ago
25
0

Description

Mapa mental Arboles binarios
Tags

Resource summary

BALANCEO DE UN ARBOL
1 Se define un árbol balanceado como un árbol binario de búsqueda, en el cual se debe cumplir la siguiente condición: Para todo nodo T del árbol, la altura de los subárboles izquierdo y derecho no deben diferir en más de una unidad.
1.1 Al insertar un elemento en un árbol balanceado se deben distinguir los siguientes casos:
1.1.1 1. Las ramas izquierda (RI) y derecha (RD) del árbol tienen la misma altura (HRI = HRD) por lo tanto:
1.1.1.1 1.2 Si se inserta un elemento en RD, entonces HRD será mayor en una unidad. Observe que en cualquiera de los dos casos mencionados (1.1 y 1.2), no se viola el criterio de equilibrio del árbol.
1.1.1.2 1.1 Si se inserta un elemento en RI, entonces HRI será mayor en una unidad.
1.1.1.3 2. Las ramas izquierda (RI) y derecha (RD) del árbol tienen altura diferente 2.1 Supongamos que HRI < HRD :
1.1.1.3.1 2.1.1 Si se inserta un elemento en RI, entonces HRI será igual a HRD . las ramas tienen la misma altura, por lo que se mejora el equilibrio de y no es necesario estructurarlo
1.1.1.3.2 2.1.2 Si se inserta un elemento en RD, entonces se rompe el criterio de equilibrio del árbol y es necesario reestructurarlo.
1.2 La principal característica de estos es la de realizar reacomodos o balanceos, después de inserciones o eliminaciones de elementos.
1.2.1 Ahora bien, para poder determinar si un árbol esta balanceado o no, se debe manejar información relativa al equilibrio de cada nodo del árbol. Surge así el concepto de factor de equilibrio de un nodo(FE) que se define como la altura del subárbol derecho menos la altura del subárbol izquierdo.
Show full summary Hide full summary

Similar

Les síl·labes i els dígrafs
Marina Ivars Asencio
Les síl·labes i els dígrafs
Jorge Forner Gar
ARBOL GENEALOGICO SANGUINEO
Wiil Montoya
Emprendimiento: oportunidad vs necesidad
Jeshuá Banda
LA MML DE UN PROYECTO
Diego Chamorro
ELEMENTOS DE UN ORDENADOR
Noelia gonzalez
Quienes conforman mi Familia
josueuniandesr
ÁRBOL DE PROBLEMAS
Natasha Zamora
ÁRBOL DE PROBLEMAS
Mateo Perez Ramirez