Tarjan's off-line lowest common ancestors algorithm

Not to be confused with Tarjan's strongly connected components algorithm.

In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure. The lowest common ancestor of two nodes d and e in a rooted tree T is the node g that is an ancestor of both d and e and that has the greatest depth in T. It is named after Robert Tarjan, who discovered the technique in 1979. Tarjan's algorithm is an offline algorithm; that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired must be specified in advance. The simplest version of the algorithm uses the union-find data structure, which unlike other lowest common ancestor data structures can take more than constant time per operation when the number of pairs of nodes is similar in magnitude to the number of nodes. A later refinement by Gabow & Tarjan (1983) speeds the algorithm up to linear time.

Pseudocode

The pseudocode below determines the lowest common ancestor of each pair in P, given the root r of a tree in which the children of node n are in the set n.children. For this offline algorithm, the set P must be specified in advance. It uses the MakeSet, Find, and Union functions of a disjoint-set data structure. MakeSet(u) removes u to a singleton set, Find(u) returns the standard representative of the set containing u, and Union(u,v) merges the set containing u with the set containing v. TarjanOLCA(r) is first called on the root r. 

function TarjanOLCA(u) is
    MakeSet(u)
    u.ancestor := u
    for each v in u.children do
        TarjanOLCA(v)
        Union(u, v)
        Find(u).ancestor := u
    u.color := black
    for each v such that {u, v} in P do
        if v.color == black then
            print "Tarjan's Lowest Common Ancestor of " + u +
                  " and " + v + " is " + Find(v).ancestor + "."

Each node is initially white, and is colored black after it and all its children have been visited.

For each node pair {u,v} to be investigated:

  • When v is already black (viz. when v comes before u in a post-order traversal of the tree): After u is colored black, the lowest common ancestor of this pair is available as Find(v).ancestor, but only while the LCA of u and v is not colored black.
  • Otherwise: Once v is colored black, the LCA will be available as Find(u).ancestor, while the LCA is not colored black.

For reference, here are optimized versions of MakeSet, Find, and Union for a disjoint-set forest: 

function MakeSet(x) is
    x.parent := x
    x.rank   := 1
 
function Union(x, y) is
    xRoot := Find(x)
    yRoot := Find(y)
    if xRoot.rank > yRoot.rank then
        yRoot.parent := xRoot
    else if xRoot.rank < yRoot.rank then
        xRoot.parent := yRoot
    else if xRoot.rank == yRoot.rank then
        yRoot.parent := xRoot
        xRoot.rank := xRoot.rank + 1
  
function Find(x) is
    if x.parent != x then
       x.parent := Find(x.parent)
    return x.parent

References

  • Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, doi:10.1145/800061.808753, ISBN 0-89791-099-0.

Read other articles:

Caterpie

CaterpieNomor PokédexNasional #010 Sebelumnya Selanjutnya Blastoise (#009) Metapod (#011) RegionalKanto#010Johto#024Hoenn#212Info produksiGenerasiI (Pertama) - 1996PerancangKen Sugimori Info Pokémon TipeseranggaSpesiesPokémon ulatKemampuanShield Dust (Debu Pelindung) Run Away (Kabur) – tersembunyiTinggi0,3 m (12 in)Berat2,9 kg (6,4 pon)Rasio gender 50% jantan  •  50% betina Evolusi CaterpieMetapodButterfree Nama da...

 

Gapan

Gapan component city (en) Tempat categoria:Articles mancats de coordenades Negara berdaulatFilipinaRegion di FilipinaLuzon TengahProvinsi di FilipinaNueva Ecija NegaraFilipina PendudukTotal122.968  (2020 )Tempat tinggal30.186  (2020 )Bahasa resmiKapampangan, Tagalog dan Bahasa Iloko GeografiLuas wilayah118 km² [convert: unit tak dikenal]Ketinggian41 m Berbatasan denganSan Leonardo SejarahPembuatan1732 Informasi tambahanKode pos3105 Zona waktuUTC+8 Kode telepon44 Lain-lainSitus...

 

فيكتوريانو لغويزامون

فيكتوريانو لغويزامون   معلومات شخصية الميلاد 23 مارس 1922  كونسيبسيون  تاريخ الوفاة 7 أبريل 2007 (85 سنة)   مركز اللعب لاعب وسط الجنسية باراغواياني المنتخب الوطني سنوات فريق مشاركات (أهداف) منتخب باراغواي لكرة القدم المواقع مُعرِّف موقع football-teams 63259  2 عدد مرات الظهور م...

Minnesota Territory

United States territory from 1849 to 1858, part of which became the state of Minnesota Territory of MinnesotaOrganized incorporated territory of the United StatesLocation of Minnesota Territory within the U.S. including U.S. state boundariesCapitalSt. PaulGovernment • TypeOrganized incorporated territoryGovernor • 1849–1853 Alexander Ramsey• 1853–1857 Willis A. Gorman• 1857–1858 Samuel Medary LegislatureMinnesota Territorial LegislatureHistory ...

 

Equatorial Counter Current

Shallow eastward flowing current found in the Atlantic, Indian, and Pacific Oceans Equatorial Counter Current (in black) The Equatorial Counter Current is an eastward flowing, wind-driven current which extends to depths of 100–150 metres (330–490 ft) in the Atlantic, Indian, and Pacific Oceans. More often called the North Equatorial Countercurrent (NECC), this current flows west-to-east at about 3-10°N in the Atlantic, Indian Ocean and Pacific basins, between the North Equatorial Cu...

 

List of United States Supreme Court cases, volume 123

Supreme Court of the United States38°53′26″N 77°00′16″W / 38.89056°N 77.00444°W / 38.89056; -77.00444EstablishedMarch 4, 1789; 235 years ago (1789-03-04)LocationWashington, D.C.Coordinates38°53′26″N 77°00′16″W / 38.89056°N 77.00444°W / 38.89056; -77.00444Composition methodPresidential nomination with Senate confirmationAuthorized byConstitution of the United States, Art. III, § 1Judge term lengthl...

Uncial 076

NaskahUncial 076TeksKisah Para Rasul 2WaktuAbad ke-5/ke-6Aksarabahasa YunaniKini diPierpont Morgan LibraryUkuran17 x 15 cmJenisTeks AlexandriaKategoriII Uncial 076 (dalam penomoran Gregory-Aland), α1008 (von Soden); adalah sebuah naskah kuno yang memuat sebagian Perjanjian Baru di Alkitab Kristen, khususnya Kisah Para Rasul. Ditulis dalam gaya tulisan uncial dalam bahasa Yunani, berdasarkan Paleografi diperkirakan dibuat pada abad ke-5 atau ke-6. Dahulunya diberi label יa.[1] P...

 

Esoterisme Barat

Pohon kehidupan seperti yang diwakili dalam Kabbalah, mencantumkan Sefirot. Esoterisme Barat atau tradisi misteri Barat,[1] adalah sebuah istilah yang dikategorisasikan oleh para cendekiawan terhahadap sejumlah besar gagasan dan gerakan terkait yang berkembang dalam masyarakat Barat. Gagasan dan gelombang tersebut disatukan oleh fakta bahwa mereka banyak berbeda dari agama Yudeo-Kristen ortodoks dan dari rasionalisme Abad Pencerahan. Referensi ^ Brian Morris, Religion and Anthropology...

 

Pasir Mas (town)

This article uses bare URLs, which are uninformative and vulnerable to link rot. Please consider converting them to full citations to ensure the article remains verifiable and maintains a consistent citation style. Several templates and tools are available to assist in formatting, such as reFill (documentation) and Citation bot (documentation). (August 2022) (Learn how and when to remove this message) Town and district capital in Kelantan Darul Naim, MalaysiaPasir Mas Pase MahTown and distric...

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国 フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期） フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

 

أتراك

هذه المقالة عن المجموعة العرقية الأتراك وليس عن من يحملون جنسية الجمهورية التركية أتراكTürkler (بالتركية) التعداد الكليالتعداد 70~83 مليون نسمةمناطق الوجود المميزةالبلد  القائمة ... تركياألمانياسورياالعراقبلغارياالولايات المتحدةفرنساالمملكة المتحدةهولنداالنمساأسترالي�...

 

La Passione (2010 film)

2010 Italian comedy film La PassioneFilm posterDirected byCarlo MazzacuratiWritten byUmberto ContarelloDoriana LeondeffCarlo MazzacuratiMarco PettenelloProduced byDomenico ProcacciStarring Silvio Orlando Giuseppe Battiston Kasia Smutniak Marco Messeri Maria Paiato Fausto Russo Alesi Cristiana Capotondi Stefania Sandrelli Corrado Guzzanti CinematographyLuca BigazziMusic byCarlo Crivelli , Orchestra Citta Aperta conducted by Robin O'NeilProductioncompanyFandangoRelease dates 3 September...

Szaszor

Orla coat of arms. Szaszor, also known as Saszor, is a heraldic charge in the shape of headless eagle.[1][2] Usage It was used in the Orla and Saszow coat of arms of heraldic clans of Poland.[1] It is also used in the coat of arms and flag of the municipality of Rędziny, Silesian Voivodeship, Poland.[3] Gallery Saszow coat of arms of the House of Szaszowski. Coat of arms of Gmina Rędziny. References ^ a b Alfred Znamierowski, Heraldyka i weksylologia. p. 392....

 

Raiden (Metal Gear)

Character in Metal Gear Fictional character RaidenMetal Gear characterRaiden as depicted in Metal Gear Rising: Revengeance.First appearanceMetal Gear Solid 2: Sons of Liberty (2001)Created byHideo KojimaDesigned byYoji ShinkawaVoiced byQuinton FlynnCharlie Schlatter (MGS3 Secret Theater)Kenyu Horiuchi (Japanese)Motion captureEiji Morisaki (MGS2) Takeshi Yoshioka (MGS4)In-universe informationNationalityLiberian-American[1] Raiden (Japanese: 雷電), real name Jack (ジャック, Jakku)...

 

Gustavo Adolfo Bécquer

Spanish poet and writer (1836–1870) Not to be confused with Gustavo Adolfo Becker. 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. (October 2009) (Learn how and when to remove this message) In this Spanish name, the first or paternal surname is Domínguez and the second or maternal family name is Bastida. Gustavo Adolfo BécquerGustavo Adolfo Bécque...

Pascale Trinquet

French fencer (born 1958) Pascale TrinquetPascale Trinquet in 1982Personal informationBorn (1958-08-11) 11 August 1958 (age 65)Marseille, FranceSportSportFencing Medal record Women's fencing Representing  France Olympic Games 1980 Moscow Individual foil 1980 Moscow Team foil 1984 Los Angeles Team foil Pascale Trinquet (born 11 August 1958 in Marseille) is a French fencer and Olympic champion in foil competition. She won a gold medal in the foil event at the 1980 Summer Olympics in M...

 

Monologue

Speech presented by a single character For the Soviet film, see Monologue (film). For the Malayalam film, see Anantaram. For the speech of a narrator, see Voiceover. Actor Christopher Walken performing a monologue in the 1984 stage play Hurlyburly In theatre, a monologue (from Greek: μονόλογος, from μόνος mónos, alone, solitary and λόγος lógos, speech) is a speech presented by a single character, most often to express their thoughts aloud, though sometimes also to directl...

 

Accounting and Corporate Regulatory Authority

Statutory board under ministry of finance in Singapore Accounting and Corporate Regulatory AuthorityAgency overviewFormed1 April 2004; 20 years ago (2004-04-01)Preceding agenciesRegistry of Companies and BusinessesPublic Accountants’ BoardJurisdictionGovernment of SingaporeHeadquarters55 Newton Road, #03-02 Revenue House, Singapore 307987Agency executivesOng Chong Tee, Chairman[1]Ong Khiaw Hong, Chief Executive[2]Parent agencyMinistry of FinanceWebsitewww.a...

Bryant's Minstrels

19th-century blackface minstrel troupe in New York City Detail from a playbill for Bryant's Minstrels, Mechanics' Hall, New York, 4 April 1859 (the première of the song Dixie) Bryant's Minstrels was a blackface minstrel troupe that performed in the mid-19th century, primarily in New York City. The troupe was led by the O'Neill brothers from upstate New York, who took the stage name Bryant.[1] History The eldest brother Jerry, a veteran of the Ethiopian Serenaders, Campbell's Minstrel...

 

Unione Sportiva Triestina Calcio 1997-1998

Questa voce sull'argomento stagioni delle società calcistiche italiane è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Voce principale: Unione Sportiva Triestina. Unione Sportiva Triestina CalcioStagione 1997-1998La formazione della Triestina, schierata prima della semifinale play-off, contro la Pro Patria. Sport calcio Squadra Triestina Allenatore Giuseppe Marchioro poi Paolo Beruatto Presidente...