Binääripuun funktioiden esittelyt

Binääripuuta voidaan käsitellä yleisen puun tavoin tietämättä puun oikeaa tyyppiä. Kuitenkin tarvitaan puita jotka sisältävät jotakin määrätyntyyppistä tietoa. Mahdollisimman erityyppisten tilanteiden kattavuuden vuoksi tietorakennekirjastoa varten on toteutettu neljä erilaista tyypitettyä binääripuutyyppiä : 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. 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 BTREE_CREATE:a joka määrittelee puun. Samoin oletetaan puun solmujen kohdalla.

BTREE_CREATE (T, D)
BTREE_RETRIEVE (T, N)
BTREE_PRINT_NODE (T,N)
BTREE_DESTROY_NODE(T,N)
BTREE_TYPE (T)
BTREE_LESS (T, x, y)
BTREE_SAME (T, x, y)
BTREE_EMPTY (T)
BTREE_ROOT(T)
BTREE_PARENT(T,N)
BTREE_LEFTCHILD(T,N)
BTREE_RIGHTCHILD(T,N)
BTREE_ASSIGN_ROOT(T, N)
BTREE_CREATE_NODE(x)
BTREE_NODE_BALANCE(N)
BTREE_NODE_SET_BALANCE(N, B)
BTREE_ASSIGN_CHILD (T, ND, dir, NS)

Yleisen binääripuun käsittely

Yleisen binääripuun 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 BTREE_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 - binääripuun käsittely

Kokonaislukupuun esittelyissä käytetään kokonaislukutyyppinä tyypinmäärittelyä INT_TYPE, joka on määritelty toteutuskohtaisesti. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (enintään 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (enintään 2^32). Kaikki INT_BTREE_XXX - aliohjelmat voidaan lyhentää IB_XXX; INT_BTREE_CREATE(T) voidaan siis kutsua myös IB_CREATE(T).

Float / real - binääripuun käsittely

Liukulukubinääripuun esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukupuun kohdalla. FLOAT_BTREE_XXX voidaan lyhentää koodissa FB_XXX.

Char* / string[ ] - binääripuun 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ä. Kaikki CHARP_BTREE_XXX - aliohjelmat voidaan lyhentää koodissa CB_XXX.

Funktioiden esittelyt

BTREE_CREATE (T, D)
void BTREE_CREATE (BTREE T, DESCRIPTOR D);

void INT_BTREE_CREATE(BTREE T);

void FLOAT_BTREE_CREATE(BTREE T);

void CHARP_BTREE_CREATE(BTREE T);

void VOIDPTR_BTREE_CREATE(BTREE T);

procedure BTREE_CREATE (var T:BTREE; D:DESCRIPTOR);

procedure INT_BTREE_CREATE (var T:BTREE);

procedure FLOAT_BTREE_CREATE (var T:BTREE);

procedure CHARP_BTREE_CREATE (var T:BTREE);

procedure VOIDPTR_BTREE_CREATE(var T:BTREE);

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

Aikavaativuus : O(1)
BTREE_ROOT(T)
BTREE_NODE BTREE_ROOT (BTREE T);

BTREE_NODE INT_BTREE_ROOT (BTREE T);

BTREE_NODE FLOAT_BTREE_ROOT (BTREE T);

BTREE_NODE CHARP_BTREE_ROOT (BTREE T);

BTREE_NODE VOIDPTR_BTREE_ROOT (BTREE T);

function BTREE_ROOT (T:BTREE):BTREE_NODE;

function INT_BTREE_ROOT (T:BTREE):BTREE_NODE;

function FLOAT_BTREE_ROOT (T:BTREE):BTREE_NODE;

function CHARP_BTREE_ROOT (T:BTREE):BTREE_NODE;

function VOIDPTR_BTREE_ROOT(T:BTREE):BTREE_NODE;

Palauttaa puun T juurisolmun.. Jos binääripuu T on tyhjä puu, palautetaan BTREE_NIL.

Aikavaativuus : O(1)

BTREE_PARENT(T,N)
BTREE_NODE BTREE_PARENT (BTREE T, BTREE_NODE N);

BTREE_NODE INT_BTREE_PARENT (BTREE T, BTREE_NODE N);

BTREE_NODE FLOAT_BTREE_PARENT (BTREE T, BTREE_NODE N);

BTREE_NODE CHARP_BTREE_PARENT (BTREE T, BTREE_NODE N);

BTREE_NODE VOIDPTR_BTREE_PARENT(BTREE T, BTREE_NODE N);

function BTREE_PARENT (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function INT_BTREE_PARENT (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function FLOAT_BTREE_PARENT (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function CHARP_BTREE_PARENT (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function VOIDPTR_BTREE_PARENT(T:BTREE T; N:BTREE_NODE):BTREE_NODE;

Palauttaa solmun N vanhemman (isän).

Aikavaativuus : O(1)

BTREE_LEFTCHILD(T,N)

BTREE_NODE BTREE_LEFTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE INT_BTREE_LEFTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE FLOAT_BTREE_LEFTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE CHARP_BTREE_LEFTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE VOIDPTR_BTREE_LEFTCHILD(BTREE T, BTREE_NODE N);

function BTREE_LEFTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function INT_BTREE_LEFTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function FLOAT_BTREE_LEFTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function CHARP_BTREE_LEFTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function VOIDPTR_BTREE_LEFTCHILD(T:BTREE; N:BTREE_NODE):BTREE_NODE;

Palauttaa solmun N vasemmanpuoleisen lapsen.

Aikavaativuus : O(1)

BTREE_RIGHTCHILD(T,N)

BTREE_NODE BTREE_RIGHTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE INT_BTREE_RIGHTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE FLOAT_BTREE_RIGHTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE CHARP_BTREE_RIGHTCHILD (BTREE T, BTREE_NODE N);

BTREE_NODE VOIDPTR_BTREE_RIGHTCHILD(BTREE T, BTREE_NODE N);

function BTREE_RIGHTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function INT_BTREE_RIGHTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function FLOAT_BTREE_RIGHTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function CHARP_BTREE_RIGHTCHILD (T:BTREE; N:BTREE_NODE):BTREE_NODE;

function VOIDPTR_BTREE_RIGHTCHILD(T:BTREE; N:BTREE_NODE):BTREE_NODE;

Palauttaa solmun N oikeanpuoleisen lapsen.

Aikavaativuus : O(1)

BTREE_RETRIEVE(T,N)

ELEMENT BTREE_RETRIEVE (BTREE T, BTREE_NODE N);

INT_TYPE INT_BTREE_RETRIEVE(BTREE T, BTREE_NODE N);

FLOAT_TYPE FLOAT_BTREE_RETRIEVE(BTREE T, BTREE_NODE N);

char* CHARP_BTREE_RETRIEVE(BTREE T, BTREE_NODE N);

void* VOIDPTR_BTREE_RETRIEVE(BTREE T, BTREE_NODE N)

function BTREE_RETRIEVE (T:BTREE; N:BTREE_NODE):ELEMENT;

function INT_BTREE_RETRIEVE (T:BTREE; N:BTREE_NODE):INT_TYPE;

function FLOAT_BTREE_RETRIEVE (T:BTREE; N:BTREE_NODE):FLOAT_TYPE;

function CHARP_BTREE_RETRIEVE (T:BTREE; N:BTREE_NODE):CHARP_TYPE;

function VOIDPTR_BTREE_RETRIEVE(BTREE T, BTREE_NODE N):pointer;

Palautetaan puun T solmun N datan arvo.

Aikavaativuus : O(1)

BTREE_ASSIGN_ROOT(T,N)

void BTREE_ASSIGN_ROOT (BTREE T, BTREE_NODE N)

void INT_BTREE_ASSIGN_ROOT (BTREE T, BTREE_NODE N)

void FLOAT_BTREE_ASSIGN_ROOT (BTREE T, BTREE_NODE N)

void CHARP_BTREE_ASSIGN_ROOT (BTREE T, BTREE_NODE N)

procedure BTREE_ASSIGN_ROOT(T:BTREE; N:BTREE_NODE);

procedure INT_BTREE_ASSIGN_ROOT(T:BTREE; N:BTREE_NODE);

procedure FLOAT_BTREE_ASSIGN_ROOT(T:BTREE; N:BTREE_NODE);

procedure CHARP_BTREE_ASSIGN_ROOT(T:BTREE; N:BTREE_NODE);

procedure VOIDPTR_BTREE_ASSIGN_ROOT(T:BTREE; N:BTREE_NODE);

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

Aikavaativuus : O(1)

BTREE_ASSIGN_CHILD (T, ND, dir, NS)
void BTREE_ASSIGN_CHILD (BTREE T, BTREE_NODE ND, BTREE_DIR dir, BTREE_NODE NS);

void INT_BTREE_ASSIGN_CHILD (BTREE T, BTREE_NODE ND, BTREE_DIR dir, BTREE_NODE NS);

void FLOAT_BTREE_ASSIGN_CHILD (BTREE T, BTREE_NODE ND, BTREE_DIR dir, BTREE_NODE NS);

void CHARP_BTREE_ASSIGN_CHILD (BTREE T, BTREE_NODE ND, BTREE_DIR dir, BTREE_NODE NS);

void VOIDPTR_BTREE_ASSIGN_CHILD(BTREE T, BTREE_NODE ND, BTREE_DIR dir, BTREE_NODE NS);

procedure BTREE_ASSIGN_CHILD (T:BTREE; ND:BTREE_NODE, dir:BTREE_DIR, NS:BTREE_NODE);

procedure INT_BTREE_ASSIGN_CHILD (T:BTREE; ND:BTREE_NODE, dir:BTREE_DIR, NS:BTREE_NODE);

procedure FLOAT_BTREE_ASSIGN_CHILD(T:BTREE; ND:BTREE_NODE, dir:BTREE_DIR,NS:BTREE_NODE);

procedure CHARP_BTREE_ASSIGN_CHILD(T:BTREE; ND:BTREE_NODE;dir:BTREE_DIR,NS:BTREE_NODE);

procedureVOIDPTR_BTREE_ASSIGN_CHILD(T:BTREE;ND:BTREE_NODE;dir:BTREE_DIR;NS:BTREE_NODE);

Asettaa solmun ND lapseksi solmun NS. NS:n tyypiksi tulee solmun ND tyyppi. Binääripuun lapsen suunta määrätään tyyppiä BTREE_DIR olevalla muuttujalla. BTREE_DIR on lueteltu tyyppi { left, right }. Esimerkiksi BTREE_ASSIGN_CHILD (T,N1,left,N2) asettaa solmun N1 vasemmaksi lapseksi solmun N2.

Aikavaativuus : O(1)

BTREE_CREATE_NODE(x)

BTREE_NODE BTREE_CREATE_NODE (ELEMENT x)

BTREE_NODE INT_BTREE_CREATE_NODE(INT_TYPE x)

BTREE_NODE FLOAT_BTREE_CREATE_NODE(FLOAT_TYPE x)

BTREE_NODE CHARP_BTREE_CREATE_NODE(char* x)

BTREE_NODE VOIDPTR_BTREE_CREATE_NODE(void* x)

function BTREE_CREATE_NODE (x:ELEMENT):BTREE_NODE;

function INT_BTREE_CREATE_NODE (x:INT_TYPE):BTREE_NODE;

function FLOAT_BTREE_CREATE_NODE (x:FLOAT_TYPE):BTREE_NODE;

function CHARP_BTREE_CREATE_NODE (x:CHARP_TYPE):BTREE_NODE;

function VOIDPTR_BTREE_CREATE_NODE(x:pointer):BTREE_NODE;

Luo uuden solmun, asettaa sen dataksi x ja palauttaa luodun solmun. Solmun tyyppi määrätään vasta puuhun vietäessä.

Aikavaativuus : O(1)

BTREE_PRINT_NODE (T, N)
void BTREE_PRINT_NODE (BTREE T, BTREE_NODE N);

procedure BTREE_PRINT_NODE (T:BTREE; N:BTREE_NODE);

Tulostaa solmun N arvon puun T kuvaajassa määritellyllä tavalla.

Aikavaativuus : yksinkertaisille tyypeille O(1)

BTREE_DESTROY_NODE(T,N)
void BTREE_DESTROY_NODE(BTREE T, BTREE_NODE N);

void INT_BTREE_DESTROY_NODE(BTREE T, BTREE_NODE N);

void FLOAT_BTREE_DESTROY_NODE(BTREE T, BTREE_NODE N);

void CHARP_BTREE_DESTROY_NODE(BTREE T, BTREE_NODE N);

void VOIDPTR_BTREE_DESTROY_NODE(BTREE T, BTREE_NODE N);

procedure BTREE_DESTROY_NODE(T:BTREE; N:BTREE_NODE);

procedure INT_BTREE_DESTROY_NODE(T:BTREE; N:BTREE_NODE);

procedure FLOAT_BTREE_DESTROY_NODE (T:BTREE; N:BTREE_NODE);

procedure CHARP_BTREE_DESTROY_NODE (T:BTREE; N:BTREE_NODE);

procedure VOIDPTR_BTREE_DESTROY_NODE(T:BTREE, N:BTREE_NODE);

Vapauttaa kaiken solmun N varaaman tilan. Kaikki solmun N jälkeläiset muuttuvat operaation jälkeen määrittelemättömiksi.

Aikavaativuus : O(1)

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

BTREE_TYPE (T)
DESCRIPTOR BTREE_TYPE (BTREE T);

function BTREE_TYPE (T:BTREE) : DESCRIPTOR;

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

Aikavaativuus : O(1)

BTREE_LESS (T, x, y)

BTREE_SAME (T, x, y)
int BTREE_LESS (BTREE T, ELEMENT x, ELEMENT y);

int BTREE_SAME (BTREE T, ELEMENT x, ELEMENT y);

function BTREE_LESS (T:BTREE; x,y:ELEMENT) : boolean;

function BTREE_SAME (T:BTREE; 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 BTREE_SAME palauttaa siis TRUE (!=0), ja jos x<y niin BTREE_LESS palauttaa TRUE (!=0). Merkkijonopuussa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

BTREE_EMPTY (T)
int BTREE_EMPTY (BTREE T);

int INT_BTREE_EMPTY (BTREE T);

int FLOAT_BTREE_EMPTY (BTREE T);

int CHARP_BTREE_EMPTY (BTREE T);

int VOIDPTR_BTREE_EMPTY(BTREE T);

function BTREE_EMPTY (T:BTREE) : boolean;

function INT_BTREE_EMPTY (T:BTREE) : boolean;

function FLOAT_BTREE_EMPTY (T:BTREE) : boolean;

function CHARP_BTREE_EMPTY (T:BTREE) : boolean;

function VOIDPTR_BTREE_EMPTY(T:BTREE) : 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)

BTREE_NODE_BALANCE(N)

BALANCETYPE BTREE_NODE_BALANCE (BTREE_NODE N);

BALANCETYPE INT_BTREE_NODE_BALANCE (BTREE_NODE N);

BALANCETYPE FLOAT_BTREE_NODE_BALANCE (BTREE_NODE N);

BALANCETYPE CHARP_BTREE_NODE_BALANCE (BTREE_NODE N);

BALANCETYPE VOIDPTR_BTREE_NODE_BALANCE(BTREE_NODE N);

function BTREE_NODE_BALANCE (N:BTREE_NODE):BALANCETYPE;

function INT_BTREE_NODE_BALANCE (N:BTREE_NODE):BALANCETYPE;

function FLOAT_BTREE_NODE_BALANCE (N:BTREE_NODE):BALANCETYPE;

function CHARP_BTREE_NODE_BALANCE (N:BTREE_NODE):BALANCETYPE;

function VOIDPTR_BTREE_NODE_BALANCE(N:BTREE_NODE):BALANCETYPE;

Palauttaa tiedon solmun tasapainosta

Aikavaativuus : O(1)

BTREE_NODE_SET_BALANCE(N,B)

void BTREE_NODE_SET_BALANCE (BTREE_NODE N, BALANCETYPE B);

void INT_BTREE_NODE_SET_BALANCE (BTREE_NODE N, BALANCETYPE B);

void FLOAT_BTREE_NODE_SET_BALANCE (BTREE_NODE N, BALANCETYPE B)

void CHARP_BTREE_NODE_SET_BALANCE (BTREE_NODE N, BALANCETYPE B);

void VOIDPTR_BTREE_NODE_SET_BALANCE(BTREE_NODE N, BALANCETYPE B);

procedure BTREE_NODE_SET_BALANCE (N:BTREE_NODE; B:BALANCETYPE);

procedure INT_BTREE_NODE_SET_BALANCE (N:BTREE_NODE; B:BALANCETYPE);

procedure FLOAT_BTREE_NODE_SET_BALANCE (N:BTREE_NODE; B:BALANCETYPE);

procedure CHARP_BTREE_NODE_SET_BALANCE (N:BTREE_NODE; B:BALANCETYPE);

procedure VOIDPTR_BTREE_NODE_SET_BALANCE(N:BTREE_NODE; B:BALANCETYPE);

Asettaa solmun N tasapainoksi B:n.

Aikavaativuus : O(1)