Questions sur les arbres de recherche, une classe de structures de données utilisée pour stocker des données triées pour un accès efficace.
Il semble que partout où je regarde, les structures de données sont mises en œuvre en utilisant des arbres rouges-noirs ( std::seten C ++, SortedDictionaryen C #, etc.) Après avoir couvert (a, b), les arbres rouge-noir et AVL dans mon cours d’algorithme, voici ce que j’ai dégagé (aussi en...
Supposons la définition suivante d'un arbre rouge-noir: C'est un arbre de recherche binaire. Chaque nœud est coloré en rouge ou en noir. La racine est noire. Deux nœuds reliés par une arête ne peuvent pas être rouges en même temps. Ici devrait être une bonne définition d'une feuille NIL, comme sur...
Intuitivement, les "arbres équilibrés" devraient être des arbres où les sous-arbres gauche et droit de chaque nœud doivent avoir "approximativement le même" nombre de nœuds. Bien sûr, lorsque nous parlons d'équilibrage des arbres rouge-noir * (voir définition à la fin), nous voulons en fait dire...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Je ne comprends pas très bien pourquoi la rotation dans la structure de données de l'arbre d'affichage prend en compte non seulement le parent du nœud de notation, mais aussi le grand-parent (opération zig-zag et zig-zig). Pourquoi les éléments suivants ne fonctionneraient-ils pas: Lorsque nous...
Dans une question précédente, il y avait une définition des arbres à poids équilibré et une question concernant les arbres rouge-noir. Cette question est de poser la même question, mais pour les arbres AVL . La question est, étant donné la définition d' arbres à μμ\mu équilibré comme dans l'autre...
J'ai lu un peu de littérature récemment et j'ai trouvé des structures de données plutôt intéressantes. J'ai recherché différentes méthodes pour réduire le temps de mise à jour au temps de mise à jour du pire cas [1-7].O ( 1 )O(1)\mathcal{O}(1) Récemment, j'ai commencé à chercher des structures de...
J'ai une affectation où je dois utiliser un arbre de recherche binaire et le modifier pour s'auto-ordonner de telle sorte que les éléments qui sont le plus consultés (ont une priorité plus élevée) soient en haut de l'arbre, la racine étant le nœud le plus consulté . Le professeur m'a donné le BST...
Une question d'entretien courante consiste à fournir un algorithme pour déterminer si un arbre binaire donné est équilibré en hauteur (définition de l'arbre AVL). Je me demandais si nous pouvions faire quelque chose de similaire avec les arbres rouges-noirs. Étant donné un arbre binaire non coloré...
Dans l' introduction aux algorithmes de Cormen et al. , La section 15.3 Éléments de programmation dynamique explique la mémorisation comme suit: Un algorithme récursif mémorisé conserve une entrée dans une table pour la solution de chaque sous-problème. Chaque entrée de table contient initialement...
J'ai la question suivante, mais je n'ai pas de réponse à cela. J'apprécierais si ma méthode est correcte: Q. Lors de la recherche de la valeur de clé 60 dans une arborescence de recherche binaire, les nœuds contenant les valeurs de clé 10, 20, 40, 50, 70, 80, 90 sont parcourus, pas nécessairement...
Cette question explique à peu près qu'ils peuvent, mais ne montre aucun exemple de l'existence de deux arbres différents avec le même parcours de pré-ordre. Il est également mentionné que la traversée dans l'ordre de deux arbres différents peut être la même bien qu'ils soient structurellement...
Je me bats avec le matériel de hachage et d'arbre de recherche binaire. Et j'ai lu qu'au lieu d'utiliser des listes pour stocker des entrées avec les mêmes valeurs de hachage, il est également possible d'utiliser des arbres de recherche binaires. Et j'essaie de comprendre quel est le temps...
Comment prouvez-vous que la hauteur attendue d'un arbre de recherche binaire construit de façon aléatoire avec nœuds est ? Il y a une preuve dans CLRS Introduction to Algorithms (chapitre 12.4), mais je ne la comprends pas.O ( log n )nnnO(logn)O(Journaln)O(\log
Je dois conserver une collection d'entiers compris entre 0 et 65535 afin de pouvoir effectuer rapidement les opérations suivantes: Insérer un nouvel entier Insérer une plage d'entiers contigus Supprimer un entier Supprimer tous les entiers sous un entier Tester si un entier est présent Mes données...
J'essaie de comprendre comment les arbres indexés binaires (arbres fenwick) peuvent être modifiés pour gérer à la fois les requêtes de plage et les mises à jour de plage. J'ai trouvé les sources suivantes: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/...
Je comprends que les arbres du segment peuvent être utilisés pour trouver la somme de tableau sous de . Et que cela peut se faire en temps selon le tutoriel ici .O ( log n )UNEAAO (logn )O(logn)\mathcal{O}(\log n) Cependant, je ne suis pas en mesure de prouver que le temps d'interrogation est bien...
Une SkipList fournit les mêmes limites pour la recherche qu'un arbre équilibré avec l'avantage qu'un rééquilibrage n'est pas nécessaire. Étant donné que la SkipList est construite à l'aide de retournements de pièces aléatoires, ces limites ne tiennent que tant que la structure de la SkipList est...
L'opération de fractionnement peut-elle être mise en œuvre pour les arbres AVL complexes O(logn)O(logn)O(\log n)? Je suis intéressé par des liens vers des articles ou toute information spécifique sur ce sujet. L'opération de division divise l'arborescence AVL en deux arborescences AVL dérivées, en...
Dans les applications du monde réel, y a-t-il un avantage concret à utiliser les algorithmes O(log(log(n))O(log(log(n))\mathcal{O}(\log(\log(n)) au lieu des algorithmes O(log(n))O(log(n))\mathcal{O}(\log(n)) ? C'est le cas lorsque l'on utilise par exemple des arbres van Emde Boas au lieu...