6. fejezet - fejezet Dinamikus halmazok

A számítástudományban gyakran használjuk a halmazokat. Az algoritmusok futása közben ezek a halmazok változhatnak, bővülhetnek, zsugorodhatnak. Rendszerint egy elem halmazba szúrására, adott elem törlésére, illetve arra van szükség, hogy eldöntsük, egy elem eleme-e a halmaznak. Az adataink/rekordjaink általában tartalmaznak egy kulcsmezőt, s esetleg kiegészítő adatokat. A most ismertetésre kerülő algoritmusokban a kiegészítő adatokat nem vesszük figyelembe, csak a kulcsmezőre, annak értékére összpontosítunk. A kulcsmezők lehetséges értékei egy teljesen rendezett halmazból származnak. Erre azért van szükségünk, hogy két tetszőleges értéket összehasonlíthassunk. Az itt használt jelölést a XII. fejezet írja le.

6.1. Műveletek típusai

A dinamikus halmazokon a következő módosító műveleteket végezhetjük:

– BESZÚR(S,x) az S halmazt bővítjük az x elemmel.

– TÖRÖL(S,x) az S halmazból töröljük az x elemet.

A dinamikus halmazokon a következő lekérdező műveleteket végezhetjük:

– KERES(S,x) az S halmazban megadja az x elem helyét, ha az a halmaznak eleme.

– MINIMUM(S) az S halmaz minimális elemének a helyét adja meg.

– MAXIMUM(S) az S halmaz maximális elemének a helyét adja meg.

– KÖVETKEZŐ (S,x) megadja az S halmaz azon elemének a helyét adja meg, amely a rendezés alapján követi az x elemet.

– ELŐ ZŐ (S,x) megadja az S halmaz azon elemének a helyét adja meg, amely a rendezés alapján megelőzi az x elemet.