Warnai pohon biner menjadi pohon merah-hitam

16

Pertanyaan wawancara yang umum adalah untuk memberikan algoritma untuk menentukan apakah pohon biner yang diberikan seimbang tinggi (definisi pohon AVL).

Saya bertanya-tanya apakah kita bisa melakukan sesuatu yang mirip dengan pohon Merah-Hitam.

Diberikan pohon biner tanpa warna yang sewenang-wenang (dengan simpul NULL), apakah ada algoritma "cepat" yang dapat menentukan apakah kita dapat mewarnai (dan menemukan pewarnaan) simpul Merah / Hitam sehingga mereka memenuhi semua sifat-sifat pohon Merah-Hitam (definisi seperti dalam pertanyaan ini )?

Pikiran awal adalah bahwa kita bisa menghapus node NULL dan mencoba untuk memverifikasi secara rekursif jika pohon yang dihasilkan bisa menjadi pohon merah-hitam, tetapi itu tampaknya tidak pergi ke mana pun.

Saya melakukan (singkat) pencarian web untuk makalah, tetapi tampaknya tidak dapat menemukan yang tampaknya berurusan dengan masalah ini.

Mungkin saja saya kehilangan sesuatu yang sederhana.

Aryabhata
sumber
Saya cukup yakin pohon bisa berwarna merah-hitam jika untuk setiap node, jalur terpanjang dari itu ke simpul NULL tidak lebih dari dua kali lebih lama dari yang terpendek. Apakah itu cukup cepat?
Karolis Juodelė

Jawaban:

12

Jika untuk setiap simpul pohon, jalur terpanjang dari itu ke simpul daun tidak lebih dari dua kali lebih lama dari yang terpendek, pohon memiliki pewarnaan merah-hitam.

Berikut ini adalah algoritma untuk mengetahui warna dari simpul apa pun 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

Berikut n.black-quotaadalah jumlah simpul hitam yang Anda harapkan untuk melihat pergi ke daun, dari simpul ndan n.min-heightjarak ke daun terdekat.

Untuk singkatnya notasi, misalkan , h ( n ) = dan m ( n ) = .b(n)= n.black-quotah(n)= n.heightm(n)= n.min-height

Teorema: Perbaiki pohon biner . Jika untuk setiap simpul n T , h ( n ) 2 m ( n ) dan untuk simpul r = root ( T ) , b (TnTh(n)2m(n)r=root(T)laluTb(r)[12h(r),m(r)]T memiliki pewarnaan merah-hitam dengan tepat simpul hitam di setiap jalur dari akar ke daun.b(r)

Bukti: Induksi lebih dari .b(n)

Verifikasi bahwa keempat pohon dengan tinggi satu atau dua memenuhi teorema dengan .b(n)=1

Menurut definisi pohon merah-hitam, root adalah hitam. Biarkan menjadi simpul dengan p induk hitam sehingga b (np. Kemudianb(n)=b(p)-1,h(n)=h(p)-1danh(n)m(n)m(p)-1.b(p)[12h(p),m(p)]b(n)=b(p)1h(n)=h(p)1h(n)m(n)m(p)1

Asumsikan teorema berlaku untuk semua pohon dengan root , b ( r ) < b ( q ) .rb(r)<b(q)

Jika , maka n dapat berwarna merah-hitam dengan asumsi induktif.b(n)=m(n)n

Jika lalub(n)=1b(p)=12h(p). ntidak memenuhi asumsi induktif dan karenanya harus merah. Biarkancmenjadi anak darin. h(c)=h(p)-2dan b(c)=b(p)-1=1b(n)=12h(n)1ncnh(c)=h(p)2 . Maka c dapat diwarnai merah-hitam dengan asumsi induktif.b(c)=b(p)1=12h(p)1=12h(c)c

Perhatikan bahwa, dengan alasan yang sama, jika , makandan anaknmemenuhi asumsi induktif. Karenanyandapat memiliki warna apa pun.b(n)(12h(r),m(r))nnn

Karolis Juodelė
sumber
@Aryabhata, semua traversal baik-baik saja, selama orang tua terlihat di depan anak-anaknya. Saya tidak punya bukti formal tertulis, tetapi saya punya ide bagaimana tampilannya. Saya akan mencoba menulis sesuatu ketika saya bisa.
Karolis Juodelė
@Aryabhata, saya menambahkan bukti. Maaf saya butuh waktu lama.
Karolis Juodelė
@Aryabhata, idenya adalah bahwa jika dari beberapa simpul p sedang dalam batasan tertentu, seorang anak atau cucu c dari p dapat memiliki b ( c ) dalam batas yang sama. Memiliki b ( n ) dalam batas tersebut dapat sesuai dengan n menjadi hitam. Sebagian besar buktinya adalah tentang mengikat h dan m anak atau cucu, mengingat h dan m dari orang tua atau kakek nenek. Pohon Anda tentu saja berwarna. b ( r o o tb(p)pcpb(c)b(n)nhmhmb(root)=8 , anak kiri berwarna hitam dan anak kanan berwarna merah, jalur panjang 16 adalah , jalur panjang 8 adalah b b b b b b b b b , jalur 9 dan 12 dapat memiliki beberapa warna yang valid. brbrbrbbbbbbbb
Karolis Juodelė
Ada pertanyaan tentang jawaban ini .
David Richerby
2

Saya percaya jawaban Karolis benar (dan karakterisasi pohon merah-hitam yang cukup bagus, memberikan algoritma waktu n ) ), hanya ingin menambahkan kemungkinan jawaban lain.O(n)

Salah satu pendekatan adalah menggunakan pemrograman dinamis.

Diberikan pohon, untuk setiap node , Anda membangun dua set: S R ( n ) dan S B ( n ) yang berisi kemungkinan ketinggian-hitam untuk subtree yang berakar pada n . S R ( n ) berisi ketinggian-hitam dengan asumsi n berwarna Merah, dan S B ( n ) dengan asumsi n berwarna hitam.nSR(n)SB(n)nSR(n)nSB(n)n

n.Leftn.Rightnn

O(nlogn)

Aryabhata
sumber