6329539
Description
Mind Map by Uriel Samano, updated more than 1 year ago
|
Created by Uriel Samano
over 7 years ago
|
|
BALANCEO DE UN ARBOL
- 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.
- Al insertar un elemento en un
árbol balanceado se deben
distinguir los siguientes casos:
- 1. Las ramas izquierda (RI) y
derecha (RD) del árbol tienen la
misma altura (HRI = HRD) por lo
tanto:
- 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 Si se inserta un
elemento en RI, entonces
HRI será mayor en una
unidad.
- 2. Las ramas izquierda (RI) y
derecha (RD) del árbol tienen altura
diferente 2.1 Supongamos que HRI
< HRD :
- 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
- 2.1.2 Si se inserta un elemento
en RD, entonces se rompe el
criterio de equilibrio del árbol y
es necesario reestructurarlo.
- 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.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. Las ramas izquierda (RI) y
derecha (RD) del árbol tienen la
misma altura (HRI = HRD) por lo
tanto:
- La principal característica de
estos es la de realizar
reacomodos o balanceos,
después de inserciones o
eliminaciones de elementos.
- 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.
- 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.
- Al insertar un elemento en un
árbol balanceado se deben
distinguir los siguientes casos:
Want to create your own Mind Maps for free with GoConqr? Learn more.