Arbre binaire équilibré [Arbre AVL] - Insérer et supprimer

1、Longueur moyenne de la recherche（Hauteur de l'arbre）:

 

2、Facteur d'équilibre du noeud=Hauteur du sous - arbre gauche-Hauteur du sous - arbre droit

Le facteur d'équilibre d'un noeud d'arbre binaire équilibré ne peut être que0,1Ou-1

 

2、Insérer

        2.1  L'objet de chaque ajustement est“Sous - arbre de déséquilibre minimal”

 

        2.2  Ajuster le Sous - arbre de déséquilibre minimalA

                ①LL【AL'enfant gauche tourne vers le haut à droite】：InAL'insertion dans le Sous - arbre gauche de l'enfant gauche provoque un déséquilibre

                ②RR【AL'enfant droit tourne à gauche】：InAL'insertion dans le Sous - arbre droit de l'enfant droit provoque un déséquilibre

 

 

                ③LR【AL'enfant de gauche l'enfant de droite tourne d'abord à gauche, puis à droite】：

                                InAL'insertion dans le Sous - arbre droit de l'enfant de gauche provoque un déséquilibre

 

                ④RL【A L'enfant droit l'enfant gauche tourne d'abord à droite, puis à gauche 】：

                                InAL'insertion dans le Sous - arbre gauche de l'enfant droit provoque un déséquilibre

【Note:】 Chaque rotation fait de cet enfant un père , Papa devient un enfant.

【Note:】Seuls les enfants de gauche peuvent pivoter vers le haut à droite

            Seul l'enfant droit peut tourner à gauche

 

 

 

3、Supprimer