Di mana istilah "Pohon Merah / Hitam" berasal?

A Red / Black Tree adalah salah satu cara untuk menerapkan pohon pencarian biner seimbang. Prinsip di balik cara kerjanya masuk akal bagi saya, tetapi warna yang dipilih tidak. Mengapa merah dan hitam, berbeda dengan pasangan warna atau atribut lainnya secara umum? Ketika saya mendengar "merah dan hitam," hal-hal pertama yang muncul di benak saya adalah papan catur dan Les Misérables, yang keduanya tampaknya tidak dapat diterapkan dalam konteks ini.

data-structures history Mason Wheeler
sumber

WAG: Pena BIC sering dijual dalam kemasan yang berisi campuran biru, hitam, dan merah (saya lupa dalam proporsi berapa). Menggunakan biru dan hitam pada diagram yang sama pada selembar kertas mungkin membuatnya sulit dibaca sehingga jika diagrammer lebih suka hitam daripada merah, mereka mungkin akan menukar pena biru dengan merah. Atau setidaknya begitulah jadinya kalau aku ... Aku tidak tahu alasan sebenarnya , tapi berspekulasi pasti menyenangkan! Mungkin kita bahkan bisa memulai legenda urban dengan cara ini!

FrustratedWithFormsDesigner

Saya memiliki seorang profesor ilmu komputer yang mengklaim bahwa warna dipilih untuk mewakili konvensi warna kawat khas untuk anoda (merah, +) dan katoda (hitam, -)

holtavolt

@FrustratedWithFormsDesigner Apa arti WAG ?

Maks.

@ Maxm: tebakan liar. Secara pribadi saya pikir itu terinspirasi roulette.

Wyatt Barnett

@FrustratedWithFormsDesigner - Tebakan bagus, ternyata benar-benar bergantung pada uang.

ocodo

Jawaban:

EDIT : Jawaban dari Profesor Guibas:

dari Leonidas Guibas [email protected] hingga istilah "Merah-Hitam" dikirimkan oleh cs.stanford.edu sembunyikan detail 16:16 (0 menit lalu)

kami memiliki pena merah dan hitam untuk menggambar pohon.

Saya percaya istilah ini pertama kali muncul dalam "Kerangka dikromatik untuk pohon seimbang" dari Leonidas J. Guibas dan Robert Sedgewick pada tahun 1978.

Dan McGrath
sumber

Saya baru saja mengirim email kepada Profesor Guibas. Mari kita lihat apakah kita bisa mendapatkan respons yang pasti.

Dan McGrath

Saya ingin tahu apakah ada salinan pohon asli yang masih ada ... :)

porges

Beginilah seharusnya situs ini bekerja, bravo.

David Cowden

Ini tidak sesuai dengan pernyataan oleh co-inventor dari RB-Trees. Seseorang lebih baik jelaskan ini :). Lihat jawaban saya.

Shital Shah

Dalam Coursera, Red-Black BSTs (2012) , Robert Sedgewick mengatakan ini:

Banyak orang bertanya mengapa kami menggunakan nama merah-hitam. Kami menemukan struktur data ini, cara memandang pohon seimbang, di Xerox PARC yang merupakan rumah dari komputer pribadi dan banyak inovasi lain yang kami jalani saat ini dengan memasukkan antarmuka pengguna grafis, ethernet, dan program berorientasi objek [sic] dan banyak hal lainnya. Tetapi salah satu hal yang ditemukan ada pencetakan laser dan kami sangat senang memiliki printer laser warna terdekat yang dapat mencetak hal-hal dalam warna dan keluar dari warna merah tampak yang terbaik. Jadi, itulah mengapa kami memilih warna merah untuk membedakan tautan merah, jenis tautan, dalam tiga simpul. Jadi, itulah jawaban untuk pertanyaan bagi orang yang telah bertanya.

Shital Shah
sumber

Bahkan di PARC, saya tidak dapat menemukan referensi untuk pencetakan Laser warna pada tahun 1978 (ketika referensi pertama untuk pohon Merah-Hitam ada). Misalnya, iklan komersial pertama HP adalah tahun 1994 dan saya tidak dapat menemukan referensi untuk printer laser warna di tahun 80-an?

Dan McGrath