Per quanto riguarda albero splay

Question

Sto leggendo su albero splay in strutture dati e algoritmi di Mark Allen Wesis

La strategia divaricazione è simile all'idea di rotazione, se non che abbiamo sono un po 'più selettivi su come vengono eseguite le rotazioni. Noi ancora ruotare la parte inferiore lungo il percorso di accesso. Sia X una (non root) nodo sul percorso di accesso a cui siamo rotante. Se il genitore di x è la radice dell'albero, noi x semplicemente ruotare e la radice. Questo è il ultima rotazione lungo il percorso di accesso. In caso contrario, x ha sia un genitore (P) e un nonno (g), e ci sono due casi, più simmetrie, considerare. Il primo caso è il caso a zig-zag, Qui x è un diritto bambino e p è un figlio sinistro (o viceversa). Se questo è il caso, eseguire una doppia rotazione, esattamente come un doppia rotazione AVL. In caso contrario, abbiamo un caso a zig-zig: x e p sono entrambi sia a sinistra figli o entrambi i bambini a destra.

Nel testo sopra che cosa autore media dal seguente dichiarazione: "Ci sono due casi più simmetrie"? due casi sono date ma quali sono symmetires qui?

Grazie!

Answer 1

Credo che sia la simmetria assiale solo piuttosto semplice:

esempio per un caso zig zag, qui ci sono 2 alberi simmetrici:

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

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

Answer 2

Per esempio, diciamo che un caso è "Quando il nodo di domande è il figlio destro del suo genitore e il genitore è il figlio sinistro del nonno" In questo caso si fa una rotazione a sinistra e poi una rotazione a destra. Quindi il nodo arriverà fino al nonno.

La parte simmetrica di questo caso è "Quando il nodo di domande è il figlio sinistro del suo genitore e il genitore è il figlio destro del nonno" In questo caso si fa una rotazione a destra e poi una rotazione a sinistra. Quindi il nodo arriverà fino al nonno.

Sostituire sinistra con destra e da destra con sinistra si ottiene il caso simmetrico.

Ci sono solo 3 casi per la rotazione in un albero splay. Annunciato lo qui Si può vedere la differenza runtime nella ricerca con e senza divaricazione.