BST con duplicati

Question

So che, BST non consente duplicati. Ad esempio, se ho una parola "RABSAB".

L'albero binario di ricerca per la stringa sopra è:

R 
    /\ 
    A S 
    \ 
    B 

E se volessimo includere i duplicati nella struttura. Come cambierà l'albero? Mi è stata fatta questa domanda in un'intervista.

Mi hanno chiesto di disegnare:

1. un albero binario
2. un Binary Search Albero
3. un albero binario di ricerca sbilanciato senza duplicati
4. un albero binario di ricerca con i duplicati

Qualsiasi aiuto è apprezzato!

PS: Aiutami disegnando i relativi alberi

Answer 1

regola da inserire in un albero binario di ricerca senza duplicato è:

1. andare a sinistra se l'elemento è inferiore a radice
2. Vai a destra se l'elemento è maggiore di root.

E per consentire le voci duplicate è necessario modificare la regola come muggito:

1. andare a sinistra se l'elemento è inferiore o uguale radice
2. Vai a destra se l'elemento è maggiore di root.

o

1. Vai a sinistra se l'elemento è inferiore radice
2. Go destra se l'elemento è maggiore o uguale radice.

o

1. Vai a sinistra se l'elemento è inferiore radice
2. Go destra se l'elemento è maggiore di radice.
3. Aumentare il conteggio se l'elemento è uguale alla radice.

Così il vostro BST per parola "RABSAB", con i duplicati possono essere come:

 R 
    /\ 
    A S 
/\ 
A B 
    /
    B 

Oppure,

 R 
    /\ 
    A S 
    \ 
    A 
     \ 
     B 
     \ 
     B 

o

R(1) 
/\ 
/ \ 
A(2) S(1) 
    \ 
    \ 
    B(2) 

In primo luogo due casi, entrambi l'inserimento e la ricerca diventano un po 'complessi! Lo troverai here con una grande quantità di spiegazioni!

E il terzo caso è un po 'più facile da mantenere.

Tutti sono utilizzati con successo per consentire duplicati, ora la scelta è vostra!

Answer 2

Una possibilità è quella di modificare l'albero in modo che un ramo comprenderà i duplicati, ad esempio, hanno i rami di sinistra sostengono i nodi che sono inferiori o uguali al genitore , in alternativa avere i rami giusti tengono nodi che sono maggiori o uguali al genitore

Un'altra opzione è quella di memorizzare tutti i duplicati in un nodo, quindi invece di

class Node { 
    Node left, right; 
    Object data; 
} 

si avrebbe invece hanno

class Node { 
    Node left, right; 
    List data; 
} 

o

class Node { 
    Node left, right; 
    Object data; 
    int count; 
} 

Answer 3

In un inserimento BST normale e verificare verificarsi entrambi basati su meno di (>) e maggiore di (<) regola.

Si potrebbe invece provare l'inserimento su meno di uguale a (> =) o maggiore di uguale a (< =) e provare a utilizzare la stessa regola per la ricerca.

In alternativa è possibile includere una matrice in ogni nodo per contenere elementi duplicati.

Answer 4

Per l'input RABPAB, è possibile creare un BST utilizzando un ELENCO per memorizzare tutte le chiavi con valore uguale. Tutte le chiavi di uguale valore sono collocate nello stesso livello utilizzando una struttura dati in grado di memorizzarlo.

La BST sarà simile a questo,

 R 
    /\ 
A--A P 
    \ 
    B--B 

Il codice Java per la BST memorizzare valori interi potrebbe essere come questo,

class Node 
{ 
    Node left, right; 
    int data[maxvalue]; 
} 

Qui maxvalue è possibili chiavi massimo pari valore.