Arboles Binarios
Páginas: 3 (603 palabras)
Publicado: 7 de noviembre de 2012
Árboles
Los árboles se pueden definir como un tipo restringido de grafo.
Un grafo se define de la siguente manera: Un grafoconsiste de un número de nodos (puntos o vértices) y un grupode arcosque unen parejas de nodos. A todos los pares de nodos unidos porun arco se les llama nodos adyacentes. Los arcos pueden t ener una direccióndeterminada, generando así un grafo dirigido, el cual de locontrariosería no-dirigido. (También existen los grafos mixtos).
Por convención a los nodos de un grafo sele representa con círculos y los arcos que los conectan como líneas(no-dirigido) o flechas(dirigido).
Los árboles son entonces un subconjunto importantede los grafos, y son una herramienta útil para describir estructurasque representan algún tipo de jerarquía.
Un árbol dirigido tieneun nodo al que sele llama "raíz" y de este nodo parten todas las conexiones a losdemás nodos. A los nodos terminales se les llama "hojas" y a todoslos demás se les llama nodos intermedios.
Deacuerdo al número de arcos que partende cada nodo en un árbol, este se puede clasificar en diferentescategorías. Así se tienen árboles binarios, árboles2-3-4, árboles rojo-negro, árboles B, etc.
A losnodos que dependen de otro nodo tambiénse les conoce como nodos "hijos" o descendientes y al otro se le llamanodo "padre".
De esto de puede concluir que cada nodo padre esuna raíz de un sub-árbol.El número de sub-árboles que tieneun nodo determinan el grado del nodo. Naturalmente el grado de lashojas es de cero. Por convención al nodo raíz de arbol sele considera el nivel cero del árbol.Cuando se tienen varios árboles en un conjunto,al conjunto se le llama bosque.
Altura de un nodo: Es la longitud del caminomás largo desde el nodo hasta una hoja que sea decendiente de estenodo.Altura de un árbol = altura del nodo raíz.
Para poder realizar búsquedas eficientes en árbolesse manejan dos características: Los árboles pueden estarbalanceados por altura o por peso.
Arbol...
Los árboles se pueden definir como un tipo restringido de grafo.
Un grafo se define de la siguente manera: Un grafoconsiste de un número de nodos (puntos o vértices) y un grupode arcosque unen parejas de nodos. A todos los pares de nodos unidos porun arco se les llama nodos adyacentes. Los arcos pueden t ener una direccióndeterminada, generando así un grafo dirigido, el cual de locontrariosería no-dirigido. (También existen los grafos mixtos).
Por convención a los nodos de un grafo sele representa con círculos y los arcos que los conectan como líneas(no-dirigido) o flechas(dirigido).
Los árboles son entonces un subconjunto importantede los grafos, y son una herramienta útil para describir estructurasque representan algún tipo de jerarquía.
Un árbol dirigido tieneun nodo al que sele llama "raíz" y de este nodo parten todas las conexiones a losdemás nodos. A los nodos terminales se les llama "hojas" y a todoslos demás se les llama nodos intermedios.
Deacuerdo al número de arcos que partende cada nodo en un árbol, este se puede clasificar en diferentescategorías. Así se tienen árboles binarios, árboles2-3-4, árboles rojo-negro, árboles B, etc.
A losnodos que dependen de otro nodo tambiénse les conoce como nodos "hijos" o descendientes y al otro se le llamanodo "padre".
De esto de puede concluir que cada nodo padre esuna raíz de un sub-árbol.El número de sub-árboles que tieneun nodo determinan el grado del nodo. Naturalmente el grado de lashojas es de cero. Por convención al nodo raíz de arbol sele considera el nivel cero del árbol.Cuando se tienen varios árboles en un conjunto,al conjunto se le llama bosque.
Altura de un nodo: Es la longitud del caminomás largo desde el nodo hasta una hoja que sea decendiente de estenodo.Altura de un árbol = altura del nodo raíz.
Para poder realizar búsquedas eficientes en árbolesse manejan dos características: Los árboles pueden estarbalanceados por altura o por peso.
Arbol...
Leer documento completo
Regístrate para leer el documento completo.