Author: Matti Meriläinen

# Puun funktioiden esittelyt

Puuta voidaan käsitellä yleisen puun avulla tietämättä puun oikeaa tyyppiä. Kuitenkin usein tarvitaan listoja jotka sisältävät jotakin määrätyntyyppistä tietoa. Mahdollisimman erityyppisten tilanteiden kattavuuden vuoksi tietorakennekirjastoa varten on toteutettu neljä erilaista tyypitettyä puutyyppiä : kokonaislukupuu, joka sisältää int / integer - arvoja, liukulukupuu (sisältää float / real - tyyppistä tietoa), merkkijonopuu (char* / string[ ]) ja osoitinpuu (void* / pointer - tyyppistä tietoa).

Tässä osassa on esitelty yleisen-, kokonaisluku-, liukuluku- ja merkkijonopuun funktiot. Osoitinpuusta enemmän osuudessa "Kirjaston laajentaminen". Funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että puu on määritelty. Mikäli parametrina annettava puu T on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin TREE_CREATE:a joka määrittelee puun. Samoin oletetaan solmujen kohdalla.

- TREE_CREATE (T, D)
- TREE_RETRIEVE (T, N)
- TREE_PRINT (T)
- TREE_ROOT(T)
- TREE_PARENT(T,N)
- TREE_LEFTMOST_CHILD(T,N)
- TREE_RIGHT_SIBLING(T,N)
- TREE_FREE (T)
- TREE_ASSIGN_ROOT(T,N)
- TREE_ASSIGN_LEFTMOST_CHILD(T,ND,NS)
- TREE_ASSIGN_RIGHTSIBLING(T,ND,NS)
- TREE_CREATE_NODE(x)
- TREE_DESTROY_NODE(T,N)
- TREE_PRINT_NODE(T,N)
- TREE_NODE_BALANCE(N)
- TREE_NODE_SET_BALANCE(N,B)
- TREE_CONSTRUCT_RANDOM (T, count, min, max)
- TREE_TYPE (T)
- TREE_LESS (T, x, y)
- TREE_SAME (T, x, y)
- TREE_EMPTY (T)

Yleisen puun käsittely

> Yleisen puun funktioita tarvitaan silloin, kun pitää käsitellä puuta, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä puuta luotaessa määritellään puun tyyppi kuvaajan DESCRIPTOR avulla. Funktio TREE_TYPE(T) palauttaa puun T kuvaajan jota voidaan käyttää puuta luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten puun alkioita vertaillaan, käsitellään ja tulostetaan.

Int / integer - puun käsittely

> Kokonaislukupuun esittelyissä käytetään kokonaislukutyyppinä tyypinmäärittelyä INT_TYPE, joka on toteutuskohtaisesti määritelty. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (max. 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (2^32).

Float / real - puun käsittely

> Liukulukupuun esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukupuun kohdalla.

Char* / string[ ] - puun käsittely

> Merkkijonopuun tyyppinä on C:ssä char*, osoitin merkkijonoon. Pascalissa tyyppinä on string, jonka maksimipituus on vakio RANDOM_STR_MAX, cs:llä 16 merkkiä.

## Funktioiden esittelyt

TREE_CREATE (T, D)

> void TREE_CREATE (TREE T, DESCRIPTOR D);

> void INT_TREE_CREATE(TREE T);

> void FLOAT_TREE_CREATE(TREE T);

> void CHARP_TREE_CREATE(TREE T);

> void VOIDPTR_TREE_CREATE(TREE T);

> procedure TREE_CREATE (var T:TREE; D:DESCRIPTOR);

> procedure INT_TREE_CREATE (var T:TREE);

> procedure FLOAT_TREE_CREATE (var T:TREE);

> procedure CHARP_TREE_CREATE (var T:TREE);

> procedure VOIDPTR_TREE_CREATE(var T:TREE);

Yleinen TREE_CREATE(T, D) muodostaa tyhjän puun T, ja asettaa puun kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDP_DESC}. Mikäli puu T ei ole tyhjä puu, kaikki puussa ollut tieto menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan puun T. Esimerkki : Pascal / C

Aikavaativuus : O(1)

TREE_RETRIEVE (T, N)

> ELEMENT TREE_RETRIEVE (TREE T, TREE_NODE N);

> INT_TYPE INT_TREE_RETRIEVE (TREE T, TREE_NODE N);

> FLOAT_TYPE FLOAT_TREE_RETRIEVE (TREE T, TREE_NODE N);

> CHARP_TYPE CHARP_TREE_RETRIEVE (TREE T, TREE_NODE N);

> function TREE_RETRIEVE (T:TREE; N:TREE_NODE) : ELEMENT;

> function INT_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : INT_TYPE;

> function FLOAT_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : FLOAT_TYPE;

> function CHARP_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : CHARP_TYPE;

> function VOIDPTR_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : pointer;

Palauttaa puun T solmun arvon. Yleinen puu palauttaa ELEMENT-tyypin, tyypitettyjen listojen funktiota palauttavat puun omaa tyyppiä olevan arvon. Jos p=TREE_EOL(T) tai solmua ei ole puussa, tulos on määrittelemätön.

Aikavaativuus : O(1)

TREE_PRINT (T)

> void TREE_PRINT (TREE T);

> procedure TREE_PRINT (T:TREE);

Tulostaa puun T kuvaajassa määritellyllä tavalla. Tyypitetyillä funktioilla ei ole eroa tämän toiminnan kanssa. Esimerkki : Pascal / C

Aikavaativuus : O(1)

TREE_ROOT(T)

> TREE_NODE TREE_ROOT (TREE T)

> TREE_NODE INT_TREE_ROOT(TREE T);

> TREE_NODE FLOAT_TREE_ROOT(TREE T);

> TREE_NODE CHARP_TREE_ROOT(TREE T);

> TREE_NODE VOIDPTR_TREE_ROOT(TREE T);

> function TREE_ROOT(T:TREE):TREE_NODE;

> function INT_TREE_ROOT(T:TREE):TREE_NODE;

> function FLOAT_TREE_ROOT(T:TREE):TREE_NODE;

> function CHARP_TREE_ROOT(T:TREE):TREE_NODE;

> function VOIDPTR_TREE_ROOT(T:TREE):TREE_NODE;

Palautetaan tunnussolmun 1. lapsi. Jos puu on tyhjä puu, palautetaan NULL.

Aikavaativuus : O(1)

TREE_PARENT(T,N)

> TREE_NODE TREE_PARENT (TREE T, TREE_NODE N);

> TREE_NODE INT_TREE_PARENT(TREE T, TREE_NODE N);

> TREE_NODE FLOAT_TREE_PARENT(TREE T, TREE_NODE N);

> TREE_NODE CHARP_TREE_PARENT(TREE T, TREE_NODE N);

> TREE_NODE VOIDPTR_TREE_PARENT(TREE T, TREE_NODE N);

> function TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

> function INT_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

> function FLOAT_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

> function CHARP_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

> function VOIDPTR_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

Palauttaa solmun vanhemman.

Aikavaativuus : O(1)

TREE_LEFTMOST_CHILD(T,N)

> TREE_NODE TREE_LEFTMOST_CHILD (TREE T, TREE_NODE N);

> TREE_NODE INT_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

> TREE_NODE FLOAT_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

> TREE_NODE CHARP_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

> TREE_NODE VOIDPTR_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

> function TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

> function INT_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

> function FLOAT_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

> function CHARP_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

> function VOIDPTR_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

Palauttaa solmun vanhimman lapsen.

Aikavaativuus : O(1)

TREE_RIGHT_SIBLING(T,N)

> TREE_NODE TREE_RIGHT_SIBLING (TREE T, TREE_NODE N);

> TREE_NODE INT_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

> TREE_NODE FLOAT_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

> TREE_NODE CHARP_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

> TREE_NODE VOIDPTR_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

> procedure TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

> procedure INT_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

> procedure FLOAT_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

> procedure CHARP_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

> procedure VOIDPTR_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

Palauttaa solmun seuraavan sisaruksen.

Aikavaativuus : O(1)

TREE_ASSIGN_ROOT(T,N)

> void TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

> void INT_TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

> void FLOAT_TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

> void CHARP_TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

> procedure TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

> procedure INT_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

> procedure FLOAT_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

> procedure CHARP_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

> procedure VOIDPTR_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

Asettaa puun T juurisolmuksi N:n. N:n tyypiksi tulee puun tyyppi.

Aikavaativuus : O(1)

TREE_ASSIGN_LEFTMOST_CHILD(T,ND,NS)

> void TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

> void INT_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

> void FLOAT_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

> void CHARP_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

> void VOIDPTR_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

> procedure TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS:TREE_NODE);

> procedure INT_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

> procedure FLOAT_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

> procedure CHARP_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

> procedure VOIDPTR_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

Asettaa solmun ND (node-destination) vanhimmaksi lapseksi solmun NS (node-source). NS:n tyypiksi tulee solmun ND tyyppi.

Aikavaativuus : O(1)

TREE_ASSIGN_RIGHT_SIBLING(T,ND,NS)

> void TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

> void INT_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

> void FLOAT_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

> void CHARP_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

> void VOIDPTR_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

> procedure TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND:TREE_NODE;NS:TREE_NODE);

> procedure INT_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

> procedure FLOAT_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

> procedure CHARP_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

> procedure VOIDPTR_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

Asettaa solmun ND seuraavaksi sisarukseksi solmun NS. NS:n tyypiksi tulee solmun ND tyyppi.

Aikavaativuus : O(1)

TREE_CREATE_NODE(x)

> TREE_NODE TREE_CREATE_NODE (ELEMENT x);

> TREE_NODE INT_TREE_CREATE_NODE(INT_TYPE x);

> TREE_NODE FLOAT_TREE_CREATE_NODE(FLOAT_TYPE x);

> TREE_NODE CHARP_TREE_CREATE_NODE(char* x);

> TREE_NODE VOIDPTR_TREE_CREATE_NODE(void* x);

> function TREE_CREATE_NODE(x:ELEMENT):TREE_NODE;

> function INT_TREE_CREATE_NODE(x:INT_TYPE):TREE_NODE;

> function FLOAT_TREE_CREATE_NODE(x:FLOAT_TYPE):TREE_NODE;

> function CHARP_TREE_CREATE_NODE(x:CHARP_TYPE):TREE_NODE;

> function VOIDPTR_TREE_CREATE_NODE(x:pointer):TREE_NODE;

Varaa tilaa uudelle solmulle, asettaa sen dataksi x:n ja palauttaa osoitteen luotuun solmuun. Tyyppi määrätään vasta puuhun vietäessä.

Aikavaativuus : O(1)

TREE_DESTROY_NODE (T,N)

> void TREE_DESTROY_NODE (TREE T, TREE_NODE N);

> void INT_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

> void FLOAT_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

> void CHARP_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

> void VOIDPTR_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

> procedure TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

> procedure INT_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

> procedure FLOAT_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

> procedure CHARP_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

> procedure VOIDPTR_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

Poistaa puusta T solmun N. Alkion poistamisen jälkeen puussa solmua N ja sitä seuraavien asemien tiedot vanhentuvat.

Aikavaativuus : O(1)

TREE_PRINT_NODE (T,N)

> void TREE_PRINT_NODE (TREE T, TREE_NODE N);

> procedure TREE_PRINT_NODE(T:TREE;N:TREE_NODE);

Tulostaa solmun N sisällön

Aikavaativuus : O(1)

TREE_NODE_BALANCE(N)

> BALANCETYPE TREE_NODE_BALANCE (TREE_NODE N);

> BALANCETYPE INT_TREE_NODE_BALANCE(TREE_NODE N);

> BALANCETYPE FLOAT_TREE_NODE_BALANCE(TREE_NODE N);

> BALANCETYPE CHARP_TREE_NODE_BALANCE(TREE_NODE N);

> BALANCETYPE VOIDPTR_TREE_NODE_BALANCE(TREE_NODE N);

> function TREE_NODE_BALANCE (N:TREE_NODE:BALANCETYPE;

> function INT_TREE_NODE_BALANCE (N:TREE_NODE: BALANCETYPE;

> function FLOAT_TREE_NODE_BALANCE (N:TREE_NODE: BALANCETYPE;

> function CHARP_TREE_NODE_BALANCE (N:TREE_NODE: BALANCETYPE;

> function VOIDPTR_TREE_NODE_BALANCE (N:TREE_NODE: BALANCETYPE;

Palauttaa tiedon solmun tasapainosta.

Aikavaativuus : O(1)

TREE_NODE_SET_BALANCE(N,B)

> void TREE_NODE_SET_BALANCE (TREE_NODE N, BALANCETYPE B);

> void INT_TREE_NODE_SET_BALANCE(TREE_NODE N, BALANCETYPE B);

> void FLOAT_TREE_NODE_SET_BALANCE(TREE_NODE N, BALANCETYPE B);

> void CHARP_TREE_NODE_SET_BALANCE(TREE_NODE N, BALANCETYPE B);

> void VOIDPTR_TREE_NODE_SET_BALANCE(TREE_NODE N, BALANCETYPE B);

> procedure TREE_NODE_SET_BALANCE(N:TREE_NODE; B:BALANCETYPE);

> procedure INT_TREE_NODE_SET_BALANCE(N:TREE_NODE; B:BALANCETYPE);

> procedure FLOAT_TREE_NODE_SET_BALANCE(N:TREE_NODE; B:BALANCETYPE);

> procedure CHARP_TREE_NODE_SET_BALANCE(N:TREE_NODE; B:BALANCETYPE);

> procedure VOIDPTR_TREE_NODE_SET_BALANCE(N:TREE_NODE; B:BALANCETYPE);

Asettaa solmun N tasapainoksi B:n.

Aikavaativuus : O(1)

Seuraavat aliohjelmat eivät ole välttämättömiä puun käytön kannalta, mutta helpottavat yleisten aliohjelmien tekemistä ja testaamista:

TREE_FREE (T)

> void TREE_FREE(TREE T);
> void INT_TREE_FREE(TREE T);

> void FLOAT_TREE_FREE(TREE T);

> void CHARP_TREE_FREE(TREE T);

> void VOIDPTR_TREE_FREE(TREE T);
> procedure TREE_FREE (var T:TREE);

> procedure INT_TREE_FREE (var T:TREE);

> procedure FLOAT_TREE_FREE (var T:TREE);

> procedure CHARP_TREE_FREE (var T:TREE);

> procedure VOIDPTR_TREE_FREE (var T:TREE);

Vapauttaa kaiken puun T varaaman tilan ja asettaa puun T määrittelemättömäksi puuksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila.Jos void*- tai char*-puussa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi puun tuhoamisen jälkeen, täytyy ennen TREE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta.Esimerkki 1 : Pascal / C

Aikavaativuus : O(n)

TREE_TYPE (T)

> DESCRIPTOR TREE_TYPE (TREE T);

> function TREE_TYPE (T:TREE) : DESCRIPTOR;

Palauttaa puun T kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen puu joudutaan luomaan. Uusi puu M, joka on samaa tyyppiä kuin puu T, luodaan komennolla TREE_CREATE(M, TREE_TYPE(T));.

Aikavaativuus : O(1)

TREE_LESS (T, x, y)

TREE_SAME (T, x, y)

> int TREE_LESS (TREE T, ELEMENT x, ELEMENT y);

> int TREE_SAME (TREE T, ELEMENT x, ELEMENT y);

> function TREE_LESS (T:TREE; x,y:ELEMENT) : boolean;

> function TREE_SAME (T:TREE; x,y:ELEMENT) : boolean;

Palauttavat tiedon siitä ovatko puun T määräämää tyyppiä olevat elementit x ja y samoja (SAME), tai onko x järjestyksessä ennen y:tä (LESS). Elementtien x ja y pitää olla samaa tyyppiä kuin puun T alkiot (muttei niiden ole pakko olla puun T alkioita). Jos x=y, niin TREE_SAME palauttaa siis TRUE (0), ja jos x<y niin TREE_LESS palauttaa FALSE (!=0). Merkkijonopuussa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

TREE_EMPTY (T)

> int TREE_EMPTY (TREE T);

> int INT_TREE_EMPTY(TREE T);

> int FLOAT_TREE_EMPTY(TREE T);

> int CHARP_TREE_EMPTY(TREE T);

> int VOIDPTR_TREE_EMPTY(TREE T);

> function TREE_EMPTY (T:TREE) : boolean;

> function INT_TREE_EMPTY (T:TREE) : boolean;

> function FLOAT_TREE_EMPTY (T:TREE) : boolean;

> function CHARP_TREE_EMPTY (T:TREE) : boolean;

> function VOIDPTR_TREE_EMPTY (T:TREE) : boolean;

Palauttaa tiedon siitä onko puu T tyhjä puu. C-kielessä palautusarvo on siis !=0, jos puu on tyhjä, ja 0 mikäli puu ei ole tyhjä. Pascalissa funktio palauttaa TRUE jos puu on tyhjä ja FALSE, jos puu ei ole tyhjä.

Aikavaativuus : O(1)