Implémentation de la méthode delete

Supprimer un élément d'un arbre AVL équivaut à le supprimer d'un BST, sauf que l'arbre devra peut-être être rééquilibré. Comme indiqué dans la section Suppression d'éléments d'un BST, pour supprimer un élément d'un arbre binaire, l'algorithme localise d'abord le nœud qui contient l'élément. Laissez current pointer vers le nœud qui contient l'élément dans l'arbre binaire et parent pointer vers le parent du nœud current. Le nœud actuel peut être un enfant gauche ou un enfant droit du nœud parent.
Deux cas se présentent lors de la suppression d'un élément.

Cas 1 : Le nœud actuel n'a pas d'enfant gauche, comme le montre la figure ci-dessous (a). Pour supprimer le nœud actuel, connectez simplement le nœud parent avec l'enfant droit du nœud actuel, comme indiqué dans la figure ci-dessous (b). La hauteur des nœuds le long du chemin depuis le nœud parent jusqu'à la racine peut avoir diminué. Pour vous assurer que l'arbre est équilibré, invoquez

balancePath(parent.element);

Cas 2 : Le nœud actuel a un enfant gauche. Laissez rightMost pointer vers le nœud qui contient le plus grand élément dans le sous-arbre gauche du nœud current et parentOfRightMost pointer vers le nœud parent du rightMost nœud, comme le montre la figure ci-dessous (a). Le nœud rightMost ne peut pas avoir d'enfant droit mais il peut avoir un enfant gauche. Remplacez la valeur de l'élément dans le nœud current par celle du nœud rightMost, connectez le nœud parentOfRightMost avec l'enfant gauche du rightMost et supprimez le nœud rightMost, comme indiqué dans la figure ci-dessous (b).

La hauteur des nœuds le long du chemin depuis parentOfRightMost jusqu'à la racine peut avoir diminué. Pour vous assurer que l'arbre est équilibré, invoquez

balancePath(parentOfRightMost);

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!