En ce qui concerne les arbres ébrasés

Question

Je suis en train de lire sur les arbres ébrasés dans les structures de données et algorithmes par Mark Allen Wesis

La stratégie de évasement est similaire à l'idée de rotation, à l'exception que nous sont un peu plus sélectif sur la façon dont les rotations sont effectuées. Nous allons faire tourner encore en bas le long du chemin d'accès. Soit x un (nonroot) nœud sur le chemin d'accès auquel nous tourne. Si le parent de x est la racine de l'arbre, nous x et la racine simplement rotate. C'est le dernière rotation le long du chemin d'accès. Dans le cas contraire, x est à la fois un parent (P) et un grand-parent (g), et il existe deux cas, en plus de symétries, à envisager. Le premier cas est le cas en zig-zag, ici x est un droit enfant et p est un enfant gauche (ou vice versa). Si tel est le cas, nous effectuer une double rotation, exactement comme une double rotation AVL. Dans le cas contraire, nous avons un cas de zig-zig: x et p sont soit à la fois à gauche les enfants ou les enfants droit.

Dans le texte ci-dessus que signifie l'auteur en suivant la déclaration « Il y a deux cas, plus symétries »? deux cas sont donnés, mais ce sont symmetires ici?

Merci!

Answer 1

Je pense qu'il est juste assez symetry axiale de base:

exemple pour une zig zag, voici 2 arbres symetriques:

     g
    / \ 
    p  d
   /\
  c  x
    / \
   a   b

     g
    / \ 
   d   p
      /\
     x  c
    / \
   a   b

Answer 2

Par exemple, dire un cas est « Lorsque le nœud dans les questions est l'enfant droit de son parent et le parent est l'enfant gauche du grand-parent » Dans ce cas, vous faites une rotation à gauche, puis une rotation à droite. Ainsi, le nœud viendra au grand-parent.

La partie symétrique de ce cas est « Lorsque le nœud dans les questions est l'enfant gauche de son parent et le parent est l'enfant le droit des grands-parents » Dans ce cas, vous faites une rotation à droite, puis une rotation gauche. Ainsi, le nœud viendra au grand-parent.

remplaçons gauche avec droite et de droite à gauche, vous obtenez le cas symétrique.

Il n'y a que 3 cas de rotation dans un arbre évasement. Vous pouvez voir la différence d'exécution dans la recherche avec et sans évasement.