Efficacité dynamique : Algorithmes pour le maintien des arbres de recherche binaires

ISBN-13: 9786208248826 / Francuski / Miękka / 2024 / 60 str.

Iman Sabah Mustafa; Yogesh Kumar Awasthi

Opis

Un arbre de recherche binaire (BST) optimise les opérations de recherche en organisant les données pour des recherches, des insertions et des suppressions rapides. Divers algorithmes d'équilibrage, y compris les rotations simples et doubles, ont été développés pour maintenir cette efficacité. Bien que les doubles rotations soient efficaces, elles consomment plus de ressources informatiques, ce qui peut avoir un impact sur les performances du système dans les environnements où les recherches sont fréquentes. Les évaluations des différents algorithmes de maintien dynamique des BST se concentrent sur les modèles de recherche imprévisibles, en gérant des tâches telles que l'insertion de nouveaux noeuds et la restructuration de l'arbre afin de réduire la longueur du chemin et le temps de recherche. Les arbres à hauteur équilibrée, tels que les arbres AVL, maintiennent des différences de hauteur minimales entre les sous-arbres pour des recherches efficaces, tandis que les arbres à équilibre limité, tels que les arbres rouge-noir, permettent un équilibrage plus souple pour des opérations spécifiques. Les algorithmes hybrides combinent les caractéristiques des deux types d'arbres pour améliorer les performances. L'article présente une nouvelle méthode qui améliore les doubles rotations et permet d'obtenir des résultats d'équilibrage similaires avec près de la moitié des étapes de calcul.