lunes, 4 de febrero de 2013

árboles ordenados


árboles ordenados

^
A partir del siguiente capítulo sólo hablaremos de árboles ordenados, ya que son los que tienen más interés desde el punto de vista de TAD, y los que tienen más aplicaciones genéricas.
Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia ordenada siguiendo uno de los recorridos posibles del árbol: inorden, preorden o postorden.
En estos árboles es importante que la secuencia se mantenga ordenada aunque se añadan o se eliminen nodos.
Existen varios tipos de árboles ordenados, que veremos a continuación:
  • árboles binarios de búsqueda (ABB): son árboles de orden 2 que mantienen una secuencia ordenada si se recorren en inorden.
  • árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles de cada rama para cualquier nodo no difieren en más de 1.
  • árboles perfectamente equilibrados: son árboles binarios de búsqueda en los que el número de nodos de cada rama para cualquier nodo no difieren en más de 1. Son por lo tanto árboles AVL también.
  • árboles 2-3: son árboles de orden 3, que contienen dos claves en cada nodo y que están también equilibrados. También generan secuencias ordenadas al recorrerlos en inorden.
  • árboles-B: caso general de árboles 2-3, que para un orden M, contienen M-1 claves.




Maria Sanabria :)

No hay comentarios:

Publicar un comentario