Eigenschaften eines rot-schwarzen Baum

Question

 35 (black) 
    / \ 
    21  54 (whole row is red) 
/\ /\ 
14 27 42 74 (whole row is black) 
       \ 
       90 (red) 

Würde dies klassifizieren als rot-schwarz Baum, ich habe keine Verletzungen nicht gesichtet. Was sind in erster Linie die Eigenschaften, nach denen ich Ausschau halten sollte, außer dass Sie nicht zwei aufeinanderfolgende rote Knoten haben können?

Answer 1

Es gibt keine Verletzungen in der obigen Baumstruktur.

Die wichtigsten Eigenschaften, wo sie nach sind:

1) Root Schwarz ist

2) Es gibt nicht zwei aufeinanderfolgenden roten Knoten sein kann.

3) Sie müssen NIL-Knoten als Blattknoten hinzufügen, deren Farbe schwarz ist.

4) Die Black Depth aller Knoten von der Wurzel ist immer die gleiche, zB im obigen Fall die einschließlich der NIL-Knoten auf jedem Pfad.

Sie können über sie hier lesen: Red Black Tree Properties