Binääripuu

Sisältö:

Määritelmä:

Binääripuun erona yleiseen puuhun on se, että siinä rajoitetaan solmun lapsiluku kahteen. Lisäksi binääripuussa solmu (juurta lukuunottamatta) voi olla vasen tai oikea lapsi riippumatta siitä onko toista lasta olemassakaan.

Käytössä olevat tyypit

Yleinen binääripuu:
Yleistä puuta käytetään kun ei tiedetä talletettavien arvojen tyyppiä tai halutaan tehdä helpommin muunnettavissa oleva rakenne Käytettäessä yleistä binääripuuta, puun funktioihin ei lisätä mitään, mutta puuta luotaessa tyyppi määritellään kuvaajalla DESCRIPTOR.

Kokonaislukupuu:
Kokonaislukupuun solmuihin voi tallettaa nimensä mukaisesti kokonaislukuarvoja. Kokonaislukupuuta käytettäessä puun funktioiden eteen lisätään INT_ tai lyhenne IB_ (korvaa sanat INT_BTREE).

Liukulukupuu/ reaalilukupuu:
Solmuihin voi tallettaa liukuluku/reaalilukuarvoja. Käytettäessä liukulukuja puun funktioiden eteen lisätään FLOAT_ tai lyhenne FB_ (korvaa sanat FLOAT_BTREE_).

Merkkijonopuu:
Puun solmuihin voi tallettaa merkkijonon.Merkkijonopuu esitellään lisäämällä puun funktion eteen CHARP_ tai lyhenne CB_ (korvaa sanat CHARP_BTREE_).

Osoitinpuu:
Puun solmuihin voi tallettaa osoittimia.Merkkijonopuu esitellään lisäämällä puun funktion eteen VOIDPTR_ .

FUNKTIOT:

Uuden binääripuun luominen:
BBTREE_CREATE (T, D)

BTREE_CREATE (T, D) muodostaa tyhjän puun T joka on yleistä tyyppiä D. Tyypitetyt operaatiot taas muodostavat puun T joka on operaation mukaista tyyppiä (esim IT_CREATE(BTREE T); luo kokonaislukupuun T).
Aikavaativuus : O(1) 

void BTREE_CREATE (BTREE T, DESCRIPTOR D);
void INT_BTREE_CREATE(BTREE T);  	(*kokonaislukupuu*)
void FLOAT_BTREE_CREATE(BTREE T); 	(*liukulukupuu*)
void CHARP_BTREE_CREATE(BTREE T);    (*merkkijonopuu*)
void VOIDPTR_BTREE_CREATE(BTREE T); (*osoitinpuu*)

Uuden solmun luominen:
BTREE_CREATE_NODE(x)

Funktio BTREE_CREATE_NODE(x) luo uuden solmun jonka sisällöksi tulee X. Solmua ei vielä kiinnitetä minnekkään eikä sen tyyppiä määritellä.
Aikavaativuus : O(1) 

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);

Solmun asettaminen juurisolmuksi:
BTREE_ASSIGN_ROOT(T,N)

BTREE_ASSIGN_ROOT(T,N) komennolla solmu N asetetaan puun T juureksi jolloin solmun tyypistä tulee sama kuin puun tyypistä.
Aikavaativuus : O(1) 

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);

Solmun asettaminen vasemmaksi/oikeaksi lapseksi:
BTREE_ASSIGN_CHILD (T, ND, dir, NS)

BTREE_ASSIGN_CHILD (T, ND, dir, NS) asettaa puun T solmun ND vasemmaksi tai oikeaksi lapseksi solmun NS. Lapsen puolen voi määrätä oikeaksi tai vasemmaksi, sijoittamalla muuttujaan dir joko right tai left.
Aikavaativuus : O(1) 

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);

Solmun isän hakeminen:
BTREE_PARENT(T,N)

Funktio palauttaa binääripuusta T, solmun N isäsolmun.
Aikavaativuus : O(1) 

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);

Solmun vasemman lapsen hakeminen:
BTREE_LEFTCHILD(T,N)

Funktio palauttaa puusta T, solmun N vanhimman(vasemmanpuoleisimman) lapsen.
Aikavaativuus : O(1) 

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);

Solmun oikean lapsen hakeminen:
BTREE_RIGHTCHILD(T,N)

Funktio palauttaa binääripuusta T, solmun N oikeanpuoleisen lapsen
Aikavaativuus : O(1) 

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);

Solmun tuhoaminen:
BTREE_DESTROY_NODE (T,N)

BTREE_DESTROY_NODE (T,N) poistaa puusta T solmun N. Poistaessa on huomioitava, että kaikki poistettavan solmun lapset jäävät "kellumaan" tyhjän päälle.
Aikavaativuus : O(1) 

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);

Puun juuren hakeminen:
BTREE_ROOT(T)

BTREE_ROOT(T) palauttaa puun T juuren. Jos puu on tyhjä palautuu arvo NULL.
Aikavaativuus : O(1) 

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);

Arvon hakeminen binääripuun tietystä solmusta:
BTREE_RETRIEVE (T, N)

BTREE_RETRIEVE (T, N) palauttaa puusta T solmun N arvon, jos solmu on olemassa.
Aikavaativuus : O(1) 

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)

Solmun arvon tulostaminen:
BTREE_PRINT_NODE (T, N)

BTREE_PRINT_NODE (T, N) tulostaa solmun N, puusta T.
Aikavaativuus : yksinkertaisille tyypeille O(1) 

void BTREE_PRINT_NODE (BTREE T, BTREE_NODE N);

Solmujen välisen tasapainon asettaminen:
BTREE_NODE_SET_BALANCE(N,B)

BTREE_NODE_SET_BALANCE(N,B) asettaa solmulle N tasapainon B.
Aikavaativuus : O(1) 

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);

Solmujen välisen tasapainon hakeminen:
BTREE_NODE_BALANCE(N)

BTREE_NODE_BALANCE(N) Palauttaa solmun N tasapainon.
Aikavaativuus : O(1) 

 
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);

Puun tyypin hakeminen:
BTREE_TYPE (T)

Funktio BTREE_TYPE (T) palauttaa puun tyypin.
Aikavaativuus : O(1) 

DESCRIPTOR BTREE_TYPE (BTREE T);

Solmujen sisältöjen järjestyksen vertailu:
BTREE_SAME (T, x, y)
BTREE_LESS (T, x, y)

Funktiot palauttavat boolen typpisen arvon (TRUE/FALSE) siitä onko puun T alkio x sama (int BTREE_SAME) vai pienempi(BTREE_LESS) kuin alkio y.
Aikavaativuus : yksinkertaisille tyypeille O(1) 

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

Tutki onko puu tyhjä:
BTREE_EMPTY (T)

BTREE_EMPTY (T) palauttaa boolean (TRUE/FALSE) tyyppisen arvon riippuen siitä onko puu tyhjä (true) vai löytyykö siellä arvo/arvoja (FALSE).
Aikavaativuus : O(1) 

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);