tree.h 9.79 KiB
#ifndef _TREE_H_
#define _TREE_H_
/**
* @brief
* Le fichier définit un arbre binaire de recherche générique équilibré ou non-équilibré.
*/
/**
* @brief
* Un élément d'un arbre binaire de recherche contient
* (+) une clé (key),
* (+) une donnée (data),
* (+) le facteur d'équilibre (bfactor) :
* différence entre la hauteur du fils gauche et la hauteur du fils droit
* NB : le facteur d'équilibre d'une feuille est égal à 0,
* (+) la référence left vers le fils gauche, et
* (+) la référence right vers le fils droit.
*/
struct tree_node_t {
void * key;
void * data;
int bfactor;
struct tree_node_t * left;
struct tree_node_t * right;
};
/**
* @brief Renvoie 1 si le nœud \p node est vide, sinon renvoie 0.
*
* @param[in] node
* @return int
*/
int tree_node_is_empty(struct tree_node_t * node);
/**
* @brief Restitue la clé du nœud \p node.
*
* @param[in] node
* @return void*
*/
void * get_tree_node_key(const struct tree_node_t * node);
/**
* @brief Restitue la donnée du nœud \p node.
*
* @param[in] node
* @return void*
*/
void * get_tree_node_data(const struct tree_node_t * node);
/**
* @brief Restitue le fils gauche du nœud \p node.
*
* @param[in] node
* @return tree_node_t*
*/
struct tree_node_t * get_left(const struct tree_node_t * node);
/**
* @brief Restitue le fils droit du nœud \p node.
*
* @param[in] node
* @return tree_node_t*
*/
struct tree_node_t * get_right(const struct tree_node_t * node);
/**
* @brief Restitue le facteur d'équilibre du nœud \p node.
* * @param[in] node
* @return int
*/
int get_bfactor(const struct tree_node_t * node);
/**
* @brief Remplace la clé du nœud \p node par \p newKey.
*
* @param[in] node
* @param[in] newKey
*/
void set_tree_node_key(struct tree_node_t * node, void * newKey);
/**
* @brief Remplace la donnée du nœud \p node par \p newData.
*
* @param[in] node
* @param[in] newData
*/
void set_tree_node_data(struct tree_node_t * node, void * newData);
/**
* @brief Remplace le fils gauche du nœud \p node par \p newLeft.
*
* @param[in] node
* @param[in] newLeft
*/
void set_left(struct tree_node_t * node, struct tree_node_t * newLeft);
/**
* @brief Remplace le fils droit du nœud \p node par \p newRight.
*
* @param[in] node
* @param[in] newRight
*/
void set_right(struct tree_node_t * node, struct tree_node_t * newRight);
/**
* @brief Incrémente le facteur d'équilibre du nœud \p node par 1.
*
* @param[in] node
* @param[in] newBFactor
*/
void increase_bfactor(struct tree_node_t * node);
/**
* @brief Décrémente le facteur d'équilibre du nœud \p node par 1.
*
* @param[in] node
* @param[in] newBFactor
*/
void decrease_bfactor(struct tree_node_t * node);
/**
* @brief Remplace le facteur d'équilibre du nœud \p node par \p newBFactor.
*
* @param[in] node
* @param[in] newBFactor
*/
void set_bfactor(struct tree_node_t * node, int newBFactor);
/**
* L'arbre binaire de recherche est une structure contenant :
* (+) une référence (root) sur sa racine,
* (+) le nombre d'éléments,
* (+) un pointeur de fonction pour comparer ses clés,
* (+) un pointeur de fonction pour afficher ses clés,
* (+) un pointeur de fonction pour afficher ses données,
* (+) un pointeur de fonction pour libérer la mémoire de ses clés,
* (+) un pointeur de fonction pour libérer la mémoire de ses données, et * (+) une indication (balanced) si l'arbre binaire de recherche
* est équilibré (balanced=1) ou pas (balanced=0).
*/
struct tree_t {
struct tree_node_t * root;
int numelm;
int (*preceed)(const void * a, const void * b);
void (*viewKey)(const void * key);
void (*viewData)(const void * data);
void (*freeKey)(void * key);
void (*freeData)(void * data);
int balanced;
};
/**
* @brief Construire un arbre binaire de recherche vide.
*
* @param balanced Indique si l'arbre doit être équilibré (valeur 1) ou pas (valeur 0).
* @param preceed Pointeur de fonction pour comparer deux clés de l'arbre.
* @param viewKey Pointeur de fonction pour afficher la clé d'un nœud de l'arbre.
* @param viewData Pointeur de fonction pour afficher la donnée d'un nœud de l'arbre.
* @param freeKey Pointeur de fonction pour libérer la mémoire de la clé d'un nœud de l'arbre.
* @param freeData Pointeur de fonction pour libérer la mémoire de la donnée d'un nœud de l'arbre.
* @return struct tree_t*
*/
struct tree_t * new_tree(int balanced, int (*preceed)(const void *, const void *),
void (*viewKey)(const void *), void (*viewData)(const void *),
void (*freeKey)(void *), void (*freeData)(void *));
/**
* @brief Renvoie 1 si l'arbre \p T est vide, sinon renvoie 0.
*
* @param[in] T
* @return int
*/
int tree_is_empty(struct tree_t * T);
/**
* @brief Renvoie 1 si l'arbre \p T est équilibré, sinon renvoie 0.
*
* @param[in] T
* @return int
*/
int tree_is_balanced(struct tree_t * T);
/**
* @brief Restitue la taille (nombre d'éléments) de l'arbre \p T.
*
* @param[in] T
* @return int
*/
int get_tree_size(const struct tree_t * T);
/**
* @brief Restitue la racine de l'arbre \p T.
*
* @param[in] T
* @return tree_node_t*
*/
struct tree_node_t * get_root(const struct tree_t * T);
/**
* @brief Incrémente la taille de l'arbre \p T par 1.
*
* @param[in] T
*/
void increase_tree_size(struct tree_t * T);
/**
* @brief Décrémente la taille de l'arbre \p T par 1. *
* @param[in] T
*/
void decrease_tree_size(struct tree_t * T);
/**
* @brief Remplace la racine de l'arbre \p T par \p newRoot.
*
* @param[in] T
* @param[in] newRoot
*/
void set_root(struct tree_t * T, struct tree_node_t * newRoot);
/**
* @brief
* Plusieurs possibilités de supprimer l'arbre binaire de recherche T :
* (+) Si le paramètre deleteKey vaut 0
* Alors les clés (key) des éléments de l'arbre T ne sont pas supprimées ;
* (+) Si le paramètre deleteKey vaut 1
* Alors le pointeur de fonction freeKey de la structure BinarySearchTree
* va servir à supprimer les clés (key) des éléments de l'arbre T.
*
* (+) Si le paramètre deleteData vaut 0
* Alors les données (data) référencées par les éléments
* de l'arbre T ne sont pas supprimées ;
* (+) Si le paramètre deleteData vaut 1
* Alors le pointeur de fonction freeData de la structure BinarySearchTree
* va servir à supprimer les données (data) référencées par
* les éléments de l'arbre T.
*
* @param[in] T
* @param[in] deleteKey
* @param[in] deleteData
*/
void delete_tree(struct tree_t * T, int deleteKey, int deleteData);
/**
* @brief
* Afficher les éléments de l'arbre binaire de recherche T.
* Chaque élément est affiché grâce aux pointeurs de fonction
* de la structure BinarySearchTree:
* (+) viewKey pour la clé
* (+) viewData pour les données
* L'arbre est affiché dans l'ordre infixe.
*
* @param[in] T
*/
void view_tree(const struct tree_t * T);
/**
* @brief
* Ajouter dans l'arbre binaire de recherche \p T un élément de clé \p key et de donnée \p data.
*
* @param[in] T
* @param[in] key
* @param[in] data
*/
void tree_insert(struct tree_t * T, void * key, void * data);
/**
* @brief
* Trouver et renvoyer le nœud de clé minimum du sous-arbre raciné au nœud \p curr.
* NB : fonction récursive.
*
* @param[in] curr
* @return struct tree_node_t*
*/
struct tree_node_t * tree_min(struct tree_node_t * curr);
/** * @brief
* Trouver et renvoyer le nœud de clé maximum du sous-arbre raciné au nœud \p curr.
* NB : fonction récursive.
*
* @param[in] curr
* @return struct tree_node_t*
*/
struct tree_node_t * tree_max(struct tree_node_t * curr);
/**
* @brief
* Chercher dans le sous-arbre raciné au nœud \p curr et renvoyer le nœud avec clé \p key.
* Le pointeur de fonction \p preceed donne l'ordre entre deux clés.
* NB1 : fonction récursive.
* NB2 : on fait l'hypothèse que la clé \p key existe dans le sous-arbre raciné au nœud \p curr.
*
* @param[in] curr
* @param[in] key
* @param[in] preceed
* @return struct tree_node_t*
*/
struct tree_node_t * tree_find_node(struct tree_node_t * curr, void * key, int (*preceed)(const void *, const void *));
/**
* @brief
* Chercher dans le sous-arbre raciné au nœud \p curr et renvoyer le prédécesseur du nœud avec clé \p key.
* Le prédécesseur est le nœud qui contient la clé la plus grande qui est plus petite que la clé \p key.
* Le pointeur de fonction \p preceed donne l'ordre entre deux clés.
* NB1 : fonction récursive.
* NB2 : on fait l'hypothèse que la clé \p key existe dans le sous-arbre raciné au nœud \p curr.
*
* @param[in] curr
* @param[in] key
* @param[in] preceed
* @return struct tree_node_t*
*/
struct tree_node_t * tree_find_predecessor(struct tree_node_t * curr, void * key, int (*preceed)(const void *, const void *));
/**
* @brief
* Chercher dans le sous-arbre raciné au nœud \p curr et renvoyer le successeur du nœud avec clé \p key.
* Le successeur est le nœud qui contient la clé la plus petite qui est plus grande que la clé \p key.
* Le pointeur de fonction \p preceed donne l'ordre entre deux clés.
* NB1 : fonction récursive.
* NB2 : on fait l'hypothèse que la clé \p key existe dans le sous-arbre raciné au nœud \p curr.
*
* @param[in] curr
* @param[in] key
* @param[in] preceed
* @return struct tree_node_t*
*/
struct tree_node_t * tree_find_successor(struct tree_node_t * curr, void * key, int (*preceed)(const void *, const void *));
/**
* @brief
* Supprime le nœud avec clé \p key de l'arbre \p T et restitue sa donnée.
* La clé \p key existe obligatoirement dans l'arbre \p T.
* La mémoire du nœud supprimé ainsi que de sa clé est libérée mais pas la mémoire de la donnée.
*
* @param[in] T
* @param[in] key
* @return void*
*/
void * tree_remove(struct tree_t * T, void * key);
#endif // _TREE_H_