Arbres de recherche binaires

There are three cases for deleting a node:
1. Leaf node: Simply remove the node
2. Node with one child: Replace the node with its child
3. Node with two children: Find the node's in-order successor (smallest node in the right subtree) and replace the node with it
Deletion can lead to imbalance in the tree, which can be resolved by rebalancing operations

There are three main types of traversal:
1. In-order traversal: Left subtree, current node, right subtree
2. Pre-order traversal: Current node, left subtree, right subtree
3. Post-order traversal: Left subtree, right subtree, current node
Traversal can be used to perform operations such as printing the tree, searching for a node, or calculating the sum of node values

Time complexity:
- Insertion: O(log n) on average, O(n) in the worst case
- Deletion: O(log n) on average, O(n) in the worst case
- Search: O(log n) on average, O(n) in the worst case
Space complexity: O(n), where n is the number of nodes in the tree

Insertion involves finding the correct location for the new node in the tree
There are two cases for insertion:
1. The tree is empty: Create a new node as the root
2. The tree is not empty: Find the correct location for the new node based on its value and insert it
Insertion can lead to imbalance in the tree, which can be resolved by rebalancing operations

A balanced tree is a tree where the height of the left and right subtrees of every node differs by at most one
Balancing operations can be performed to maintain a balanced tree, such as:
- Left rotation: Rotating a node to the left to balance the tree
- Right rotation: Rotating a node to the right to balance the tree
Balancing operations can be performed during insertion and deletion to maintain a balanced tree

Il existe trois cas pour supprimer un nœud :
Feuille : Supprimer simplement le nœud
Nœud avec un enfant : Remplacer le nœud par son enfant
Nœud avec deux enfants : Trouver le successeur in-order (plus petit nœud de la sous-arbre droite) et le remplacer par ce successeur
La suppression peut conduire à une déséquilibre dans l'arbre, qui peut être résolu par des opérations de rebalancement

Il existe trois types de parcours principaux :
Parcours in-order : Sous-arbre gauche, nœud actuel, sous-arbre droit
Parcours pré-order : Nœud actuel, sous-arbre gauche, sous-arbre droit
Parcours post-order : Sous-arbre gauche, sous-arbre droit, nœud actuel
Le parcours peut être utilisé pour effectuer des opérations telles que l'impression de l'arbre, la recherche d'un nœud ou le calcul de la somme des valeurs des nœuds

Complexité temps :
- Insertion : O(log n) en moyenne, O(n) dans le pire cas
- Suppression : O(log n) en moyenne, O(n) dans le pire cas
- Recherche : O(log n) en moyenne, O(n) dans le pire cas
Complexité d'espace : O(n), où n est le nombre de nœuds dans l'arbre

L'insertion implique de trouver l'emplacement correct pour le nouveau nœud dans l'arbre
Il existe deux cas pour l'insertion :
L'arbre est vide : Créer un nouveau nœud comme racine
L'arbre n'est pas vide : Trouver l'emplacement correct pour le nouveau nœud en fonction de sa valeur et l'insérer
L'insertion peut conduire à une déséquilibre dans l'arbre, qui peut être résolu par des opérations de rebalancement

Un arbre équilibré est un arbre où la hauteur des sous-arbres gauche et droit de chaque nœud diffère d'au plus un
Les opérations de rebalancement peuvent être effectuées pour maintenir un arbre équilibré, telles que :
- Rotation à gauche : Faire pivoter un nœud à gauche pour équilibrer l'arbre
- Rotation à droite : Faire pivoter un nœud à droite pour équilibrer l'arbre
Les opérations de rebalancement peuvent être effectuées pendant l'insertion et la suppression pour maintenir un arbre équilibré

Parcours inordonné : Sous-arbre gauche -> Racine -> Sous-arbre droit
- Vise les nœuds dans l'ordre croissant
- Utilisé pour imprimer les nœuds dans l'ordre trié
Parcours préordonné : Racine -> Sous-arbre gauche -> Sous-arbre droit
- Utilisé pour créer une copie de l'arbre
- Utilisé pour obtenir l'expression préfixe d'un arbre d'expression
Parcours postordonné : Sous-arbre gauche -> Sous-arbre droit -> Racine
- Utilisé pour supprimer l'arbre
- Utilisé pour obtenir l'expression postfixe d'un arbre d'expression
Parcours en largeur : Vise les nœuds niveau par niveau, de gauche à droite

Hauteur d'un arbre : Le nombre dearettes sur le chemin le plus long du racine à une feuille
Hauteur d'un nœud : Le nombre dearettes sur le chemin le plus long du nœud à une feuille
Arbre équilibré : Un arbre avec une hauteur de O(log n), où n est le nombre de nœuds

Insertion :
- Trouver la position appropriée pour le nouveau nœud
- Insérer le nouveau nœud
- Rééquilibrer l'arbre si nécessaire
Suppression :
- Trouver le nœud à supprimer
- Supprimer le nœud
- Rééquilibrer l'arbre si nécessaire
Rééquilibrage : Rotation des nœuds pour maintenir la propriété d'équilibre de l'arbre

Facteurs d'équilibrage : Une mesure de l'équilibre d'un arbre
Rotation à gauche : Rotation des nœuds à gauche pour équilibrer l'arbre
Rotation à droite : Rotation des nœuds à droite pour équilibrer l'arbre
Arbres auto-équilibrés : Arbres qui se rééquilibrent automatiquement après insertion ou suppression, tels que les arbres AVL et les arbres Rouge-Noir

Prédécesseur : Le nœud qui précède un nœud donné lors d'un parcours inordonné
Trouver le prédécesseur :
- Trouver le successeur inordonné du nœud
- Si le nœud a un fils gauche, le prédécesseur est le nœud le plus à droite du sous-arbre gauche
- Sinon, le prédécesseur est le parent du nœud jusqu'à ce qu'un nœud avec un fils gauche soit trouvé