Warnai pohon biner menjadi pohon merah-hitam

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.

algorithms data-structures binary-trees search-trees 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:

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 , dan . $b(n) =$ n.black-quota $h(n) =$ n.height $m(n) =$ n.min-height

Teorema: Perbaiki pohon biner . Jika untuk setiap simpul , dan untuk simpul , $T$ $n \in T$ $h(n) \leq 2m(n)$ $r = \text{root}(T)$ lalu $b(r) \in [\frac{1}{2}h(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 induk hitam sehingga $n$ $p$ . Kemudian,dan. $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$

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

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

Jika lalu $b(p) = \frac{1}{2}h(p)$ . tidak memenuhi asumsi induktif dan karenanya harus merah. Biarkanmenjadi anak dari. dan $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$ $n$ $c$ $n$ $h(c) = h(p)-2$ . Maka dapat diwarnai merah-hitam dengan asumsi induktif. $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$ $c$

Perhatikan bahwa, dengan alasan yang sama, jika , makadan anakmemenuhi asumsi induktif. Karenanyadapat memiliki warna apa pun. $b(n) \in (\frac{1}{2}h(r), m(r))$ $n$ $n$ $n$

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

sedang dalam batasan tertentu, seorang anak atau cucu

dari

dapat memiliki

dalam batas yang sama. Memiliki

dalam batas tersebut dapat sesuai dengan

menjadi hitam. Sebagian besar buktinya adalah tentang mengikat

dan

anak atau cucu, mengingat

dan

dari orang tua atau kakek nenek. Pohon Anda tentu saja berwarna.

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$ , anak kiri berwarna hitam dan anak kanan berwarna merah, jalur panjang 16 adalah

, jalur panjang 8 adalah

, jalur 9 dan 12 dapat memiliki beberapa warna yang valid.

b r b r b r \dots

$brbrbr\dots$

b b b b b b b b

$bbbbbbbb$

Karolis Juodelė

Ada pertanyaan tentang jawaban ini .

David Richerby

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

Salah satu pendekatan adalah menggunakan pemrograman dinamis.

Diberikan pohon, untuk setiap node , Anda membangun dua set: dan yang berisi kemungkinan ketinggian-hitam untuk subtree yang berakar pada . berisi ketinggian-hitam dengan asumsi berwarna Merah, dan dengan asumsi berwarna hitam. $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
sumber