ARBOLES BALANCEADOS
Páginas: 3 (542 palabras)
Publicado: 24 de marzo de 2014
ARBOLES BALANCEADOS
DEFINICION:
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 estamanera 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 enun 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.
• Árbolbalanceado 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 semantienen a poca distancia de la raíz.
En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases dedatos y sistemas de archivos. Son árboles balanceados de búsqueda en los cuales cada nodo puede poseer más de dos hijos.1 Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones serealizan en tiempo logarítmico amortizado.
La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o seelimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o separten. Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden...
DEFINICION:
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 estamanera 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 enun 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.
• Árbolbalanceado 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 semantienen a poca distancia de la raíz.
En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases dedatos y sistemas de archivos. Son árboles balanceados de búsqueda en los cuales cada nodo puede poseer más de dos hijos.1 Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones serealizan en tiempo logarítmico amortizado.
La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o seelimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o separten. Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden...
Leer documento completo
Regístrate para leer el documento completo.