Arbres
  • Definición de recorrido en anchura y profundidad de un árbol binario Eva Santonja Civantos
    • En un recorrido en anchura de un árbol binario los nodos se visitan nivel a nivel y, dentro de cada nivel, de izquierda a derecha. En profundidad los nodos se visitan bajando por las ramas del árbol.
  • ¿Un solo nodo sin contener ningun dato se podría considerar un arbol binario? Víctor Costa Vidal
    • Si, ya que no incumple ninguna propiedad de dicha estructura.
  • Quin ès l'element mínim en un ABC? Jordi Belda Felipe
    • L'element minim en un ABC és el node que no té cap fill a l’esquerre i no pertany a cap subarbre dret de cap node
  • Quan un arbre binari es de cerca? Genís Martínez Sanchís
    • Tots el elements del subarbre esquerre són menors que el valor de l’arrel
    • Tots el elements del subarbre dret són majors que el valor de l’arrel.
  • Què es la profunditat d'un node? ? José Joaquin Rubio Iñigo
    • S’anomena profunditat d’un node a la longitud del camí des de l’arrel fins eixe node.
  • Que es un arbre binari de cerca? Daniel Sanchez Lopez.
    • És una estructura de dades molt versàtil que serveix per a la implementació de diccionaris i de cues de prioritat (generalització de la cerca dicotòmica). Suporta eficientment les operacions de cerca, localitzar el mínim i el màxim, el predecessor i el successor i les operacions d’inserció i esborrat.
  • A que anomenem alçària d'un arbre? Jesús Yáñez Signes
    • L’alçària d’un arbre és la profunditat del node més profund.
  • Per què diem que un arbre és una estructura recursiva? Javier Martínez Bernia
    • Perquè l'agafes del node que l'agafes continues tenint un arbre.
  • Quin ès l'element MÀXIM un ABC? Joan Vicent Pedro Martí
    • És el node que no te cap fill a la dreta i no pertany a cap subarbre esquerre de cap node
  • Quins són els posibles recorreguts, per a vore tots els nodes d'un arbre binari? Juan Carlos Asensi Cavero
    • Preordre, inordre, postordre.
  • Quan podem dir que un arbre binari és de cerca? Pablo Pérez Mas
    • Quan tots el elements del subarbre esquerre són menors que el valor de l’arrel i tots el elements del subarbre dret són majors que el valor de l’arrel.
  • En que es basen els arbres balancejats? Vicent Martinez Chulvi
    • Efectuen “rotacions” on s’intercanvien nodes i subarbres en un arbre binari de cerca para aconseguir un altre equivalent.
    • Efectuen una “reconstrucció parcial”. Un recorregut en inordre d’un ABC produeix una seqüència ordenada que permet un arbre perfectament balancejat amb un cost lineal.
  • Que denominem com a fulla? David García Agost
    • Un node sense fills, la resta de nodes s’anomenen nodes interns.
  • En que consisteix el recorregut inordre? Héctor Serrano Estellés
    • Consisteix en recorrer l’arrel entre el subarbre esquerre i dret, es a dir visitar el fill esquerre, el node i finalment el fill dret.
  • Què és un arbre binari? Mireia Vico Burruezo
    • És un arbre en el que el màxim nombre de fills de cada node és 2: fill esquerrà i fill dret.
  • Què es un arbre? María Alabau Bosque
    • Un arbre es una estructura jeràrquica que es defineix com:
      • 1) Un conjunt finit de nodes, un de ells s'anomena arrel.
      • 2) Una relació entre nodes representada en forma d’arestes. Cada node té un únic pare conectat amb una aresta, excepte l’arrel que no té pare.
  • Com s'esborra en un ABC? Ana María Adam Liberos
    • Depén del cas:
      • Cas 1: L'element es una fulla -> s'esborra i no es fa res mes.
      • Cas 2: L'element té un fill -> s'esborra i el seu fill ocupa la seua posició.
      • Cas 3: L'element té dos fills -> s'esborra i el seu lloc es ocupat per el menor fill del subarbre dret (o del major fill del subarbre esquerra).
  • En que consisteix en recorregut preordre? Pablo S. Díaz Castelló
    • L'arrel es processa abans que les subarrels:
      • visitar el node
      • visitar el fill esquerre en preordre
      • visitar el fill dret en preordre
  • Quin és l'element màxim en un ABC? Raúl Talens Ferrer
    • L'element màxim en un ABC és el node que no té cap fill a la dreta i no pertany a cap subarbre esquerre de cap node
  • Quina propietat han de seguir els arbres de binaris de cerca? Juan Carlos Criado Beltrán
    • Si es llisten els elements segons un recorregut inordre resulta una seqüència ordenada.
  • Quin és el grau d'un node? Maria Ribes de la Concepción
    • El grau d’un node és el nombre de fills que té.
  • Respecte a la cerca en un ABC, hi ha instàncies significatives? ¿Quines? Stella Esparza Torregrosa
    • Sí, les instàncies significatives són:
        • Cas millor: L'element buscat està en l'arrel de l'ABC. (Es realitza 1 comparació,per tant, cost constant).
        • Cas pitjor: L'element està en qualsevol fulla del nivell més alt o l'element NO està en l'ABC i provoca el recorregut de la branca més llarga. (Es realitza un nombre de comparacions proporcional al nombre de nivells de l'ABC).
  • Com es fa el recorregut postordre d'un ABC? Álvaro Salvador González
    • Primer es visita el fill esquerre en postordre, després el fill dret en postordre, i finalment el node.
  • Entre quins costos es mouen les operacions en un ABC? Cristian Medina Azorín
    • Cost de la majoria d'operacions en un ABC ∈ O(h), essent h l’alçària de l’ABC (h ∈ [logn : n]).
    • Així que T(n) ∈ [ $\Omega(logn$ : O(n) ]
  • Quina és la diferència entre un arbre ordenat i un no ordenat? Iris López Mratínez
    • En un arbre no ordenat l’ordre dels fills no és rellevant, mentre que en un ordenat si que ho és
  • Quin és el nombre màxim de nodes de profunditat "i" en un arbre binari ? Albert Grau Anguera
    • El nombre màxim de nodes de profunditat "i" manté una relació de 2^i.
  • Com s'anomenen les estructures basades en arbres que inclouen informació i/o operacions addicionals per a aconseguir un equilibri en els arbres? Javier Contrí González
    • Aquestes estructures s'anomenen arbres balancejats.
  • Segons l'ordenació dels fills, quins tipus d'arbres tenim? Elena Garrigós Candela
    • Arbre ordenat: l'ordre dels fills és rellevant.
    • Arbre no ordenat: l'orde dels fills no és rellevant.
  • Quan diem que un ABC està equilibrat? Jose Daniel Ferrando Ferrer
    • Un ABC està equilibrat si els subarbres esquerre i dret de qualsevol node tenen altures que difereixen com a molt en 1
  • Quin és l'element successor d'un node? Àngel Giner Vidal
    • El mínim element en el subarbre dret del node, dins del subarbre dret, l'element més a l'esquerra.
  • ¿Cómo puede crearse un árbol equilibrado mediante un array? Tomás Ruiz Martín
    • Asegurándonos primero que el array está ordenado de forma ascendente, para después de forma recursiva, ir vinculando los elementos situados en la mitad del array/subarray. Siendo la raíz el elemento situado en la mitad, su hijo izquierdo el elemento de la mitad del subarray inferior y el derecho el elemento de la mitad del subarray superior.
  • Com es calcula el nombre de fulles màxim a un arbre binari? Laura Medina Chaveli
    • 2^h (h sent alçària)
  • Quin és l'element predecessor d'un node? Arnau Ruiz Fuster
    • És el node amb major clau del subarbre esquerre del node en qüestió.
  • Quines aplicacions tenen els arbres en la vida cotidiana? Joan Ramón Esteve Chulià
    • Degut a les seues propietats jeràrquiques i reduïts costos de cerca, els arbres son utilitzats principalment amb diccionaris en teclats predictius i de correcció. A més, son utilitzats ampliament per compiladors. Un ús molt interessant es el de les xarxes neuronals, pero aixó es una altura asignatura.
  • Son propietats d'un arbre binari? Joan Ramon Coscollar
    • 1-El màxim nombre de nodes en un arbre binari d’alçària h és 2^(h+1) - 1.
    • 2- El màxim nombre de nodes interns és 2^h.
    • 3- El màxim nombre e fulles és 2^h.
      • Sols la 1 i la 3, la 2 dueria ser 2^(h) - 1.
  • Quina es l'alçària mínima d'un arbre binari amb n nodes?# Antonio Manuel Sirvent Juan
    • L'alçària mínima d'un arbre binari amb n nodes es [log2n]
  • Quina és la diferencia entre un arbre ordenat i un no ordenat? Jesús Peiró López
    • En el no ordenat, l'ordre dels fills no és rellevant, mentre que en el ordenat sí.
  • Com s'esborraria un element de un ABC que té dos fills? Àngel Chirlaque Zapata
    • S’elimina aquest element i el seu lloc és ocupat pel menor fill del subarbre dret o si és del subarbre esquerre, el major fill.
  • ¿Que es un arbol balanceado?Miguel Angel Mateo Casali
    • Es un arbol que incluye informacion o operaciones adicionales para conseguir un equilibrio
  • Què és un subarbre? Joaquim Brines i Garcia
    • És tot aquell arbre inclós dins de l'arbre, per exemple si l'arbre principal té 2 fills, aleshores podem dir que té 2 subarbres
  • Què són els nodes interns? Víctor Cardona Lorenzo
    • Són tots aquells nodes de l'arbre que no són fulles
  • Com podem saber si un element d'un arbre es el mínim? I si és el màxim? Miguel García Bohigues
    • Si el node no pertany a cap sub arbre dret de cap node y no té fill esquerre és el minim. Si, per altra banda, no pertany a cap sub arbre dret de cap node y no te fill dret, es màxim.
  • Quina diferencia hi ha entre un arbre binari complet i un quasi-complet? Guillermo Montilla Tomás
    • En un arbre binari complet totes les fulles tenen la mateixa profunditat i tots els nodes interns tenen grau 2, en canvi, un arbre quasi-complet es com un complet a excepció del nivell de les fulles, en el qual estan tant a l'esquerra com siga posible.
  • Quin es el ABC mes menut possible? Marc Gavilán Gil
    • Un ABC amb 0 nodes
  • Què és un arbre degenerat? Sergi Vendrell García
    • Un arbre degenerat és un arbre que, per a cada node pare, només hi ha associat un node fill. Per tant es comporta com una llista enllaçada.
  • Un arbre amb un sol node. Pot ser un ABC? Joan Cervera Buigues
  • Si.
  • Que es el invers de un ABC? Vicente Gavilá Buigues
  • Es un ABC que te els mateixos elements, però, de orden invers. Es a dir, que el fill dret es menor que el node i el fill esquerre es major que el node.
  • **Existeix algun recorregut que aplicat a un arbre binari de cerca ens proporcione una seqüència ordenada? A què es degut? Jean Fernandes **
  • El Inordre, perque primer fa els fills esquerres (que són els més menuts), després el node i per últim els fills drets que són majors que el node. Per això, queden ordenats.
  • Com es pot saber si cal equilibrar un ABC? Antonio Vte. Molines Martin
  • Si te un cost linial o proxim, cosa que podem apreciar si l'alçada es similar al nombre total de nodes, caldria equilibrarlo, en cas contrari, amb una altura propera o igual al logaritme en base 2 del nombre de nodes, el abre esta prou equilibrat i no cal fer operacions per equilibrarlo.
  • Qué és l'arrel d'un arbre? Aitana Villaplana
    • En un arbre, el l'únic node que no te pare.
  • Com busquem el succesor de un node en un arbre? Pilar Piqueres Matoses
  • Trobem generalment dos casos:
  • Cas 1: X té fill dret. Aleshores el successor de X serà el mínim extret del subproblema a partir del seu fill dret.
  • Cas 2: X no té fill dret. Aleshores haurem de buscar de qui és predecessor X, mirant l'últim node visitat durant la cerca de X.
  • A la hora de insertar en un árbol binario de búsqueda, ¿el orden importa? Murcia Serrano, Andrea
    • Sí, porque el árbol varía de forma según cómo se hayan insertado los elementos. Esto es relevante especialmente cuando hablamos de costes, donde podríamos tener hasta un coste lineal en el caso peor a la hora de buscar un elemento (por ejemplo, habiendo insertado los nodos en orden ascendente).
  • En que consisteix el métode inordre? I el postordre? Francesc Ferrer Pérez
      • La única diferéncia entre ambdós, es l'ordre dels passos, que son comuns. Al métode inordre, primer es visita le fill esquerre en inordre, després el node i per últim el dret, mentre que al metode postordre, es visita primer el fill esquerre en postordre, després el dret i últim el node. F
  • Com es representa un ABC amb llistes (ordenades) de fills? Pablo de Polonia Llopis
      • Amb un array representem tots els nodes de l'arbre (ordenats de menor a major).
      • Si la posició de l'array enllaça a una llista de nodes (nodes >= 1), estos representen els fills del node d'eixa posició.
      • S'utilitza null al final d'una llista per indicar que ja no hi han més fills d'eixe node.
      • Si la posició de l'array conté null, el node d'eixa posició es una fulla.
  • ¿Qué diferencia hay entre visitar todos los nodos de un árbol en preorden a postorden? Robert Muradyan
      • En preordre primero visitar el nodo, luego su hijo izquierdo y luego su derecho, estos dos último en preorden; en cambio en postordre visitas el hijo izquierdo y derecho en posorden respectivamente y luego el nodo.
  • Existeixen instancies significatives a les operacions amb arbres? De ser així, com poden variar els costos? Miguel Alejandro Muñoz Gil
      • Si. El millor cas el tenim als arbres balancejats, on els costos son d'ordre logn.
      • Mentre que el pitjor cas seríen el arbres degenerats, on trobaríem operacions d'ordre n.
      • On n és el número d'elements
  • En que consisteix l'estructura en l'arbre? Arnau Mompo Alepuz
  • En un conjunt relacions jeràrquiques entre els elements d'una colecció i cerques en temps sublineal.
  • Cúal es el número máximo de nodos en un árbol binario de altura H? ¿Y la altura mínima de un árbol binario con N nodos? Hugo Martínez Marcos
      • El número máximo de nodos es: 2h+1-1
      • La altura mínima es: log2n
  • Segons la seua definició recursiva, què pot ser un arbre? Jaume Murgui Gomez
  • Recursivament parlant, un arbre pot ser:
      • Un conjunt buit
      • Un node arrel P i zero o més subarbres no buits on les seues arrels son fills de P
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License