Rot-schwarzer Baum Zugang nach Ordinal Index

Question

Ich habe einen rot-schwarzen Baum (binary Baum, alle Blätter sind innerhalb von 2 Ebenen). Ich kann durch Knoten navigieren: nach links, rechts oder übergeordnet. Ich kenne die gesamte Anzahl der Knoten.

Ich muss das N-te kleinste Element in einem Baum finden. Gibt es eine Möglichkeit, dies schneller als in O (n) zu tun? Irgendwelche Ideen zur Optimierung des Zugriffs nach Index?

Answer 1

In jedem Knoten X sollten Sie speichern, wie viele Knoten in Teilbaum mit X als Root sind.

count(LEAF) = 1 
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1 

Während jedes Einfügen/Löschens sollten Sie diese Gleichung verwenden, um die Anzahl der Knoten in Knoten zu aktualisieren, die von Rotationen betroffen sind.

Nach dieser Lösung

NODE nth(NODE root, int n) { 
    if (root->left->count <= n) return nth(root->left, n); 
    if (root->left->count + 1 == n) return root; 
    return nth(root->right, n - root->left->count - 1); 
} 

Answer 2

Sie können in jedem Knoten ein Attribut hinzufügen, das die Anzahl der Children dieses Knotens anzeigt. Mit diesem Attribut können Sie den kleinsten N-ten Knoten mit O (lgn) finden.

Jetzt müssen Sie nur mit diesem Attribut umgehen, wenn Sie einen Knoten in den Baum einfügen (oder löschen). Wenn es keine Rotation gibt, dann ist es einfach zu handhaben, aber wenn Sie Rotation haben, ist es ein wenig schwierig, aber Sie können es tun.

Answer 3

Für rot Sie die Anzahl der Knoten auf der linken Seite, weil zu verfolgen nicht schwarz Baum einfach brauchen, wenn es richtig vorbelastet ist die Anzahl der linken Knoten (sollte), dann wird immer bilden eine Mersenne-Serie (1, 3, 7, 15, 31 ...) oder 2^depth -1.

In diesem Sinne können wir die Logik aufschreiben, um den Knoten rekursiv zu bekommen. Die angenommene Antwort oben hat ihr Vorzeichen geschaltet. Dies ist die korrekte Implementierung in Elixier. Für package

def nth(%Rbtree{node: r}, n), do: do_nth(r, n) 
defp do_nth({_,h,k,v,l,r}, n) do 
    l_count = left_count(h) 
    cond do 
    l_count > n -> 
     case l do 
     nil -> {k,v} 
     _ -> do_nth(l, n) 
     end 
    l_count == n -> {k,v} 
    true -> 
     case r do 
     nil -> {k,v} 
     _ -> do_nth(r, n - l_count - 1) 
     end 
    end 
end 
defp left_count(1), do: 0 
defp left_count(0), do: 0 
defp left_count(h), do: :math.pow(2,h-1)-1 |> round