Trova il primo null nell'albero binario con memoria limitata

Question

Ho un albero binario in cui ogni nodo può avere un valore.

Voglio trovare il nodo nella struttura che ha valore null ed è il più vicino alla radice. Se ci sono due nodi con la stessa distanza dalla radice, lo faranno entrambi. Devo ridurre al minimo il numero di accessi in lettura all'albero binario. Supponiamo che la memoria di lavoro sia limitata a soli nodi k.

DFS a profondità k è esaustivo ma non troverà il nodo più vicino a meno che non attraversi prima l'intero albero. BFS troverà il più vicino, ma potrebbe non funzionare perché DFS può trovare valori nulli più profondi con la stessa memoria.

Vorrei avere il minor numero di accessi in lettura all'albero e trovare il nodo null più vicino.

(Alla fine dovrò implementarlo anche negli alberi n-way, quindi una soluzione generale sarebbe buona. Nessun accesso in scrittura all'albero, basta leggere.)

Answer 1

Potresti dare un'occhiata a prima ricerca approfondita iterativa . Troverà automaticamente il nodo più vicino ma sarà in grado di raggiungere la stessa profondità di DFS. Tuttavia, utilizzerà più accessi in lettura.

Puoi anche iniziare con BFS e, se non trovi un valore nullo con la memoria consentita, esegui DFS.

Answer 2

Vorrei implementare un DFS con una semplice potatura ad albero. Pertanto, non è vero che devi eseguire l'intero albero.

Ad esempio, se hai individuato un valore null all'altezza h, puoi saltare nodi che si trovano nello stesso o posizione più profonda.

Answer 3

Se non riesci a modificare la struttura dei dati, dovrai leggere ogni nodo, prima di tutto.

Se è possibile modificare la struttura dei dati, ciascun nodo potrebbe registrare la profondità relativa del primo nodo figlio nullo. (Ciascuno per allenarsi dai valori equivalenti dei propri figli).

Quindi sai quale linea dell'albero inseguire quando cerchi il primo null.

Answer 4

C'è un modo semplice, se sei disposto a memorizzare il tuo albero in un array. Piuttosto che ogni nodo che ha puntatori ai suoi figli sinistro e destro, i figli del nodo n sono 2n + 1 e 2n + 2 nell'array. (E il genitore del nodo n è (n-1) / 2, se n! = 0.)

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

La semplice iterazione lineare dell'array equivale a un BFS, ma con requisiti di spazio di O (1).

Questo può essere facilmente esteso ad alberi n-ary. ad esempio, in un albero ternario, il figlio sinistro è 3n + 1, il centro è 3n + 2, il diritto è 3n + 3 e il genitore è (n-1) / 3 se n! = 0.