Un arbre AVL avec la répétition des valeurs et de la double comparaison

Question 1

J'ai besoin de créer une structure de données (principalement à l'aide de AVL arbres) des objets avec deux valeurs: niveau (n'est pas unique) et id (unique).

J'ai besoin de soutien à la recherche par id, l'impression par l'ordre des niveaux, ainsi que la fusion de deux de ces arbres et de maintenir ces fonctionnalités avec la nouvelle arborescence.

J'ai déjà plusieurs solutions dans l'esprit, mais je voulais vous demander à propos de l'un spécifique:

Il travaillera à mettre en œuvre cette structure avec un singulier AVL arbre où deux nœuds sont d'abord comparées en fonction de leur niveau, et puis leurs id? Surtout j'ai du mal à comprendre comment la fusion de deux de ces arbres pourraient travailler, en particulier dans le cas que nous avons Un arbre où tous les objets sont de niveau x et de l'arbre B, où tous les objets sont de niveau y de la.

EDIT: pour la recherche de l'id en outre, il y aura un arbre seulement triés par id.

Pourrait cette méthode de travail?

Question 2

singulier AVL arbre où deux nœuds sont d'abord comparées en fonction de leur niveau, et puis leurs id?

Malheureusement pas. Si vous faites cela, vous ne serez pas en mesure de trouver efficacement un nœud par son id -- vous aurez besoin de regarder à travers tous les possibles "niveaux", que vous n'avez pas spécifié, donc je suppose qu'ils peuvent être sans limite.

Je pense que vous pouvez insérer chaque nœud en deux AVL arbres de la place. Un arbre AVL commande les nœuds par niveau, les autres par leur id. Toutes les requêtes, des insertions, des suppressions et fusions peut être fait sur chaque arbre séparément.

En d'autres termes, vous devez créer deux index sur vos données.

Dans le code:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

EDIT: pour la recherche de l'id en outre, il y aura un arbre seulement triés par id.

Alors vous décrivent essentiellement la même chose que moi. Toutefois, votre arbre c'est trié par le composite (level, id) la clé, c'est du gaspillage; tous vous avez besoin est un arbre trié par (level) et un arbre trié par (id) (scalaire touches). Il n'y a pas besoin, parmi les opérations que vous avez fourni, pour trier par (level, id) et (id).

Yakov Galka · Answer 1 · 2021-11-23T19:29:44

singulier AVL arbre où deux nœuds sont d'abord comparées en fonction de leur niveau, et puis leurs id?

Malheureusement pas. Si vous faites cela, vous ne serez pas en mesure de trouver efficacement un nœud par son id -- vous aurez besoin de regarder à travers tous les possibles "niveaux", que vous n'avez pas spécifié, donc je suppose qu'ils peuvent être sans limite.

Je pense que vous pouvez insérer chaque nœud en deux AVL arbres de la place. Un arbre AVL commande les nœuds par niveau, les autres par leur id. Toutes les requêtes, des insertions, des suppressions et fusions peut être fait sur chaque arbre séparément.

En d'autres termes, vous devez créer deux index sur vos données.

Dans le code:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

EDIT: pour la recherche de l'id en outre, il y aura un arbre seulement triés par id.

Alors vous décrivent essentiellement la même chose que moi. Toutefois, votre arbre c'est trié par le composite (level, id) la clé, c'est du gaspillage; tous vous avez besoin est un arbre trié par (level) et un arbre trié par (id) (scalaire touches). Il n'y a pas besoin, parmi les opérations que vous avez fourni, pour trier par (level, id) et (id).

Merci pour la réponse, malheureusement j'ai juste oublié de mentionner qu'en plus je vais avoir un arbre triés par id pour cette fonctionnalité. J'ai pensé à vous la solution je viens vous demandez-vous à propos de cette solution particulière à un camarade de classe m'a dit ce qui je pense ne va pas travailler en raison de la fusion,
@user3917631: un arbre triés par (niveau, id) est également triés par (niveau). Donc si vous avez un arbre triés par (id) en plus de l'une de ces, vous serez en mesure de faire efficacement des opérations comme je l'ai décrit. C'est un peu du gaspillage de trier par (niveau, id) si vous avez besoin d' (niveau).
Je sais, je ne fais que demander de sortir d'intérêt, cela peut-il fonctionner? Est-il possible d'avoir deux arbres triés par (niveau, id) les nombres entiers et les fusionner en O(n) (n nombre de combinés nœuds).
@user3917631: oui c'est possible, et ne diffère pas de la fusion de deux arbres triés par quoi que ce soit d'autre. Arbres binaires sont basé sur des comparaisons, afin de ne pas "attention" à ce que vous êtes en utilisant votre clé, tant que c'est un totalement jeu ordonné. Un n-uplet de nombres entiers est un DE jeu. Article de wikipédia sur les arbres AVL décrit la façon de faire efficace de fusion; de là il est appelé à un syndicat. Cependant, vous voudrez peut-être stocker nœud de hauteur au lieu d'un facteur de le faire.

Un arbre AVL avec la répétition des valeurs et de la double comparaison

La question

La meilleure réponse

Dans d'autres langues

Cette page est dans d'autres langues

Populaires dans cette catégorie

Questions populaires dans cette catégorie