libin103 1.4
Bibliothèque de structures de données en C
Chargement...
Recherche...
Aucune correspondance
Structures de données | Macros | Définitions de type | Fonctions
Référence du fichier generic_bistree.h

Structure de données d'arbres binaires de recherche équilibrés contenant des valeurs de type void* . Plus de détails...

#include "generic_bitree.h"

Aller au code source de ce fichier.

Structures de données

struct  generic_avlnode_t
 Type de données pour représenter l'information stockée dans un noeud d'un arbre binaire. Plus de détails...
 

Macros

#define AVL_LFT_HEAVY   1
 
#define AVL_BALANCED   0
 
#define AVL_RGT_HEAVY   -1
 

Définitions de type

typedef struct generic_avlnode_t generic_avlnode_t
 Type de données pour représenter l'information stockée dans un noeud d'un arbre binaire.
 
typedef generic_bitree_t generic_bistree_t
 Type de données pour représenter arbre binaire de recherche équilibrée.
 

Fonctions

void generic_bistree_init (generic_bistree_t *tree, int(*compare)(const void *key1, const void *key2), void *(*build)(const void *data), void(*destroy)(void *data))
 Initialisation d'un nouvel arbre binaire de recherche équilibré
 
void generic_bistree_destroy (generic_bistree_t *tree)
 Destruction d'un arbre binaire de recherche équilibré
 
int generic_bistree_insert (generic_bistree_t *tree, void *data)
 Insertion d'une nouvelle valeur dans un arbre binaire de recherche équilibré
 
int generic_bistree_remove (generic_bistree_t *tree, void *data)
 Suppression d'une valeur dans un arbre binaire de recherche équilibré
 
int generic_bistree_lookup (generic_bistree_t *tree, void **data)
 Test la présence d'une valeur dans l'arbre binaire de recherche équilibré
 
int generic_bistree_size (generic_bistree_t *tree)
 Accesseur donnant la taille de l'arbre binaire de recherche équillibré
 

Description détaillée

Structure de données d'arbres binaires de recherche équilibrés contenant des valeurs de type void* .

Les arbres binaires de recherche équilibrés sont mis en oeuvre à partir des arbres binaires dans leur version générique (avec des type void*). Pour cette mise en oeuvre une structure de données représentant des valeurs à stocker dans l'arbre binaire est définie.

Documentation des macros

◆ AVL_BALANCED

#define AVL_BALANCED   0

Etiquette pour indiquer qu'noeud a ses deux sous arbres de meme hauteur

◆ AVL_LFT_HEAVY

#define AVL_LFT_HEAVY   1

Etiquette pour indiquer qu'un noeud a un sous-arbre gauche plus haut que le sous arbre droit

◆ AVL_RGT_HEAVY

#define AVL_RGT_HEAVY   -1

Etiquette pour indiquer qu'un noeud a un sous-arbre droit plus haut que le sous arbre guache

Documentation des définitions de type

◆ generic_avlnode_t

typedef struct generic_avlnode_t generic_avlnode_t

Type de données pour représenter l'information stockée dans un noeud d'un arbre binaire.

Cette structure de données contient la valeur de type void* à stocker ainsi que des informations servant à équilibrer l'arbre binaire de recherche au besoin et une étiquette utilisée pour améliorer les performances de l'opération de suppression.

◆ generic_bistree_t

Type de données pour représenter arbre binaire de recherche équilibrée.

Ce type est un arbre binaire générique avec des opérations d'insertion et de suppression adaptée pour maintenir l'équilibrage de l'arbre.

Documentation des fonctions

◆ generic_bistree_destroy()

void generic_bistree_destroy ( generic_bistree_t * tree)

Destruction d'un arbre binaire de recherche équilibré

Met à zéro la taille et à NULL le pointeur vers la racine après avoir parcourus l'arbre pour détruire chaque noeud

Paramètres
treeest un pointeur vers la structure de données generic_bistree_t

◆ generic_bistree_init()

void generic_bistree_init ( generic_bistree_t * tree,
int(*)(const void *key1, const void *key2) compare,
void *(*)(const void *data) build,
void(*)(void *data) destroy )

Initialisation d'un nouvel arbre binaire de recherche équilibré

Met à zéro la taille et à NULL le pointeur vers la racine. Cette fonction nécessite une fonction de comparaison des éléments de la file, une fonction de construction d'un élément de la file et une fonction de destruction des éléments de la file.

Paramètres
treeest un pointeur vers la structure de données generic_bistree_t
comparefonction permettant la comparaison de deux éléments de l'arbre binaire de recherche
buildfonction permettant la construction d'une valeur de l'arbre binaire de recherche
destroyfonction permettant la destruction d'une valeur de l'arbre binaire de recherche

◆ generic_bistree_insert()

int generic_bistree_insert ( generic_bistree_t * tree,
void * data )

Insertion d'une nouvelle valeur dans un arbre binaire de recherche équilibré

Cette fonction crée un nouveau noeud avec la données et réalise des opérations d'équilibrage (rotations) de la structure de données arbres binaires de recherche au besoin.

Paramètres
treeest un pointeur vers la structure de données generic_bistree_t
datala valeur de type void* à ajouter
Renvoie
valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur)

◆ generic_bistree_lookup()

int generic_bistree_lookup ( generic_bistree_t * tree,
void ** data )

Test la présence d'une valeur dans l'arbre binaire de recherche équilibré

Paramètres
treeest un pointeur vers la structure de données generic_bistree_t
datala valeur de type void* cherchée
Renvoie
valeur booléenne indiquant si data est présent dans tree ou non

◆ generic_bistree_remove()

int generic_bistree_remove ( generic_bistree_t * tree,
void * data )

Suppression d'une valeur dans un arbre binaire de recherche équilibré

Cette fonction ne supprime pas le noeud associé à la données supprimée mais le cache seulement grâce à l'étiquette hidden. Optimisation pour ne pas réaliser d'opération d'équilibrage après suppression.

Paramètres
treeest un pointeur vers la structure de données generic_bistree_t
datala valeur de type void* à supprimer.
Renvoie
valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur)

◆ generic_bistree_size()

int generic_bistree_size ( generic_bistree_t * tree)

Accesseur donnant la taille de l'arbre binaire de recherche équillibré

La taille correspond au nombre de valeurs stockées dans l'arbre

Paramètres
treeest un pointeur vers la structure de données generic_bistree_t
Renvoie
valeur entière donnant le nombre de valeurs stockées dans l'arbre