Référence du fichier character_bistree.h

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

#include <stdbool.h>
#include "bitree.h"

Aller au code source de ce fichier.

Structures de données
struct	character_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	character_AVL_LFT_HEAVY   1
#define	character_AVL_BALANCED   0
#define	character_AVL_RGT_HEAVY   -1

Définitions de type
typedef struct character_avlnode_t	character_avlnode_t
	Type de données pour représenter l'information stockée dans un noeud d'un arbre binaire.
typedef generic_bitree_t	character_bistree_t
	Type de données pour représenter arbre binaire de recherche équilibrée.

Fonctions
void	character_bistree_init (character_bistree_t *tree)
	Initialisation d'un nouvel arbre binaire de recherche équilibré
void	character_bistree_destroy (character_bistree_t *tree)
	Destruction d'un arbre binaire de recherche équilibré
int	character_bistree_insert (character_bistree_t *tree, char data)
	Insertion d'une nouvelle valeur dans un arbre binaire de recherche équilibré
int	character_bistree_remove (character_bistree_t *tree, char data)
	Suppression d'une valeur dans un arbre binaire de recherche équilibré
bool	character_bistree_lookup (character_bistree_t *tree, char data)
	Test la présence d'une valeur dans l'arbre binaire de recherche équilibré
int	character_bistree_size (character_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 char .

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

character_AVL_BALANCED

#define character_AVL_BALANCED   0

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

character_AVL_LFT_HEAVY

#define character_AVL_LFT_HEAVY   1

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

character_AVL_RGT_HEAVY

#define character_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

character_avlnode_t

typedef struct character_avlnode_t character_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 char à 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.

character_bistree_t

typedef generic_bitree_t character_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

character_bistree_destroy()

void character_bistree_destroy

(

character_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

tree	est un pointeur vers la structure de données character_bistree_t

character_bistree_init()

void character_bistree_init

(

character_bistree_t *

tree

)

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

Met à zéro la taille et à NULL le pointeur vers la racine

Paramètres

tree	est un pointeur vers la structure de données character_bistree_t

character_bistree_insert()

int character_bistree_insert	(	character_bistree_t *	tree,
		char	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

tree	est un pointeur vers la structure de données character_bistree_t
data	la valeur de type char à ajouter

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur)

character_bistree_lookup()

bool character_bistree_lookup	(	character_bistree_t *	tree,
		char	data )

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

Paramètres

tree	est un pointeur vers la structure de données character_bistree_t
data	la valeur de type char cherchée

Renvoie

valeur booléenne indiquant si data est présent dans tree ou non

character_bistree_remove()

int character_bistree_remove	(	character_bistree_t *	tree,
		char	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

tree	est un pointeur vers la structure de données character_bistree_t
data	la valeur de type char à supprimer.

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur)

character_bistree_size()

int character_bistree_size

(

character_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

tree	est un pointeur vers la structure de données character_bistree_t

Renvoie

valeur entière donnant le nombre de valeurs stockées dans l'arbre