Skąd pochodzi termin „czerwone / czarne drzewo”?

Red / Black Drzewo jest jednym ze sposobów wdrożenia zrównoważonej binarne drzewo poszukiwań. Zasady, jak to działa, mają dla mnie sens, ale wybrane kolory nie. Dlaczego czerwony i czarny, w przeciwieństwie do jakiejkolwiek innej pary kolorów lub ogólnie atrybutów? Kiedy słyszę „czerwony i czarny”, pierwsze rzeczy, które przychodzą mi do głowy, to szachownice i Les Misérables, z których żadna nie wydaje się szczególnie odpowiednia w tym kontekście.

data-structures history

— Mason Wheeler
źródło

WAG: długopisy BIC są często sprzedawane w opakowaniach zawierających mieszankę niebieskiego, czarnego i czerwonego (zapominam w jakich proporcjach). Używanie niebieskiego i czarnego na tym samym schemacie na kartce papieru może utrudnić czytanie, więc jeśli diagrammer woli kolor czarny od czerwonego, prawdopodobnie zamieniłby niebieski długopis na czerwony. A przynajmniej tak by było, gdybym to był ja ... Nie mam pojęcia o żadnym prawdziwym celu , ale spekulowanie na pewno jest zabawne! Może w ten sposób możemy stworzyć legendę miejską!

— FrustratedWithFormsDesigner

Miałem profesora informatyki, który twierdził, że kolory zostały wybrane tak, aby reprezentowały typowe konwencje kolorów drutu dla anody (czerwony, +) i katody (czarny, -)

— holtavolt

@FrustratedWithFormsDesigner Co oznacza WAG ?

— Maks.

@Maxpm: dzikie zgadywanie. Osobiście uważam, że była inspirowana ruletką.

— Wyatt Barnett

@FrustratedWithFormsDesigner - Zgaduję, że okazało się, że całkowicie zarabia.

— ocodo

Odpowiedzi:

EDYCJA : Odpowiedź profesora Guibasa:

od Leonidas Guibas guibas@cs.stanford.edu do terminu „Czerwono-czarny” przesłany przez cs.stanford.edu ukryj szczegóły 16:16 (0 minut temu)

mieliśmy czerwone i czarne długopisy do rysowania drzew.

Sądzę, że termin ten pojawił się po raz pierwszy w „Dichromatycznej ramie dla zrównoważonych drzew” Leonidasa J. Guibasa i Roberta Sedgewicka w 1978 roku.

— Dan McGrath
źródło

Właśnie wysłałem e-mail do profesora Guibasa. Zobaczmy, czy możemy uzyskać ostateczną odpowiedź.

— Dan McGrath,

Zastanawiam się, czy istnieją jakieś zachowane kopie oryginalnych drzew ... :)

— odsłania

Właśnie tak powinna działać ta strona, brawo.

— David Cowden,

Nie zgadza się to z oświadczeniem współtwórcy RB-Trees. Niech ktoś to wyjaśni :). Zobacz moją odpowiedź.

— Shital Shah

W Coursera, czerwono-czarne BST (2012) , Robert Sedgewick mówi:

Wiele osób pyta, dlaczego używamy nazwy czerwono-czarna. Cóż, wymyśliliśmy tę strukturę danych, ten sposób patrzenia na zrównoważone drzewa, na Xerox PARC, który był domem komputera osobistego i wiele innych innowacji, z którymi obecnie żyjemy, wprowadzając [sic] graficzne interfejsy użytkownika, Ethernet i programowanie obiektowe [sic] i wiele innych rzeczy. Ale jedną z rzeczy, które tam wymyślono, było drukowanie laserowe i byliśmy bardzo podekscytowani, że mamy w pobliżu kolorową drukarkę laserową, która może drukować rzeczy w kolorze i poza kolorami, które wyglądały najlepiej. Dlatego wybraliśmy kolor czerwony, aby rozróżnić czerwone linki, typy łączy, w trzech węzłach. To odpowiedź na pytanie zadawane przez ludzi.

— Shital Shah
źródło

Nawet w PARC nie mogę znaleźć żadnego odniesienia do kolorowego druku laserowego w 1978 roku (kiedy istnieją pierwsze odniesienia do drzew czerwono-czarnych). Na przykład pierwszy komercyjny HP był w 1994 roku i nie mogę znaleźć żadnych odniesień do kolorowych drukarek laserowych w latach 80-tych?

— Dan McGrath,