Vollständige und vollständige binäre Baum max und min Indizes?

Question

Ich bin mir nicht sicher, ob ich dies Grübeln, aber ich kann von der allgemeinen Fall Lösung nicht denken :(

Answer 1

Soweit wir speichern Knoten in höhere Werten im rechten Teilbaum und kleinere Werte linker Teilbaum für jeden Knoten, der Knoten bei Bottom Right Ecke wird den maximalen Wert und der Knoten bei Bottom Left Ecke wird den minimalen Wert haben.

So jetzt müssen Sie die Knoten zu finden.Es wird angegeben, dass der Baum ist Complete and Full BST und auch in Array gespeichert, so dass die Indizes gleichmäßig über den Knoten verteilt sind es. Hier müssen wir also Top to Bottom und Left to Right verschieben, um Knoten, beginnend mit 1 bis n, Index zuzuweisen, wenn n Knoten vorhanden sind.

Wenn wir also Indizes für bestimmten Baum schreiben,

      1 
         / \ 
         2  3 
        / \ / \ 
        4  5 6  7 
        /\   ^^^-------------Largest value 
        8 9 
Smallest value----^^^ 

Also hier ein Knoten mit 8 Index wird den kleinsten Wert und ein Knoten mit 7 Index mit dem größten Wert wird sein müssen.

So jetzt ist die Frage, wie man es findet. Überlegen Sie sich also, dass wir einen Baum mit dem Level l haben, dann wird der Index für den größten Wert 2^level - 1 sein und der kleinste Wert wird bei 2^level th Index sein. Aber der Index, den wir hier für den größten Wert erhalten, kann uns eine falsche Antwort geben, wenn total_nodes = 2^level-1. Also müssen wir level dafür auf eine andere Weise berechnen, indem wir total_nodes = n+1 betrachten.

int level = (int)(Math.ceil (Math.log(n)/Math.log(2))); //For index of smallest value; 
int smallest_index = (int) Math.pow (2,level); 

level = (int)(Math.ceil (Math.log(n+1)/Math.log(2))); //For index of largest value; 
int largest_index = (int) Math.pow (2,level) - 1; 

Answer 2

Sankets Antwort ist grundsätzlich richtig, aber die Art und Weise, wie es schließlich festgestellt wird, macht mich unbehaglich. Wer sagt, dass das abgerundete (!) Verhältnis von zwei gerundeten (!) Logs nicht auf nur etwas höher als die beabsichtigte ganze Zahl rundet? Und dann wird ceil es bis ganz nach oben tragen. Vielleicht funktioniert es, aber es wäre im Wesentlichen zufällig, nicht durch Design.

Es kann auch "sauber" angegeben werden, ohne dass man sich Gedanken über solche Dinge machen muss, im Sinne der bitweisen Arithmetik. Alles bleibt eine Ganzzahl, also ist es einfacher, darüber nachzudenken.

Der Index des untersten Elements ist bei der höchsten in 2 vorhandenen Leistung in n, also das höchste gesetzte Bit. In Java gibt es auch eine Funktion für das heißt: Integer.highestOneBit, oder wir könnten sie schreiben:

int highestOneBit(int x) { 
    x |= x >> 16; 
    x |= x >> 8; 
    x |= x >> 4; 
    x |= x >> 2; 
    x |= x >> 1; 
    return x^(x >>> 1); 
} 

Und wir haben jetzt

indexOfLowest = highestOneBit(n); 
indexOfHighest = highestOneBit(n + 1) - 1; 

Dies setzt voraus, noch 1 basierte Indizes (wobei der Index 0 nicht verwendet), Sie können einfach alles um 1 versetzen, um es 0-indexiert zu machen.