Kinetisk turnering

Kinetisk turneringsöversikt

En kinetisk turnering är en kinetisk datastruktur som fungerar som en prioritetskö för element vars prioriteringar ändras som en kontinuerlig funktion av tiden. Det implementeras analogt med en "turnering" mellan element för att avgöra "vinnaren" (högsta eller lägsta elementet), med certifikaten som framtvingar vinnaren av varje "match" i turneringen. Den stöder de vanliga prioriterade köoperationerna - infoga , ta bort och find-max . De används ofta som komponenter i andra kinetiska datastrukturer, såsom kinetic closest pair .

Genomförande

En kinetisk turnering är organiserad i en binär trädliknande struktur, där löven innehåller elementen, och varje inre nod innehåller de större (eller mindre) av elementen i sina undernoder . Således innehåller trädets rot det maximala (eller minimum) elementet vid en given tidpunkt. Giltigheten av strukturen upprätthålls genom att skapa ett certifikat vid varje nod, som hävdar att elementet i noden är det största av de två barnen. När detta certifikat misslyckas ändras elementet vid noden (för att vara elementet i det andra underordnade) och ett nytt certifikat som representerar den nya invarianten skapas. Om elementet denna nod var en vinnare vid sin överordnade nod måste elementet och certifikaten hos den överordnade också uppdateras rekursivt.

Analys

Detta är en O( n ) utrymme, lyhörd, lokal, kompakt och effektiv datastruktur.

• Lyhördhet : Ett certifikatfel kommer att göra att ett nytt certifikat ersätts av det gamla, som måste läggas i händelsekön . Det kan också utlösa ändringar av O(log n )-certifikaten vid dess överordnade noder. Varje certifikatändring kräver en raderings- och infogningsoperation i den prioriterade händelsekön. Var och en av dessa tar O(log n ) tid, så responsen, den totala tiden som krävs för att bearbeta ett certifikatfel, är $O(\lg ^{2}n)$ . Även om detta anses vara lyhört i allmänhet är det mindre känsligt än andra kinetiska prioritetsköer såsom kinetiska högar som svarar på certifikatfel med O(1) certifikatändringar.
• Lokalitet : Varje element är inblandat i O(log n )-certifikat (till exempel är det maximala elementet involverat i ett certifikat vid var och en av dess föräldrar hela vägen upp till rotnoden). Återigen, även om detta anses vara lokalt, är en kinetisk hög mycket mer lokal.
• Kompakthet : Detta är en mycket kompakt struktur, som innehåller O( n )-certifikat - exakt ett för varje kant i trädet.
• Effektivitet : Kinetiska högar är mycket effektiva, med antalet interna händelser (certifikatändringar) är bara en faktor O(log n ) mer än antalet externa händelser . Specifikt, för en samling av rymd-tidsbanor där varje par skär högst s gånger, bearbetar den kinetiska turneringen O(λ _s+2 log n ) händelser i O(λ _s+2 log ² n ) tid, där λ _{s+ 2} är en Davenport-Schinzel-sekvens . Dessutom orsakar infogning och radering O(log n ) certifikatändringar var och en. Varje certifikatändring tar O(log n )-tid, vilket bestäms av den tid som krävs för att utföra händelseköuppdateringen.

• Basch, J. 1999. Kinetiska datastrukturer. Ph.D. avhandling, Institutionen för datavetenskap, Stanford University. [1]