[JAVA] Mémorandum d'arbre de bisection pour les débutants (1)

J'ai écrit un article de commentaire sur le demi-arbre pour un certain travail, mais pour diverses raisons, il n'a pas été utilisé. C'est un article enfantin, mais je l'ai écrit avec soin, alors faites-le moi savoir ici.

Tous ces articles s'appellent "Digital Series 10 Algorithms and Data Structures that Connect to the Future" (Superviseur: Shojiro Nishio, Auteurs: Takahiro Hara, Satoshi Mizuta, Takenao Okawa Editeur: Mitsuaki Nanjo Editeur: Kyoritsu Publishing Co., Ltd.) Je me réfère au livre. C'est un bon livre pour les débutants avec de nombreuses illustrations et pseudo-codes, alors lisez-le si vous êtes intéressé.

Bien qu'il soit étiqueté comme "pour les débutants", cet article est un article hostile sans illustrations, donc si vous avez vraiment une idée rafraîchissante de la bifurcation, vous pouvez le lire. Si vous lisez cet article et ne comprenez pas ce qu'il signifie, ce n'est pas de votre faute, mais de la faute de l'auteur.

Qu'est-ce qu'un arbre bifurqué?

Une arborescence est l'une des mêmes structures de données que les piles et les files d'attente. Par exemple, l'organigramme d'une entreprise a une belle structure en bois. Chaque poste tel que le président, le responsable de la conception, l'ingénieur serveur, etc. est appelé un nœud. La ligne reliant chaque nœud est appelée une arête. Les nœuds aux deux extrémités du côté sont appelés le parent en haut et l'enfant en bas. En d'autres termes, le responsable de la conception est le parent du concepteur et le concepteur est l'enfant du responsable de la conception. Comme le président, le nœud supérieur s'appelle la racine. Un nœud qui n'a pas d'enfants, tel qu'un concepteur ou un ingénieur, est appelé une feuille. Une structure arborescente dans laquelle chaque nœud a deux enfants ou moins est appelée un arbre dichotomisé. En d'autres termes, un arbre dichotomisé est composé d'une combinaison de nœuds et de côtés.

Exemple d'implémentation

C++

BinaryTree.cpp

#include <iostream>
using namespace std;

int main()
{
	string binaryTree[7] = {"Président", "Responsable conception", "Responsable ingénieur",
												  "designer", "", "Ingénieur serveur", "Ingénieur infrastructure"};

	//Le parent est 0
	cout << binaryTree[0] << endl;
	//Les enfants du responsable ingénieur (index 2) sont des ingénieurs serveur et des ingénieurs infrastructure.
	cout << binaryTree[2 * 2 + 1] + ", " + binaryTree[2 * 2 + 2] << endl;
}

Java

BinaryTree.java

public class BinaryTree {
	public static void main(String[] args) {
		String[] binaryTree = {"Président", "Responsable conception", "Responsable ingénieur",
													 "designer", "", "Ingénieur serveur", "Ingénieur infrastructure"};

		//Le parent est 0
		System.out.println(binaryTree[0]);
		//Les enfants du responsable ingénieur (index 2) sont des ingénieurs serveur et des ingénieurs infrastructure.
		System.out.println(binaryTree[2 * 2 + 1] + ", " + binaryTree[2 * 2 + 2]);
	}
}

Explication sur la mise en œuvre

Une dichotomie peut être obtenue en utilisant un tableau. Formellement, l'index racine est d'abord défini sur 0. Pour les nœuds autres que la racine, lorsque l'index parent est k, l'index enfant gauche est 2k + 1 et l'index enfant droit est 2k + 2. Si vous avez un enfant, faites-en l'enfant gauche et l'enfant droit vides. Après avoir attribué un index à chaque nœud, il est complété par le stockage des données du contact dans le tableau en fonction de l'index.

Exemple d'utilisation

La structure arborescente est une structure de données adaptée lorsqu'il existe une relation d'ordre telle que la hiérarchie et la taille entre les données. Étant donné que les données sont organisées régulièrement, vous pouvez effectuer une recherche rapidement si vous décidez à l'avance comment les organiser. Il y a des arbres en tas et des arbres dichotomisés comme dichotomies qui profitent de cette propriété.

Précautions d'application

Comme je l'ai mentionné précédemment, cela fonctionne bien pour les données ordonnées, mais inversement, il est impuissant pour les données non ordonnées. De plus, même s'il existe une relation d'ordre, si les entrées sont données dans cet ordre, un arbre en forme de liste sera créé, avec uniquement l'enfant gauche ou droit. De plus, si vous utilisez l'implémentation en utilisant le tableau décrit précédemment, vous devrez allouer de la mémoire aux enfants vides, ce qui est inutile. C'est une caractéristique des tableaux que la mémoire est gaspillée pour des données rares. En d'autres termes, l'implémentation basée sur un tableau convient aux dichotomies denses sans enfants vides au milieu. Un arbre dense bifurqué est surtout appelé un arbre dichotomisé complet. Pour être précis, un arbre dichotomisé dans lequel toutes les feuilles sont justifiées à gauche sans aucun espace aux nœuds qui ne sont pas des feuilles est appelé un arbre dichotomisé complet. Une dichotomie qui n'est pas une dichotomie complète peut être réalisée en utilisant des classes pour éliminer le gaspillage de mémoire.

Partie 2 est ici