Newsgroup: it.lavoro.informatica
Titolo: Aiuto!

Da 2 giorni sto impazzendo per scrivere una c...o di funzione per
l'eliminazione di un nodo da un albero  binario bilanciato e pesato per
ramo che feci tanto tempo fa. Lo so che e` un cavolatata complesse ma non
cagnatemi: sono solo stanco di ragionare sugli stessi problemi. Per favore
mi potreste indicare una fonte di codice Java da cui attingere una
funzione pulita pulita (senza troppi ghirigori, eredita` ecc.ecc.) che
faccia una cosa del genere?
Grazie molte!

, 
filo....@catamail.it
 
says...

Facci vedere cosa hai fatto, e vediamo cosa manca. Altrimenti sembra che cerchi 
qualcuno che ti faccia i compiti..... :P 
-- 
__________________________
Luc (32, CO)
MS Visual Studio developer
__________________________

 qualcuno che ti faccia i compiti..... :P
Purtroppo l'ogetto e` assai lungo per poterlo postare ma se volete ve
lo posso mandare via e-mail (e` parecchio interessante, ha funzioni
veramente utili, e` svincolato da eredita`, richiede l'import del solo
Vector (che fra, l'altro non viene utilizzato ma sono ritornato da una
funzione interna). Comunque, anche se forse non si capira` al volo, vi
riporto la funzione cosi` come e` stata scritta e che, aime`, non e`
ricorsiva per motivi di prestazioni.
L'oggetto si chiama SimpleNode ed e` un nodo che autocostruisce un albero
binario autolimitante bilanciato ecc.ecc.ecc. sotto di se appendendo altri
SimpleNode con prestazioni da paura.
	/**
	 * La funzione opera la rimozione del nodo il cui indice e' specificato come argomento. Se il nodo viene effettivamente eliminato ritorna true altrimenti (il nodo non esiste) ritorna false;
	 * 
	 * @param index
	 *            indice del nodo da eliminare.
	 * @return true se il nodo esiste, false se il nodo non esiste.
	 */
	public boolean remove(long index) {
		// Ora cerco la replacing del ramo piu` lungo.
		SimpleNode trans = get(index), replacing, trans1;
		if(trans == null) return false;
 
		if(trans.leftchild==null && trans.rightchild==null) {
			if(trans == trans.phather.rightchild) {
				trans.phather.rightchild=null;
			}
			else trans.phather.leftchild=null;
			return true; //Il nodo e` stato correttamente rimosso.
		}
		// Ora cerco la replacing adeguata del ramo piu` lungo sottostante a quello da sostituire in questo modo si contribuisce, anche se poco, a mantenere bilanciato l'albero.
		replacing = trans;
		if(replacing.rightElNumber >= replacing.leftElNumber && replacing.rightchild != null) {
			replacing = replacing.rightchild;
			while(replacing.leftchild != null) {
				replacing = replacing.leftchild;
			}
		}
		else if(replacing.leftchild != null) {
			replacing = replacing.leftchild;
			while(replacing.rightchild != null) {
				replacing = replacing.rightchild;
			}
		}
 
		/*Ora le operazioni da fare in sequenza dovranno essere le seguenti:
		 * -se il replacing non ha figli si svincola semplicemente dall'albero.
		 * -se il replacing ha un figlio, unico per definizione, questo va inserito al posto del replacing che rimane cosi` svincolato
		 * -si aggiornano i pesi al di sopra del replacing (decremento unitario).
		 * -si sostituisce il replaced con il replacing ereditando anche i pesi.
		 * -TUTTO OK
		 */
		//Rimozione replacing dall'albero
		if(replacing.rightchild == null && replacing.leftchild == null) {//replacing senza figli
			// Caso in cui la replacing sia un nodo "destro".
			if(replacing == replacing.phather.rightchild) {
				replacing.phather.rightchild = null;
			}
			// Caso in cui la replacing sia un nodo "sinistro".
			else {
				replacing.phather.leftchild = null;
			}
		}
		else if(replacing.rightchild!=null){//Caso in cui il replacing abbia un figlio a destra.
			//A questo punto il replacing puo` essere solo un figlio sinistro.
			replacing.phather.leftchild = replacing.rightchild;
		}
		else {
			//A questo punto il replacing puo` essere solo un figlio destro.
			replacing.phather.rightchild = replacing.leftchild;
		}
 
		// Correzione elnumber dei nodi sovrastanti il nodo replacing.
		trans1 = replacing;
		while(!trans1.isRootNode) {
			if(trans1 == trans1.phather.rightchild) {
				trans1.phather.rightElNumber--;
				// if(trans.phather.rightElNumber < 0) System.err.println("SimpleNode: qualcosa non va nellaggiornamento degli elNumber nella funzione remove().");
			}
			else {
				trans1.phather.leftElNumber--;
				// if(trans.phather.leftElNumber < 0) System.err.println("SimpleNode: qualcosa non va nellaggiornamento degli elNumber nella funzione remove().");
			}
			trans1 = trans1.phather;
		}
		replaceNode(trans, replacing);
		trans = null;
		replacing = null;
		return true;
	}

 SimpleNode con prestazioni da paura.
E' praticamente un albero binario di ricerca bilanciato con funzione di inserimento di sottoalberi 
dello stesso tipo?
Per l'eliminazione basta cercare in rete qualsiasi tipo di codice d'esempio per l'eliminazione di un 
nodo da quel tipo di struttura, per la ricorsione non vedo il problema, basta che ogni nodo 
dell'albero sia del tipo SimpleNode e tutto viene automatico, prevedendo la cosa nei metodi ovviamente.
Feci una cosa ricorsiva simile in un linguaggio funzionale come esercizio durante un corso al primo 
anno, se trovo il codice te lo posto può essere una buona traccia.
Ciao.

 phather
Posso chiederti perché scrivi "father" in questo modo?!?
Massimo

 l'eliminazione di un nodo da un albero  binario bilanciato e pesato per
...
Parzialmente off topic:
usa C++
poi fai
#include <map>
std::map< QualsiasiTipo, QualsiasiAltroTipo > M;
Meno off topic di prima:
Prendi "Algoritmi in C" di Sedgewick
ciao
-- 
Leo
"So, putting it simply, STL is the result of a bacterial infection." (A. 
Stepanov)