Quelles sont les applications des arbres binaires ?

Question

Je me demande quelles sont les applications particulières des arbres binaires. Pourriez-vous me donner quelques exemples concrets ?

Answer 1

Se chamailler sur les performances de arbres binaires n'a pas de sens - il ne s'agit pas d'une structure de données, mais d'une famille de structures de données, ayant toutes des caractéristiques de performance différentes. S'il est vrai que arbres binaires non équilibrés sont beaucoup moins performants que arbres binaires auto-équilibrés pour la recherche, il existe de nombreux arbres binaires (comme les essais binaires) pour laquelle "équilibrage" n'a pas de sens.

Applications des arbres binaires

• Arbre de recherche binaire - Utilisé dans beaucoup de les applications de recherche où les données entrent et sortent en permanence, telles que la map y set dans les bibliothèques de nombreux langages.
• Partition de l'espace binaire - Utilisé dans presque tous les jeux vidéo 3D pour déterminer quels objets doivent être rendus.
• Essais binaires - Utilisé dans presque tous les routeurs à large bande passante pour stocker les tables de routeur.
• Arbres de hachage - Utilisé dans les torrents et les signatures d'images spécialisées dans lesquels un hachage doit être vérifié, mais le fichier entier n'est pas disponible. Également utilisé dans les chaînes de blocs, par exemple le bitcoin.
• Amas - Utilisé pour la mise en œuvre de files d'attente prioritaires efficaces, qui sont à leur tour utilisées pour l'ordonnancement des processus dans de nombreux systèmes d'exploitation, la qualité de service dans les routeurs, et A*. (algorithme de recherche de chemin utilisé dans les applications d'IA, notamment la robotique et les jeux vidéo) . Également utilisé dans heap-sort.
• Arbre de codage de Huffman ( Chip Uni ) - Utilisé dans les algorithmes de compression, tels que ceux utilisés par les formats de fichiers .jpeg et .mp3.
• Arbres GGM - Utilisé dans les applications cryptographiques pour générer un arbre de nombres pseudo-aléatoires.
• Arbre syntaxique - Construit par les compilateurs et (implicitement) les calculateurs pour analyser les expressions.
• Treap - Structure de données aléatoires utilisée dans les réseaux sans fil et l'allocation de mémoire.
• Arbre en T - Bien que la plupart des bases de données utilisent une forme d'arbre B pour stocker les données sur le disque, les bases de données qui conservent toutes (ou la plupart) de leurs données en mémoire utilisent souvent des arbres T pour le faire.

---

La raison pour laquelle les arbres binaires sont plus souvent utilisés que les arbres n-aires pour la recherche est que les arbres n-aires sont plus complexes, mais n'offrent généralement aucun avantage réel en termes de vitesse.

Dans un arbre binaire (équilibré) avec m nœuds, passer d'un niveau à l'autre nécessite une comparaison, et il y a log_2(m) niveaux, pour un total de log_2(m) comparaisons.

En revanche, un arbre n-aire nécessitera log_2(n) comparaisons (en utilisant une recherche binaire) pour passer au niveau supérieur. Puisqu'il y a log_n(m) total des niveaux, la recherche nécessitera log_2(n)*log_n(m) = log_2(m) total des comparaisons. Ainsi, bien que les arbres n-aires soient plus complexes, ils ne présentent aucun avantage en termes de nombre total de comparaisons nécessaires.

(Toutefois, les arbres n-aires sont toujours utiles dans les situations de niche. Les exemples qui viennent immédiatement à l'esprit sont quadri-arbres et d'autres arbres de division de l'espace, où la division de l'espace en utilisant seulement deux nœuds par niveau rendrait la logique inutilement complexe ; et Arbres B utilisé dans de nombreuses bases de données, où le facteur limitant n'est pas le nombre de comparaisons effectuées à chaque niveau, mais le nombre de nœuds pouvant être chargés simultanément à partir du disque dur).

Answer 2

Lorsque la plupart des gens parlent d'arbres binaires, ils pensent le plus souvent aux arbres binaires. recherche arbres, donc je vais couvrir ça en premier.

Un arbre de recherche binaire non équilibré n'est en fait guère plus utile que pour enseigner aux étudiants les structures de données. En effet, à moins que les données n'arrivent dans un ordre relativement aléatoire, l'arbre peut facilement dégénérer en sa forme la plus défavorable, qui est une liste liée, puisque les arbres binaires simples sont no équilibré.

Un bon exemple : j'ai eu à réparer un logiciel qui chargeait ses données dans un arbre binaire pour les manipuler et les rechercher. Il écrivait les données sous forme triée :

Alice
Bob
Chloe
David
Edwina
Frank

de sorte que, en le relisant, on obtient l'arbre suivant :

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

qui est la forme dégénérée. Si vous cherchez Frank dans cet arbre, vous devrez chercher dans les six nœuds avant de le trouver.

Les arbres binaires deviennent vraiment utiles pour la recherche lorsque vous les équilibrez. Cela implique de faire tourner les sous-arbres à travers leur nœud racine de manière à ce que la différence de hauteur entre deux sous-arbres soit inférieure ou égale à 1. Si l'on ajoute les noms ci-dessus, un par un, dans un arbre équilibré, on obtient la séquence suivante :

1.   Alice
    /     \
   =       =

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

Vous pouvez en fait voir des sous-arbres entiers tourner vers la gauche (aux étapes 3 et 6) au fur et à mesure que les entrées sont ajoutées, ce qui vous donne un arbre binaire équilibré dans lequel la consultation la plus défavorable est la suivante O(log N) plutôt que le O(N ) que la forme dégénérée donne. A aucun moment, le NULL le plus élevé ( = ) diffèrent des plus bas de plus d'un niveau. Et, dans l'arbre final ci-dessus, vous pouvez trouver Frank en regardant seulement trois noeuds ( Chloe , Edwina et, enfin, Frank ).

Bien sûr, ils peuvent devenir encore plus utiles lorsque vous les rendez équilibrés multi-voies des arbres plutôt que des arbres binaires. Cela signifie que chaque nœud contient plus d'un élément (techniquement, ils contiennent N éléments et N+1 pointeurs, un arbre binaire étant un cas particulier d'un arbre multivoie à 1 voie, avec 1 élément et 2 pointeurs).

Avec un arbre à trois voies, on se retrouve avec :

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

Cette fonction est généralement utilisée pour gérer les clés d'un index d'éléments. J'ai écrit un logiciel de base de données optimisé pour le matériel où un nœud a exactement la taille d'un bloc de disque (disons 512 octets) et où vous mettez autant de clés que vous pouvez dans un seul nœud. Le site pointeurs dans ce cas, étaient en fait des numéros d'enregistrement dans un fichier à accès direct de longueur fixe distinct du fichier d'index (donc le numéro d'enregistrement X pourrait être trouvé en cherchant simplement à X * record_length ).

Par exemple, si les pointeurs sont de 4 octets et que la taille des clés est de 10, le nombre de clés dans un nœud de 512 octets est de 36. Cela représente 36 clés (360 octets) et 37 pointeurs (148 octets) pour un total de 508 octets avec 4 octets gaspillés par nœud.

L'utilisation de clés multivoie introduit la complexité d'une recherche en deux phases (une recherche multivoie pour trouver le bon nœud combinée à une petite recherche séquentielle (ou binaire linéaire) pour trouver la bonne clé dans le nœud) mais l'avantage de faire moins d'E/S disque compense largement.

Je ne vois aucune raison de faire cela pour une structure en mémoire, vous feriez mieux de vous en tenir à un arbre binaire équilibré et de garder votre code simple.

N'oubliez pas non plus que les avantages de O(log N) en O(N) n'apparaissent pas vraiment lorsque vos ensembles de données sont petits. Si vous utilisez un arbre à plusieurs voies pour stocker les quinze personnes de votre carnet d'adresses, c'est probablement trop. Les avantages apparaissent lorsque vous stockez quelque chose comme toutes les commandes de vos cent mille clients au cours des dix dernières années.

L'intérêt de la notation big-O est d'indiquer ce qui se passe lorsque le système N s'approche de l'infini. Certaines personnes peuvent ne pas être d'accord, mais il est même possible d'utiliser le tri à bulles si vous êtes sûr que les ensembles de données resteront en dessous d'une certaine taille, tant que rien d'autre n'est facilement disponible :-)

---

Quant aux autres utilisations des arbres binaires, il en existe un grand nombre, comme par exemple :

• Les tas binaires où les clés supérieures sont supérieur ou égal à inférieurs plutôt qu'à gauche de (ou en dessous ou égal à et à droite) ;
• Les arbres de hachage, similaires aux tables de hachage ;
• Arbres syntaxiques abstraits pour la compilation de langages informatiques ;
• Arbres de Huffman pour la compression de données ;
• Arbres de routage pour le trafic réseau.

Étant donné la quantité d'explications que j'ai générées pour les arbres de recherche, je suis réticent à entrer dans beaucoup de détails sur les autres, mais cela devrait suffire pour les rechercher, si vous le souhaitez.

Answer 3

Un arbre binaire est une structure de données arborescente dans laquelle chaque nœud a au plus deux nœuds enfants, généralement distingués comme "gauche" et "droit". Les nœuds ayant des enfants sont des nœuds parents, et les nœuds enfants peuvent contenir des références à leurs parents. À l'extérieur de l'arbre, il y a souvent une référence au nœud "racine" (l'ancêtre de tous les nœuds), s'il existe. On peut atteindre n'importe quel nœud de la structure de données en commençant par le nœud racine et en suivant de manière répétée les références à l'enfant gauche ou droit. Dans un arbre binaire, le degré de chaque nœud est de deux au maximum.

Les arbres binaires sont utiles, car comme vous pouvez le voir sur l'image, si vous voulez trouver n'importe quel nœud de l'arbre, vous ne devez regarder que 6 fois au maximum. Si vous souhaitez rechercher le nœud 24, par exemple, vous devez commencer par la racine.

• La Racine a une valeur de 31, qui est supérieure à 24, donc vous allez au noeud de gauche.
• Le nœud de gauche a une valeur de 15, ce qui est inférieur à 24, vous passez donc au nœud de droite.
• Le nœud de droite a une valeur de 23, qui est inférieure à 24, donc vous allez au nœud de droite.
• Le nœud de droite a une valeur de 27, qui est supérieure à 24, donc vous passez au nœud de gauche.
• Le nœud de gauche a une valeur de 25, qui est supérieure à 24, donc vous allez au nœud de gauche.
• Le nœud a une valeur de 24, qui est la clé que nous recherchons.

Cette recherche est illustrée ci-dessous :

Vous pouvez voir que vous pouvez exclure la moitié des nœuds de l'arbre entier lors du premier passage et la moitié du sous-arbre de gauche lors du second. Cela permet d'effectuer des recherches très efficaces. Si cela était fait sur 4 milliards d'euros éléments, vous n'auriez à effectuer que 32 recherches au maximum. Par conséquent, plus l'arbre contient d'éléments, plus votre recherche sera efficace.

Les suppressions peuvent devenir complexes. Si le nœud a 0 ou 1 enfant, il suffit de déplacer quelques pointeurs pour exclure celui qui doit être supprimé. Cependant, vous ne pouvez pas facilement supprimer un noeud avec 2 enfants. Nous prenons donc un raccourci. Disons que nous voulons supprimer le nœud 19.

Comme il n'est pas facile de déterminer où déplacer les pointeurs gauche et droit, nous en trouvons un pour le remplacer. Nous allons dans le sous-arbre de gauche, et allons aussi loin que possible à droite. Cela nous donne la prochaine plus grande valeur du nœud que nous voulons supprimer.

Maintenant, nous copions tout le contenu de 18, à l'exception des pointeurs gauche et droit, et nous supprimons le nœud 18 original.

---

Pour créer ces images, j'ai implémenté un arbre AVL, un arbre auto-équilibrant, de sorte qu'à tout moment, l'arbre a au plus un niveau de différence entre les nœuds feuilles (nœuds sans enfants). Cela permet d'éviter que l'arbre ne devienne asymétrique et de maintenir l'écart maximal entre les deux. O(log n) temps de recherche, au prix d'un peu plus de temps nécessaire pour les insertions et les suppressions.

Voici un exemple montrant comment mon arbre AVL s'est maintenu aussi compact et équilibré que possible.

Dans un tableau trié, les recherches prendraient toujours O(log(n)) comme un arbre, mais l'insertion et la suppression aléatoires prendraient O(n) au lieu de l'arbre O(log(n)) . Certains conteneurs STL utilisent ces caractéristiques de performance à leur avantage de sorte que les temps d'insertion et de retrait prennent un maximum de O(log n) ce qui est très rapide. Certains de ces conteneurs sont map , multimap , set y multiset .

Un exemple de code pour un arbre AVL se trouve à l'adresse suivante http://ideone.com/MheW8

Answer 4

L'application principale est arbres de recherche binaires . Il s'agit d'une structure de données dans laquelle la recherche, l'insertion et la suppression sont toutes très rapides (environ 1,5 million d'euros). log(n) opérations)

Answer 5

• Les arbres binaires sont utilisés dans Codage de Huffman qui sont utilisés comme code de compression.
• Les arbres binaires sont utilisés dans Arbres de recherche binaires qui sont utiles pour conserver des enregistrements de données sans trop d'espace supplémentaire.