Equilibrer l'arbre BST manuellement

Question

J'ai fait l'équilibrage de l'arbre (bst> avl) demandé à la main et je me demande si c'était vraiment facile, donc je ne suis pas sûr de l'avoir fait correctement. est

  a 
    /\ 
     b e3 
    /\ 
    e1 e2

état initial: 'a' est parent de 'b' (gauche) et 'e3' (à droite), 'b' est un parent de 'e1' (à gauche) et 'e2' (droite).

application rotation à droite nous donne:

  b 
    /\ 
    e1 a 
     /\ 
     e2 e3

'b' à la place de 'a' avec l'enfant 'e1' à gauche et 'un' enfant à droite, 'a' obtient 'e2' de 'b' sur la gauche.

Ainsi, les questions suivantes:

1. Si e1 est lui-même un sous-arbre ou d'un nœud contenant d'autres éléments, je peux faire encore cette rotation?
2. 2. Si e2 et e3 sont absents, puis-je effectuer cette rotation?

exemple 11; 12; 16

  16 
    /
    13 
/
10 

état intial: 16 est un parent de 13 et 13 est un parent de 10. puis-je faire de celle-ci: la figure 13 est un parent de 10 (à gauche) et 16 (droite)

Je sais que c'est simpliste, mais la théorie ne couvre souvent pas ces choses en supposant que c'est clair, et pas pour tout le monde. Merci pour votre aide,

Answer 1

Oui à tout, vraiment. Pensez à la propriété d'ordre: gauche descendants < noeud et noeud < droite descendants. Notez comment la rotation le conserve; comparez a et b à e1, e2 et e3 avant la rotation, et vérifiez l'ordre et les relations descendantes après la rotation. Je vais vous laisser réfléchir comment avant de le donner.