Je connais les moyens de garder les arbres de recherche binaires équilibrés / auto-équilibrés à l'aide de rotations.

Je ne sais pas si mon cas doit être aussi compliqué. Je n'ai pas besoin de maintenir une propriété d'ordre trié comme avec les BST auto-équilibrés. J'ai juste un arbre binaire ordinaire dont je pourrais avoir besoin pour supprimer des nœuds ou insérer des nœuds. J'ai besoin d'essayer de maintenir l'équilibre dans l'arbre. Pour plus de simplicité, mon arbre binaire est similaire à un arbre de segments, et chaque fois qu'un nœud est supprimé, tous les nœuds le long du chemin de la racine à ce nœud seront affectés (dans mon cas, c'est juste une soustraction des valeurs nodales) . De même, chaque fois qu'un nœud est inséré, tous les nœuds de la racine à l'emplacement final du nœud inséré seront affectés (un ajout aux valeurs nodales cette fois).

Quelle serait la manière la plus simple de maintenir un arbre comme celui-ci en équilibre? Il n'a pas besoin d'être strictement aussi équilibré en hauteur que les arbres AVL, mais quelque chose comme les arbres RB ou peut-être légèrement moins équilibré est également acceptable.

1
user5965026 13 mars 2021 à 05:14

1 réponse

Lors de l'équilibrage des non-BST, la grande question à se poser est

Votre arbre peut-il supporter efficacement les rotations?

Certains types d'arbres binaires, comme les arbres k-d, ont une structure couche par couche spécifique qui rend les rotations irréalisables. D'autres, comme les arbres de plage, ont des métadonnées auxiliaires dans chaque nœud qui coûtent cher à mettre à jour après une rotation. Mais si vous pouvez gérer les rotations, vous pouvez utiliser à peu près n'importe quelle stratégie d'équilibrage. L'option la plus simple pourrait être de modéliser votre arbre sur un treap: placez un champ de poids choisi au hasard dans chaque nœud, puis, lors des insertions, faites pivoter votre feuille nouvellement ajoutée jusqu'à ce que son poids soit inférieur à celui de son parent. Pour supprimer, faites pivoter à plusieurs reprises le nœud avec son enfant plus clair jusqu'à ce qu'il s'agisse d'une feuille, puis supprimez-le.

Si vous ne pouvez pas prendre en charge les rotations, vous aurez besoin d'une stratégie de rééquilibrage qui n'en nécessite pas. L'option la plus simple est peut-être de modéliser votre arbre d'après un arbre de bouc émissaire, qui fonctionne en détectant paresseusement un nœud trop profond pour que l'arbre soit équilibré, puis en reconstruisant le plus petit sous-arbre déséquilibré possible en un arbre parfaitement équilibré pour tout remettre en place. ordre. Les suppressions sont gérées en reconstruisant l'arborescence entière une fois que le nombre de nœuds diminue d'un facteur constant.

0
templatetypedef 13 mars 2021 à 02:42