Pourquoi les arbres binaires sont-ils importants?

les arbres binaires sont la forme la plus simple des arbres à voies multiples donc ils sont plus faciles à étudier dans ce sens.

les arbres multidirectionnels ont des noeuds qui consistent en N clés et N+1 pointeurs, dans le sens de:

               |
   +-----+-----+-----+-----+
   | k00 | k01 | k02 | k03 |
   +-----+-----+-----+-----+
  /      |     |     |      \
p00     p01   p02   p03     p04

pour trouver quel pointeur suivre dans une recherche, vous comparez la clé que vous recherchez avec les clés du noeud. Cet exemple ci-dessus est un arbre multidirectionnel de l'ordre-2 (Je définit l'ordre n avoir 2n clés et 2n+1 pointeur.)

quand vous "dégénérez" cette structure pour avoir le plus petit noeud possible, vous vous retrouvez avec une clé et deux pointeurs, votre arbre binaire classique:

      |
   +-----+
   | k00 |
   +-----+
  /       \
p00       p01

quand je suis allé à l'université( et j'avoue que c'était il y a un moment), nous avons étudié les arbres binaires premier, simplement parce que les algorithmes étaient élégants. La recherche était un simple noeud de comparaison et de choisir l'un des deux sous-arbres. L'Insertion et la suppression ont également été relativement facile.

Puis nous sommes allés sur équilibre arbres binaires, où la recherche était exactement la même, mais l'insertion et la suppression étaient un peu plus compliquées, impliquant la "rotation" des sous-arbres à travers la racine du sous-arbre lorsque cela était nécessaire pour le maintenir en équilibre.

cela a ensuite été suivi par des arbres multidirectionnels non équilibrés pour obtenir le concept de recherche dans un noeud une fois que vous avez trouvé le noeud correct puis, enfin, les arbres multidirectionnels équilibrés qui étaient essentiellement les mêmes que les arbres binaires, mais avec la même complexité ajoutée d'une recherche séquentielle, ainsi que l'insertion ou la suppression dans le noeud et la combinaison et le crachage des noeuds eux-mêmes.

À chacune de ces étapes vous simplement ajouté un peu plus de complexité des algorithmes. Je ne me souviens pas que beaucoup de gens aient eu des problèmes avec cette progression donc peut-être que tous les manuels que vous mentionnez sont juste au niveau de démarrage.

je n'ai jamais vraiment trouvé plusieurs arbres plus utile que des binaires arbres sauf dans une situation très spécifique. C'est quand vous lisez les noeuds de l'arbre à partir d'un milieu lent comme le disque et vous avez optimisé pour les secteurs/cluster/blocs de tailles.

nous avons développé une implémentation d'arbre multi-way sous OS / 2 (montrant mon âge ici) qui a crié le long, en s'assurant que les noeuds étaient identiques en taille aux blocs de disque sous-jacents. Même si cela pouvait entraîner une perte d'espace, les améliorations de la vitesse en valaient la peine.

Pour la mémoire des trucs, les arbres binaires ont tous les avantages du multi-voies sans aucune des complications supplémentaires (devant combiner la recherche séquentielle d'un noeud avec la sélection de sous-arbres).

les arbres binaires se résument comme suit: "doit-on se déplacer à gauche ou à droite?", multi-voies sont " Où est la clé dans ce noeud afin que nous puissions choisir le sous-arbre?".