J'essaie de rechercher le parent d'un nœud avec l'algorithme de Kruskal. Mon programme fonctionne très bien, mais je pense avoir entendu parler d'une méthode pour améliorer la vitesse de l'algorithme en reconstruisant l'arbre en cherchant le nœud parent et en le connectant au nœud parent. Je suis sûr que j'en ai entendu parler quelque part, peut-être dans une conférence. Quelqu'un peut-il me rafraîchir la mémoire? Et aussi, étant donné un certain nombre de tableaux, lors de la recherche de la valeur minimale et maximale d'une certaine section d'un tableau, quel est le nom de l'arbre qui peut calculer la valeur minimum/maximum du tableau en faisant un arbre binaire qui a la valeur minimum/maximum de chaque tableau dans O (log N)?Petites questions sur la structure des données
Répondre
Concernant votre deuxième question: Je pense que vous parlez d'un heap. Un tas peut vous récupérer au minimum ou maximum dans O (1) et le supprimer dans O (log n). Cependant, il existe des structures de données sophistiquées, qui sont destinées à gérer des listes complètes (c'est-à-dire qu'elles ne sont pas conçues pour des accès min/max en particulier). Ceux-ci prennent également en charge l'accès au minimum et maximum simultanément. Quelques exemples importants:
- Red-Black-Tree
- B-Tree (amorti O (log n))
- Splay-Tree (amorti O (log n))
Concernant votre première question: Kruskals algorithm est utilisé pour calculer un minimum spanning tree. Mais puisque vous mentionnez le "nœud parent", je suppose que votre structure considérée est déjà un arbre. Mais si la structure est déjà un arbre, l'algorithme de Kruskals renvoie simplement l'arbre lui-même. Pourriez-vous préciser ce que vous entendez par "nœud parent"?
Pour la première question, vous recherchez Disjoint-set data structure.
Pour la deuxième question, je suppose que vous posez des questions sur les requêtes de distance minimale/maximale. La structure de données pour cela est le Cartesian Tree.