2015-02-23 9 views
5

Stavo leggendo sulla struttura dei dati della corda su wikipedia ed ero un po 'confuso riguardo la descrizione.Spiegazione struttura dati in corda?

collegamento Wiki: http://en.wikipedia.org/wiki/Rope_(data_structure)

Descrizione

Una corda è un albero binario avendo nodi foglia che contengono una breve stringa.

Ogni nodo ha un valore di peso uguale alla lunghezza della sua stringa più la somma del peso di tutti i nodi foglia nel suo sottoalbero sinistro, vale a dire il peso di un nodo è la lunghezza totale della stringa nel suo sottoalbero sinistro per un non- nodo foglia o la lunghezza della stringa stessa per un nodo foglia.

Quindi un nodo con due figli divide l'intera stringa in due parti: la sottostruttura di sinistra memorizza la prima parte della stringa. Il sottoalbero destro memorizza la seconda parte e il suo peso è la somma del peso del bambino sinistro e della lunghezza della sua stringa contenuta.

L'immagine qui sotto è uno degli esempi di wikipedia.

Rope data structure tree .

Ho difficoltà a vedere da dove provengono i numeri nell'immagine in alto.

Ogni nodo ha un valore di peso pari alla lunghezza della sua corda più la somma di peso tutti i nodi foglia del suo sottoalbero sinistro

  • C = 6 + 0 (E + C del vuoto lunghezza della stringa)?
  • B = 6 + 3 + 0 + 0 (lunghezza stringa vuota E + F + C + lunghezza stringa B vuota)?
  • Questo non può essere corretto, perché A 22? (6 + 6 + 9 = 21? 6 + 6 + 3 + 9 = 24?)

Sono quasi sicuro di aver perso qualcosa. Qualcuno può aiutarmi a chiarirlo?

Grazie.

risposta

5

Ogni nodo ha un valore di peso pari alla lunghezza della sua corda più la somma di tutti i nodi foglia peso del suo sottoalbero sinistro ...

A non ha sottoalbero destro quindi il suo valore è la somma dei pesi di tutti i nodi foglia (anche se A aveva un sottoalbero destro il suo valore sarebbe lo stesso): 6 + 3 + 2 + 4 + 1 + 6 = 22

B ha due foglie nella sua sottostruttura di sinistra: 6 + 3 = 9

C ha una foglia nel suo sottoalbero sinistro: 6