Les Arbres de recherche binaires supportent trois opérations principales: insertion d’éléments, suppression d’éléments et recherche (vérification de la présence d’une clé).

SearchingEdit

La recherche dans un arbre de recherche binaire d’une clé spécifique peut être programmée de manière récursive ou itérative.

Nous commençons par examiner le nœud racine. Si l’arbre est null, la clé que nous recherchons n’existe pas dans l’arbre. Sinon, si la clé est égale à celle de la racine, la recherche est réussie et nous retournons le nœud. Si la clé est inférieure à celle de la racine, nous recherchons le sous-arbre gauche., De même, si la clé est supérieure à celle de la racine, nous recherchons le bon sous-arbre. Ce processus est répété jusqu’à ce que la clé soit trouvée ou que le sous-arbre restant soit null. Si la clé recherchée n’est pas trouvée après l’atteinte d’un sous-arbre null, la clé n’est pas présente dans l’arborescence. Ceci est facilement exprimé sous la forme d’un algorithme récursif (implémenté en Python):

le même algorithme peut être implémenté de manière itérative:

ces deux exemples ne prennent pas en charge les doublons, c’est-à-dire qu’ils reposent sur la relation d’ordre étant un ordre total.

On peut noter que l’algorithme récursif est la queue récursive., Dans un langage prenant en charge l’optimisation des appels de queue, les exemples récursifs et itératifs seront compilés en programmes équivalents.

dans le pire des cas, cet algorithme doit rechercher de la racine de l’arbre à la feuille la plus éloignée de la racine, l’opération de recherche prend un temps proportionnel à la hauteur de l’arbre (voir terminologie de l’arbre). En moyenne, les arbres de recherche binaires avec des clés de nœuds ont une hauteur O(log |Nodes|). Cependant, dans le pire des cas, les arbres de recherche binaires peuvent avoir une hauteur O(|Nodes|), lorsque l’arbre déséquilibré ressemble à une liste chaînée (arbre dégénéré).,

recherche avec doublons allowedEdit

Si la relation d’ordre n’est qu’une précommande totale, une extension raisonnable de la fonctionnalité est la suivante: également en cas de recherche d’égalité jusqu’aux feuilles. Ce qui permet de spécifier (ou hard-wire) une direction, où insérer un doublon, soit à droite ou à gauche de tous les doublons dans l’arborescence jusqu’à présent. Si la direction est câblée, les deux choix, à droite et à gauche, prennent en charge une pile avec insert duplicate comme opération push et delete comme opération pop.,: 155

un tri d’arbre binaire équipé d’une telle fonction de recherche devient stable.

InsertionEdit

L’Insertion commence comme une recherche commencerait; si la clé n’est pas égale à celle de la racine, nous recherchons les sous-arbres gauche ou droit comme auparavant. Finalement, nous atteindrons un nœud externe et ajouterons la nouvelle paire clé-valeur (ici codée comme un enregistrement ‘newNode’) comme enfant droit ou gauche, en fonction de la clé du nœud., En d’autres termes, nous examinons la racine et insérons récursivement le nouveau nœud dans le sous-arbre gauche si sa clé est inférieure à celle de la racine, ou le sous-arbre droit si sa clé est supérieure ou égale à la racine.

Voici comment une insertion d’arbre de recherche binaire typique peut être effectuée dans un arbre binaire en C++:

alternativement, une version non récursive peut être implémentée comme ceci., L’utilisation d’un pointeur à pointeur pour garder une trace de notre provenance permet au code d’éviter la vérification explicite et la gestion du cas où il doit insérer un nœud à la racine de l’arbre:

la variante procédurale destructive ci-dessus modifie l’arbre en place. Il utilise uniquement un espace de tas constant (et la version itérative utilise également un espace de pile constant), mais la version précédente de l’arbre est perdue., Alternativement, comme dans L’exemple Python suivant, nous pouvons reconstruire tous les ancêtres du nœud inséré; toute référence à la racine de l’arbre d’origine reste valide, faisant de l’arbre une structure de données persistante:

la partie reconstruite utilise L’Espace O(log n) dans le cas moyen et O(n) dans le pire des cas.

dans les deux versions, cette opération nécessite un temps proportionnel à la hauteur de l’arbre dans le pire des CAs, qui est O(log n) Temps dans le cas moyen sur tous les arbres, mais O(n) temps dans le pire des cas.,

Une autre façon d’expliquer l’insertion est que pour insérer un nouveau nœud dans l’arborescence, sa clé est d’abord comparée à celle de la racine. Si sa clé est inférieure à celle de la racine, elle est alors comparée à la clé de l’enfant gauche de la racine. Si sa clé est plus grande, elle est comparée à l’enfant droit de la racine. Ce processus continue, jusqu’à ce que le nouveau nœud soit comparé à un nœud leaf, puis il est ajouté comme enfant droit ou gauche de ce nœud, en fonction de sa clé: si la clé est inférieure à la clé de la feuille, elle est insérée comme enfant gauche de la feuille, sinon comme enfant droit de la feuille.,

Il existe d’autres façons d’insérer des nœuds dans un arbre binaire, mais c’est le seul moyen d’insérer des nœuds aux feuilles tout en préservant la structure BST.

DeletionEdit

Lors de la suppression d’un nœud d’un arbre de recherche binaire, il est obligatoire de maintenir l’ordre de la séquence des nœuds. Il existe de nombreuses possibilités pour ce faire. Cependant, la méthode suivante qui a été proposée par T. Hibbard en 1962 garantit que les hauteurs des sous-arbres du sujet sont modifiées d’au plus un., Il y a trois cas possibles à considérer:

• suppression d’un nœud sans enfant: supprimez simplement le nœud de l’arborescence.
• suppression d’un nœud avec un enfant: supprimez le nœud et remplacez-le par son enfant.
• suppression d’un nœud D avec deux enfants: choisissez le prédécesseur dans L’ordre de D ou le successeur dans l’ordre E (voir figure). Au lieu de supprimer D, remplacez sa clé et sa valeur par E. Si E n’a pas d’enfant, supprimez E de son parent précédent G. Si E a un enfant F, c’est un bon enfant, de sorte qu’il doit remplacer E au parent de E.,

dans tous les cas, lorsque D se trouve être la racine, rendez le nœud de remplacement root à nouveau.

Les nœuds avec deux enfants sont plus difficiles à supprimer., Le successeur dans l’ordre d’un nœud est l’enfant le plus à gauche de son sous-arbre droit, et le prédécesseur dans l’ordre d’un nœud est l’enfant le plus à droite du sous-arbre gauche. Dans les deux cas, ce nœud n’aura qu’un seul enfant ou aucun enfant du tout. Supprimer selon l’un des deux cas les plus simples ci-dessus.

L’utilisation cohérente du successeur dans l’ordre ou du prédécesseur dans l’ordre pour chaque instance du cas à deux enfants peut conduire à une arborescence déséquilibrée, de sorte que certaines implémentations sélectionnent l’une ou l’autre à des moments différents.,

analyse D’exécution: bien que cette opération ne traverse pas toujours l’arbre jusqu’à une feuille, c’est toujours une possibilité; ainsi, dans le pire des cas, elle nécessite un temps proportionnel à la hauteur de l’arbre. Il n’en nécessite pas plus même lorsque le nœud a deux enfants, car il suit toujours un seul chemin et ne visite aucun nœud deux fois.,

TraversalEdit

Une fois l’arbre de recherche binaire créé, ses éléments peuvent être récupérés dans l’ordre en traversant récursivement le sous-arbre gauche du nœud racine, en accédant au nœud lui-même, puis en traversant récursivement le sous-arbre droit du nœud, en continuant Ce modèle avec chaque nœud de Comme pour tous les arbres binaires, on peut effectuer une traversée pré-commande ou une traversée post-commande, mais aucun n’est susceptible d’être utile pour les arbres de recherche binaires., Une traversée dans l’ordre d’un arbre de recherche binaire entraînera toujours une liste triée d’éléments de nœud (nombres, chaînes ou autres éléments comparables).

le code pour la traversée dans L’ordre en Python est donné ci-dessous. Il appellera callback (une fonction que le programmeur souhaite appeler sur la valeur du nœud, comme l’impression à l’écran) pour chaque nœud de l’arborescence.

La Traversée nécessite O(n) de temps, car elle doit visiter chaque nœud. Cet algorithme est également O (n), il est donc asymptotiquement optimal.

La traversée peut également être implémentée de manière itérative. Pour certaines applications, par exemple, une plus grande recherche égale, une recherche approximative, une opération de traversée en une seule étape (itérative) peut être très utile. Ceci est, bien sûr, implémenté sans la construction de rappel et prend O(1) en moyenne et O(log n) dans le pire des cas.

VerificationEdit

parfois, nous avons déjà un arbre binaire, et nous devons déterminer s’il s’agit d’un BST. Ce problème a une solution récursive.,

Le BST de la propriété—chaque nœud du sous-arbre droit doit être plus grand que l’actuel nœud et chaque nœud du sous-arbre gauche doit être plus petit que l’actuel nœud—est la clé pour déterminer si un arbre est un BST ou pas. L’algorithme gourmand-il suffit de parcourir l’arbre, à chaque nœud vérifier si le nœud contient une valeur supérieure à la valeur de l’enfant gauche et inférieure à la valeur de l’enfant droit—ne fonctionne pas pour tous les cas., Considérez l’arborescence suivante:

 20 / \ 10 30 / \ 5 40

dans l’arborescence ci-dessus, chaque nœud remplit la condition que le nœud contienne une valeur supérieure à son enfant gauche et plus petite que son enfant droit hold, et pourtant ce n’est pas un BST: la valeur 5 est sur le sous-arbre droit du nœud contenant

Au Lieu de prendre une décision basée uniquement sur les valeurs d’un nœud et de ses enfants, nous avons également besoin d’informations provenant du parent., Dans le cas de l’arbre ci-dessus, si nous pouvions nous souvenir du nœud contenant la valeur 20, nous verrions que le nœud avec la valeur 5 viole le contrat de propriété BST.,

donc, la condition que nous devons vérifier à chaque nœud est la suivante:

• si le nœud est l’enfant gauche de son parent, alors il doit être plus petit que (ou égal à) le parent et il doit transmettre la valeur de son parent à son sous-arbre droit pour s’assurer qu’aucun des nœuds de ce sous-arbre n’est supérieur au parent
• si le nœud est l’enfant droit de son parent, alors il doit être plus grand que le parent et il doit transmettre la valeur de son parent à son sous-arbre gauche à assurez-vous qu’aucun des nœuds de ce sous-arbre n’est inférieur au parent.,

Une solution récursive en C++ peut expliquer cela plus loin:

node->key+1 Et node->key-1 sont faits pour n’autoriser que des éléments distincts dans BST.

Si nous voulons que les mêmes éléments soient également présents, nous ne pouvons utiliser quenode->key aux deux endroits.

L’appel initial à cette fonction peut être quelque chose comme ceci:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

Essentiellement, nous continuons à créer une plage valide (à partir de ) et à la réduire pour chaque nœud lorsque nous descendons récursivement.,

comme indiqué dans la section #Traversal, une traversée dans l’ordre d’un arbre de recherche binaire renvoie les nœuds triés. Ainsi, il suffit de conserver le dernier nœud visité lors de la traversée de l’arbre et de vérifier si sa clé est plus petite (ou plus petite/égale, si les doublons doivent être autorisés dans l’arbre) par rapport à la clé actuelle.

algorithmsEdit Parallel

il existe également des algorithmes parallèles pour les arbres de recherche binaires, y compris l’Insertion/Suppression de plusieurs éléments, la construction à partir d’un tableau, le filtre avec un certain prédicateur, l’aplatissement en un tableau, la fusion/soustraction / intersection de deux arbres, etc., Ces algorithmes peuvent être implémentés à l’aide d’algorithmes d’arbre basés sur des jointures, qui peuvent également maintenir l’arbre équilibré à l’aide de plusieurs schémas d’équilibrage (y compris L’arbre AVL, l’arbre rouge-noir, l’arbre équilibré en poids et treap) .