Concepts fondamentaux
Une arbre est une structure de données hiérarchique composée de nœuds connectés par des arêtes sans cycles.
- Nœud (node) : représentation abstraite d’un élément (racine, nœud interne, feuille).
- Racine : unique nœud sans parent.
- Feuille : nœud sans enfant (degré zéro).
- Arête : lien entre zwei nœuds parent-enfant.
- Sous-arbre : arbre formé d’un nœud et de ses descendants.
Propriétés essentielles
- Une arbre vide (sans nœud) est valide.
- La profondeur d’un nœud est le nombre d’arêtes entre lui et la racine ; la hauteur est le nombre maximal d’arêtes jusqu’à une feuille dans son sous-arbre.
- La hauteur d’un arbre est égale à la profondeur maximale de ses nœuds.
- Le degré d’un nœud est son nombre d’enfants ; le degré maximal dans l’arbre est sa largeur.
- Une structure connexe avec n nœuds et n−1 arêtes est nécessairement un arbre.
- Un ensemble d’arbres disjoints forme une forêt.
Arbres binaires
Définition récursive
- Une arbre vide.
- Un nœud racine, avec un sous-arbre gauche et un sous-arbre droit, chacun étant également un arbre binaire.
Contrairement aux arbres généraux de degré 2, dans les arbres binaires, la gauche et la droite sont distinguées.
Types spéciaux
- Arbre binaire parfait : chaque niveau est entièrement rempli.
- Arbre binaire complet : tous les niveaux sauf le dernier sont remplis, et le dernier est rempli de gauche à droite sans sauts.
Representation en mémoire
Utilisation d’une structure avec pointeurs vers les sous-arbres gauche et droit :
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
TreeNode() : value(0), left(nullptr), right(nullptr) {}
};
Initialisation d’un arbre vide :
TreeNode* root = nullptr;
Fonction utilitaire pour créer un nouveau nœud :
TreeNode* createNode(int val) {
return new TreeNode{val, nullptr, nullptr};
}
Opérations sur les arbres binaires
Recherche et modification
void update(TreeNode* node, int target, int newValue) {
if (!node) return;
if (node->value == target) node->value = newValue;
update(node->left, target, newValue);
update(node->right, target, newValue);
}
Insertion (dans un arbre binaire quelconque)
L’insertion suit la logique d’un arbre de recherche binaire (BST) si une contrainte d’ordre est introduite. Ici, on suppose une insertion récursive dans l’arbre générique :
void insert(TreeNode*& node, int val) {
if (!node) {
node = createNode(val);
return;
}
// Logique d’insertion basée sur une règle donnée (ex. arbres de recherche)
if (val < node->value) {
insert(node->left, val);
} else {
insert(node->right, val);
}
}
Construction
Création à partir d’un tableau d’entiers :
TreeNode* buildTree(const vector<int>& vals) {
TreeNode* root = nullptr;
for (int x : vals) {
insert(root, x);
}
return root;
}
ARBRE BINAIRE COMPLET-stockage tableau
Pour les arbres binaires complets, on peut utiliser un tableau :
- Si l’index de la racine est 1 (idx > 0), alors :
- Fils gauche → idx * 2
- Fils droit → idx * 2 + 1
Un nœud d’index i est une feuille si 2i > n. La traversée en niveau coïncide avec l’ordre du tableau.
Parcours d’arbres binaires
Parcours en profondeur (DFS)
- Préordre : Racine → Gauche → Droite
- Infixe (ordre médian) : Gauche → Racine → Droite
- Postordre : Gauche → Droite → Racine
Implémentations
void preorder(TreeNode* node) {
if (!node) return;
cout << node->value;
preorder(node->left);
preorder(node->right);
}
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
cout << node->value;
inorder(node->right);
}
void postorder(TreeNode* node) {
if (!node) return;
postorder(node->left);
postorder(node->right);
cout << node->value;
}
Parcours en largeur (BFS — niveau par niveau)
void levelorder(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front(); q.pop();
cout << cur->value;
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
Pour suiver les niveaux, on ajoute un champ level dans la structure de nœud, initialisé à 1 pour la racine, puis incrémenté à chaque descente.
Reconstruction d’arbre à partir de traversées
Avec les séquences inorder et preorder (ou postorder), on reconstruit l’arbre de manière unique si les clés sont distinctes.
Principe : le premier élément du preorder est la racine. Dans la séquence inorder, cet élément sépare les sous-arbres gauche et droit.
TreeNode* rebuild(const vector<int>& pre, const vector<int>& in,
int pl, int pr, int il, int ir) {
if (pl > pr) return nullptr;
int rootVal = pre[pl];
int k = il;
while (in[k] != rootVal) ++k;
int leftSize = k - il;
TreeNode* r = new TreeNode{rootVal, nullptr, nullptr};
r->left = rebuild(pre, in, pl + 1, pl + leftSize, il, k - 1);
r->right = rebuild(pre, in, pl + leftSize + 1, pr, k + 1, ir);
return r;
}
Arbre de recherche binaire (BST)
Arbre binaire où pour chaque nœud :
- Tous les nœuds à gauche ont une clé ≤ nœud courant.
- Tous les nœuds à droite ont une clé > nœud courant.
Opérations fondamentales
Recherche
TreeNode* search(TreeNode* node, int key) {
if (!node || node->value == key) return node;
return key < node->value ? search(node->left, key) : search(node->right, key);
}
Insertion
void add(TreeNode*& root, int val) {
if (!root) {
root = createNode(val);
return;
}
if (val < root->value) add(root->left, val);
else if (val > root->value) add(root->right, val);
}
Suppression
Deux cas critiques :
- Nœud feuille : suppression directe.
- Nœud à un enfant ou deux enfants :
- Remplacer par le prédécesseur (maximum sous-arbre gauche) ou le successeur (minimum sous-arbre droit).
- Puis supprimer ce remplaçant.
TreeNode* findMax(TreeNode* node) {
while (node && node->right) node = node->right;
return node;
}
TreeNode* findMin(TreeNode* node) {
while (node && node->left) node = node->left;
return node;
}
void removeValue(TreeNode*& root, int key) {
if (!root) return;
if (key < root->value) removeValue(root->left, key);
else if (key > root->value) removeValue(root->right, key);
else {
if (!root->left && !root->right) root = nullptr;
else if (root->left) {
TreeNode* pred = findMax(root->left);
root->value = pred->value;
removeValue(root->left, pred->value);
} else {
TreeNode* succ = findMin(root->right);
root->value = succ->value;
removeValue(root->right, succ->value);
}
}
}
La traversée infixe d’un BST produit les clés en ordre croissant.
Arbre équilibré (AVL)
Un BST où pour chaque nœud :
|h_gauche − h_droite| ≤ 1
Chaque nœud stocke sa hauteur pour recalculer rapidement l’équilibre.
Ensemble disjoints (Union-Find)
Représentation à l’aide d’un tableau parent[i]. La racine vérifie parent[i] == i.
Optimisations
find(x):_recherche_ de la racine avec compressage de chemin.union(x, y): fusion des ensembles avec union par rang/hauteur.
int find(int x, vector<int>& p) {
return p[x] == x ? x : p[x] = find(p[x], p);
}
void unite(int x, int y, vector<int>& p, vector<int>& rank) {
int rx = find(x, p), ry = find(y, p);
if (rx == ry) return;
if (rank[rx] < rank[ry]) swap(rx, ry);
p[ry] = rx;
if (rank[rx] == rank[ry]) ++rank[rx];
}
Tas (heap)
Arbre binaire complet (ou presque) vérifiant :
- Tas max : parent ≥ enfants.
- Tas min : parent ≤ enfants.
Souvent implémenté avec un tableau (indexation 0 ou 1).
Arbre de Huffman
Arbre binaire minimisant la longueur de encodage pondéré (WPL) :
WPL = Σ (freq_i × profondeur_i)
Construction
- Créer n’arbres unitaires (chaque nœud = fréquence).
- Tant qu’il reste >1 arbre : - Prendre les deux faibles poids. - Créer un nouveau nœud parent avec le poids = somme.
long long huffman(vector<int> data) {
priority_queue<long long, vector<long long>, greater<>> pq(data.begin(), data.end());
long long cost = 0;
while (pq.size() > 1) {
long long a = pq.top(); pq.pop();
long long b = pq.top(); pq.pop();
cost += a + b;
pq.push(a + b);
}
return cost;
}
Encodage de Huffman
- Chemin gauche = 0, droite = 1.
- Code sans préfixe : aucun code n’est préfixe d’un autre.
- Permet une compression optimale (minimum d’entiers bits).