Arbre (estructura de dades)

Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat.

En informàtica, un arbre és una estructura de dades jeràrquica que conté una col·lecció d'elements distribuïts en nodes enllaçats. Tots els nodes tenen almenys un únic node anomenat pare o ascendent, excepte un únic node que no té node pare que anomenen arrel i que és el punt de partida de tot l'arbre. Al seu torn, cada node pot tenir zero o més nodes anomenats fills o descendents. A més, els nodes fills d'un determinat node tenen un ordre determinat entre ells. Tots els nodes han de poder-se abastar des del node arrel seguint els enllaços dels nodes fills.

A les implementacions, els nodes sempre tenen referències als seus nodes fills, però no sempre al seu únic node pare.

Matemàticament es tracta d'un graf acíclic (sense cicles) i connex (tots els nodes són connectats).

Per convenció es parla de:

  • El node arrel és l'únic node que no té pare.
  • Un node terminal o node fulla és un que no té cap fill.
  • Un node intern o node branca és un qualsevol que no sigui ni arrel ni fulla, és a dir, que té pare i que almenys té un fill.
  • La fondària o nivell d'un node és el nombre d'enllaços que cal passar des del node arrel fins a aquest node. Per convenció -1 és la fondària d'un arbre buit, i 0 és la fondària d'un arbre amb un únic node arrel sol.
  • Un subarbre és la part d'un arbre que penja d'un node determinat si el prenguéssim com a node arrel, és a dir l'arbre format pel node i tots els seus descendents recursivament. Com a cas especial, el subarbre del node arrel és el mateix arbre sencer.

L'acció de recórrer els nodes de l'arbre (walking the tree) es pot fer aplicant diferent criteris:

  • Pre-ordre o en ordre anterior, o primer en fondària (en anglès depth-first-search o DFS): per cada node primer tractar el node i després recórrer cada un dels subarbres fills.
  • Post-ordre o en ordre posterior: per cada node primer recórrer cada un dels subarbres fills i després tractar el node.
  • En ordre de nivell, o primer en amplada (en anglès breadth-first-search o BFS): es recorren successivament tots els nodes de cada nivell, i a continuació es passa al nivell següent.

La majoria d'operacions que es fan sobre un arbre comencen pel node arrel, especialment en implementacions d'algorismes recursius.

Un arbre simple desordenat

Les operacions habituals que ha d'implementar un arbre són:

Les habituals dels contenidors (vegeu l'article contenidor):

  • Una operació per comprovar quan un arbre està buit
  • Una operació per obtenir el nombre d'elements de l'arbre

Les específiques d'un arbre:

  • Un constructor que crea un nou arbre buit
  • Una operació per obtenir el nombre de nivells de l'arbre
  • Una operació per trobar el node arrel de l'arbre
  • Algun mètode recursiu per recórrer tots els nodes de l'arbre, sigui pre-ordre, post-ordre, o en ordre de nivell
  • Una operació per trobar el nivell d'un node determinat
  • Una operació per trobar cada un dels nodes ascendents d'un node determinat
  • Una operació per cercar un element d'un valor determinat
  • Una operació per afegir un nou element en una posició concreta de l'arbre, potser rebalancejant l'arbre
  • Una operació per eliminar un nou element, potser rebalancejant l'arbre
  • Una operació per eliminar un subarbre, operació també anomenada podar (pruning)
  • Una operació per afegir tot un subarbre en una posició concreta de l'arbre, operació també anomenada empeltar (grafting)
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Arbre

Read other articles:

Francesco Lodi

Francesco Lodi Informasi pribadiTanggal lahir 23 Maret 1984 (umur 39)Tempat lahir Napoli, ItaliaTinggi 1,83 m (6 ft 0 in)Posisi bermain GelandangInformasi klubKlub saat ini Parma(pinjaman dari Catania)Nomor 21Karier junior EmpoliKarier senior*Tahun Tim Tampil (Gol)2000–2010 Empoli 89 (19)2004 → Vicenza (pinjaman) 11 (0)2006–2008 → Frosinone (pinjaman) 82 (31)2009–2010 → Udinese (pinjaman) 19 (1)2010–2011 Frosinone 23 (7)2011– Catania 105 (20)2013–2014 �...

 

Postal codes in France

Overview of postal codes in France This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Postal codes in France – news · newspapers · books · scholar · JSTOR (January 2009) (Learn how and when to remove this template message) Postal codes were introduced in France in 1964, when La Poste introduced automated sortin...

 

The Perfect Husband

The Perfect HusbandSutradaraRudi AryantoProduserSukhdev SinghWicky V. OlindoSkenarioSukhdev SinghTisa TSBenni SetiawanBerdasarkannovel The Perfect Husbandkarya Indah RiyanaPemeran Dimas Anggara Amanda Rawles Maxime Bouttier Slamet Rahardjo Tanta Ginting Bunga Zainal Maya Wulan Dolly Martin Ade Yunita Claudy Putri Maudy Effrosina Carmela Van der Kruk Penata musikJoseph S. DjafarSinematograferRoy LolangPenyuntingWawan I. WibowoPerusahaanproduksiScreenplay FilmsLegacy PicturesDistributorSc...

Sutter Creek, California

City in California, United States City in California, United StatesSutter CreekCityA view of Main Street (Old Highway 49) in Sutter Creek.Nickname: Jewel of the gold countryLocation in Amador CountySutter CreekLocation in CaliforniaShow map of CaliforniaSutter CreekSutter Creek (the United States)Show map of the United StatesCoordinates: 38°23′35″N 120°48′09″W / 38.39306°N 120.80250°W / 38.39306; -120.80250Country United StatesState Californi...

 

Namada Chilume

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Namada Chilume – news · newspapers · books · scholar · JSTOR (December 2019) (Learn how and when to remove this template message) Place in Karnataka, IndiaNamada chilumeCountry IndiaStateKarnatakaDistrictTumkuruLanguages • OfficialKannadaTime z...

 

Dimaro

Dimaro Frazioneabolished municipality in Italy (en) Dimaro (it) Tempat Negara berdaulatItaliaRegion otonom dengan status khususTrentino-Tirol SelatanProvinsi di ItaliaTrentinoCommune di ItaliaDimaro Folgarida (en) NegaraItalia Ibu kotaDimaro PendudukTotal1.298  (2015 )GeografiLuas wilayah27,77 km² [convert: unit tak dikenal]Ketinggian766 m Berbatasan denganCommezzadura Malè Monclassico Pinzolo Ragoli Tuenno Cles SejarahSanto pelindungLaurensius Informasi tambahanKode pos38025 Zona...

Homosexualités et socialisme

Pour les articles homonymes, voir HES. Homosexualités et socialismeHistoireFondation 1983CadreType Organisation à but non lucratif, LGBT wingForme juridique Association déclaréeDomaines d'activité LGBT, socialisme, autres organisations fonctionnant par adhésion volontairePays  FranceOrganisationFondateur Jan-Paul PouliquenPrésident Sophie RoquesAffiliation Parti socialisteSite web hes.lgbtIdentifiantsRNA W751064672SIREN 490324951modifier - modifier le code - modifier Wikidata Hom...

 

Italia

Para otros usos de este término, véase Italia (desambiguación). República ItalianaRepubblica Italiana  (italiano) Estado miembro de la Unión EuropeaBandera Emblema nacional Himno: Il Canto degli Italiani(en italiano: «El canto de los italianos») ¿Problemas al reproducir este archivo?      Italia     Resto de la Unión Europea     Resto de EuropaCapital(y ciudad más poblada) Roma 41°53′35″N 12°28′58″E...

 

Phipps v Pears

United Kingdom court case about land law Phipps v PearsWalls damaged by weather damage.CourtCourt of AppealFull case nameGeorge Edward Phipps v Pears and others Decided10 March 1964Citation(s)[1964] EWCA Civ 3[1965] 1 QB 76Transcript(s)EWCA Civ 3Case historyPrior action(s)Appellant also lost at first instance.Subsequent action(s)None.Case opinionsHeld: But a right to protection from the weather (if it exists) is entirely negative. It is a right to stop your neighbour pulling down his own hous...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

 

Praise, my soul, the King of heaven

19th century Christian hymn Praise, my soul, the King of heavenHenry Francis LyteGenreHymnWritten1834TextHenry Francis LyteBased onPsalm 103Meter8.7.8.7.8.7MelodyLauda Anima by John Goss, Regent Square by Henry T. Smart John Goss Praise, my soul, the King of heaven is a Christian hymn. Its text, which draws from Psalm 103, was written by Anglican divine Henry Francis Lyte.[1] First published in 1834, it endures in modern hymnals to a setting written by John Goss in 1868, and remai...

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

 

國民陣線

国民阵线Barisan NasionalNational Frontباريسن ناسيونلபாரிசான் நேசனல்国民阵线标志简称国阵，BN主席阿末扎希总秘书赞比里署理主席莫哈末哈山总财政希山慕丁副主席魏家祥维纳斯瓦兰佐瑟古律创始人阿都拉萨成立1973年1月1日 (1973-01-01)[1]设立1974年7月1日 (1974-07-01)前身 联盟总部 马来西亚  吉隆坡 50480 秋傑区敦依斯迈路太子世贸中心（英�...

 

The Daily News (Batavia)

The Daily NewsBatavia Daily News, December 16, 1880TypeDaily newspaper, except Sunday, MondayFormatBroadsheetOwner(s)Johnson Newspaper CorporationPublisherMichael MesserlyEditorBen BeagleFoundedJune 25, 1878LanguageAmerican EnglishHeadquartersBatavia, New YorkCountryUnited StatesCirculation7,758 (as of 2017)[1]ISSN1536-6901OCLC number9659012 Websitethedailynewsonline.comMedia of the United StatesList of newspapers The Daily News is an American, English language newspaper serving B...

Sagan (ceremony)

Sukunda oil lamp made of silver Serving rice wine during Sagan, note egg and smoked fish in left hand Sagun (Nepali: सगन) is a Nepalese ceremony which involves ritualized presentation of auspicious food to a person to invoke good fortune and show respect. It is a highly revered ceremony in Newar society of the Kathmandu Valley. The food items served are boiled egg, smoked fish, meat, lentil cake and rice wine which represent Tantric concepts.[1] The Sagan is presented during lif...

 

Gelnhausen

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (April 2013) (Learn how and when to remove this message) Town in Hesse, GermanyGelnhausen TownView of Gelnhausen with the Marienkirche Coat of armsLocation of Gelnhausen within Main-Kinzig-Kreis district Gelnhausen Show map of GermanyGelnhausen Show map of HesseCoordinates: 50°12′N 09°10′E / ...

 

Space Transportation System

Proposed system of reusable manned space vehicles This article is about the complete STS project. For the portion which survived to fruition, see Space Shuttle. This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (June 2011) (Learn how and when to remove this message) Space Transportation System, Integrated Program Plan1970 artist's concept illustrating use of a S...

1891 Brazilian presidential election

1891 Brazilian presidential election February 1891 1894 → Presidential election   Candidate Deodoro da Fonseca Prudente de Morais Electoral vote 129 97 Percentage 55.60% 41.81% President before election Deodoro da Fonseca (Provisional) Elected President Deodoro da Fonseca Vice-Presidential election   Candidate Floriano Peixoto Eduardo Wandenkolk Electoral vote 153 57 Percentage 65.95% 24.57% Vice president before election None Elected Vice president Floriano Pe...

 

Capitano

Disambiguazione – Se stai cercando altri significati, vedi Capitano (disambigua). Capitano è un grado militare di molte forze armate e corpi di polizia del mondo. Inoltre, fino al 31 dicembre 2007, quella di capitano di lungo corso era la denominazione del titolo professionale marittimo sul certificato di competenza, documento indispensabile per chi ambiva a poter esercitare il comando di una nave civile ovvero mercantile. Il termine deriva dal latino capitanu(m), da căput, capo. In tutt...