Färbe einen binären Baum so, dass er rot-schwarz ist

Eine häufig gestellte Interviewfrage besteht darin, einen Algorithmus anzugeben, mit dem festgestellt werden kann, ob ein gegebener Binärbaum eine ausgeglichene Höhe aufweist (AVL-Baumdefinition).

Ich habe mich gefragt, ob wir etwas Ähnliches mit rot-schwarzen Bäumen machen können.

Wenn ein beliebiger, ungefärbter Binärbaum (mit NULL-Knoten) gegeben ist, gibt es einen "schnellen" Algorithmus, der bestimmen kann, ob wir die Knoten rot / schwarz färben (und eine Färbung finden) können, so dass sie alle Eigenschaften eines Rot-Schwarz-Baums erfüllen (Definition wie in dieser Frage )?

Ein erster Gedanke war, dass wir einfach die NULL-Knoten entfernen und versuchen können, rekursiv zu überprüfen, ob der resultierende Baum ein rot-schwarzer Baum sein kann, aber das schien nirgendwo hin zu gehen.

Ich habe (kurz) im Internet nach Artikeln gesucht, konnte aber anscheinend keine finden, die sich mit diesem Problem befassen.

Es ist möglich, dass mir etwas Einfaches fehlt.

algorithms data-structures binary-trees search-trees Aryabhata
quelle

Ich bin mir ziemlich sicher, dass ein Baum eine rot-schwarze Farbe haben kann, wenn der längste Pfad von ihm zu einem NULL-Knoten nicht länger als zweimal so lang ist wie der kürzeste. Ist das schnell genug

Karolis Juodelė

Antworten:

Wenn für jeden Knoten eines Baumes der längste Weg von ihm zu einem Blattknoten nicht mehr als zweimal länger ist als der kürzeste, hat der Baum eine rot-schwarze Färbung.

Hier ist ein Algorithmus, um die Farbe eines Knotens zu bestimmen n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Hier n.black-quotaist die Anzahl der schwarzen Knoten , die Sie erwarten , gehen zu einem Blatt zu sehen, die von dem Knoten nund n.min-heightder Abstand zum nächsten Blatt.

Der Kürze halber sei , und . $b(n) =$ n.black-quota $h(n) =$ n.height $m(n) =$ n.min-height

$T$ $n \in T$ $h(n) \leq 2m(n)$ $r = \text{root}(T)$ $b(r) \in [\frac{1}{2}h(r), m(r)]$ $T$ $b(r)$

$b(n)$

$b(n) = 1$

$n$ $p$ $b(p) \in [\frac{1}{2}h(p), m(p)]$ $b(n) = b(p) -1$ $h(n) = h(p)-1$ $h(n) \geq m(n) \geq m(p)-1$

$r$ $b(r) < b(q)$

$b(n) = m(n)$ $n$

$b(p) = \frac{1}{2}h(p)$ $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$ $n$ $c$ $n$ $h(c) = h(p)-2$ $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$ $c$

$b(n) \in (\frac{1}{2}h(r), m(r))$ $n$ $n$ $n$

Karolis Juodelė
quelle

@Aryabhata, jede Überquerung ist in Ordnung, solange der Elternteil vor seinen Kindern gesehen wird. Ich habe keinen formellen Beweis geschrieben, aber ich habe eine Vorstellung davon, wie er aussehen würde. Ich werde versuchen, etwas aufzuschreiben, wenn ich kann.

Karolis Juodelė

@Aryabhata, ich habe einen Beweis hinzugefügt. Entschuldige, dass ich so lange gebraucht habe.

Karolis Juodelė

b (p)

$b(p)$

p

$p$

c

$c$

p

$p$

b (c)

$b(c)$

b (n)

$b(n)$

n

$n$

h

$h$

m

$m$

h

$h$

m

$m$

b (r o o t) = 8

$b(root) = 8$

b r b r b r \dots

$brbrbr\dots$

b b b b b b b b

$bbbbbbbb$

Es gibt eine Frage zu dieser Antwort .

David Richerby

$O(n)$

Ein Ansatz ist die Verwendung der dynamischen Programmierung.

$n$ $S_R(n)$ $S_B(n)$ $n$ $S_R(n)$ $n$ $S_B(n)$ $n$

$n.Left$ $n.Right$ $n$ $n$

$O(n \log n)$

Aryabhata
quelle