[Powered by Google Translate] Com representar tots els membres de la seva família en un ordinador? Podríem simplement utilitzar una llista, però hi ha una jerarquia clara aquí. Diguem que estem començant amb la seva besàvia, Alice. Té 2 fills, Bob i el seu avi, Charlie. Charlie té 3 fills, seu oncle, Dave, la seva tia, Eva i el seu pare, Fred. Vostè és fill únic de Fred. Per què l'organització dels membres de la família d'aquesta manera ser millor que la representació simple llista? Una raó és que aquesta estructura jeràrquica, anomenat un "arbre", conté més informació que una simple llista. Sabem que les relacions familiars entre tots simplement mitjançant l'examen de l'arbre. A més, es pot accelerar look-up temps tremendament, si les dades de l'arbre està ordenat. No podem prendre avantatge d'això aquí, però anem a veure un exemple d'això aviat. Cada persona està representat per un node a l'arbre. Els nodes poden tenir nodes secundaris així com un node pare. Aquests són els termes tècnics, fins i tot quan s'utilitzen els arbres per coses més de les famílies. Node d'Alicia té 2 fills i els pares no, mentre que el node de Charlie té 3 fills i els pares 1. Un node fulla és un que no té fills en la vora exterior de l'arbre. El node superior de l'arbre, el node arrel, no té pare. Un arbre binari és un tipus específic d'arbre, en el qual cada node té, com a màxim, 2 nens. Aquí està l'estructura d'un node d'un arbre binari en C. Cada node té algunes dades associats amb ell i 2 punters a altres nodes. En el nostre arbre genealògic, les dades associades era el nom de cada persona. Aquí és un int, encara que podria ser qualsevol cosa. Doncs resulta que, un arbre binari no seria una bona representació per a una família, ja que les persones solen tenir més de 2 fills. Un arbre binari de cerca és un tipus especial d'arbre binari ordenat que ens permet veure els valors ràpidament. Vostè pot haver notat que tots els nodes per sota de l'arrel d'un arbre és l'arrel d'un altre arbre, anomenat 'subarbre. Aquí, l'arrel de l'arbre és 6, i el seu fill, 2, és l'arrel d'un subarbre. En un arbre de recerca binari tots els valors d'un node és el subarbre dret són més grans que el valor del node. A continuació: 6. Doncs bé, els valors de subarbre esquerre d'un node són menors que el valor del node. Si hem de manejar valors duplicats, podem canviar qualsevol d'ells a una desigualtat solt, el sentit de valors idèntics poden caure ja sigui en el costat esquerre o dret, sempre que siguin coherents sobre això en tot. Aquest arbre és un arbre de cerca binària perquè segueix la regla. Així és com es veuria si convertíssim tots els nodes en estructures de C. Tingueu en compte que si un nen està desaparegut, el punter és nul. Com comprovar si 7 es troba en l'arbre? Partim des de l'arrel. El set és més gran que 6, de manera que si està en l'arbre, ha d'estar a la dreta. Llavors, és menys de 8, de manera que ha de ser l'esquerra. Aquí, hem trobat 7. Ara, anem a comprovar per 5. Cinc és inferior a 6, pel que ha d'estar a l'esquerra. Cinc és major que 2, per la qual cosa ha de ser correcte, i també és major que 4, per la qual cosa ha de ser la dreta de nou. No obstant això, no hi ha un nen aquí. El punter és nul. Això vol dir que 5 no és al nostre arbre. Podem buscar a l'arbre binari amb el codi: A cada node, es comprova si s'ha trobat el valor que es busca. Si no el troba, es determina si ha de ser i en l'esquerra o la dreta comprovar subarbre. Aquest cicle continuarà l'arbre fins que no hi ha cap node fill a l'esquerra o la dreta. Recordi que 5 no estava en l'arbre. Com s'insereix? El procés és similar a recerca. Ens iterar l'arbre a partir de 6, esquerra a 2, dret a 4, ia la dreta de nou, però 4 no té fills en aquest costat. Aquesta serà la nova posició de 5, i s'iniciarà sense fills. A quina velocitat són operacions en un arbre de cerca binària? Recordi que Bigohnotation busca proporcionar un límit superior. En el pitjor dels casos, nostre arbre podria ser simplement una llista enllaçada el que significa que la inserció, deleció, i recerca podria prendre un temps proporcional al nombre de nodes en l'arbre. Això és O (n). Per exemple, el següent és un arbre binari de cerca vàlid. No obstant això, si tractem de trobar 9, hem de travessar cada node. No és més que una llista enllaçada. L'ideal seria que cada node del nostre arbre de cerca binària per tenir 2 fills. D'aquesta manera, inserció, eliminació i recerca prendria, en el pitjor, O (log n) temps. L'arbre de davant podria ser més equilibrada, com aquesta. Ara, mirant cap amunt pren qualsevol valor, com a màxim, 3 passos. Aquest arbre està equilibrat, significat que disposi d'un mínim de profunditat en relació amb el nombre de nodes. Busca un valor en un arbre binari de recerca equilibrat és similar a la recerca binària en un arranjament ordenat. De fet, si no és necessari inserir o eliminar elements, es comporten exactament de la mateixa manera. No obstant això, una estructura d'arbre és millor per les insercions i delecions de manipulació El meu nom és Bannus Van der Kloot. Això és CS50.