Tidak semua pohon Merah-Hitam seimbang?

Secara intuitif, "pohon seimbang" harus pohon di mana sub-pohon kiri dan kanan di setiap node harus memiliki "kurang lebih sama" jumlah node.

Tentu saja, ketika kita berbicara tentang pohon merah-hitam * (lihat definisi di akhir) yang seimbang, kita benar-benar berarti bahwa mereka adalah tinggi badan seimbang dan dalam arti bahwa, mereka seimbang.

Misalkan kita mencoba memformalkan intuisi di atas sebagai berikut:

Definisi: Pohon Biner disebut -balanced, dengan , jika untuk setiap simpul , ketidaksamaan $\mu$ $0 \le \mu \leq \frac{1}{2}$ $N$

$μ \leq \frac{| N_{L} | + 1}{| N | + 1} \leq 1 - μ$ $\mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$
memegang dan untuk setiap , ada beberapa simpul yang gagal pernyataan di atas. adalah jumlah node di sub-pohon kiri danadalah jumlah node di bawah pohon dengan sebagai root (termasuk root). $\mu' \gt \mu$ $|N_L|$ $N$ $|N|$ $N$

Saya percaya, ini disebut pohon dengan bobot seimbang dalam beberapa literatur tentang topik ini.

Satu dapat menunjukkan bahwa jika pohon biner dengan node adalah -balanced (untuk konstanta ), maka ketinggian pohon adalah , sehingga mempertahankan pencarian yang bagus properti. $n$ $\mu$ $\mu \gt 0$ $\mathcal{O}(\log n)$

Jadi pertanyaannya adalah:

Apakah ada beberapa sedemikian rupa sehingga setiap pohon merah-hitam yang cukup besar adalah seimbang? $\mu \gt 0$ $\mu$

Definisi pohon Merah-Hitam yang kami gunakan (dari Pengantar ke Algoritma oleh Cormen et al):

Pohon pencarian biner, di mana setiap node berwarna merah atau hitam dan

Akar hitam
Semua NULL node berwarna hitam
Jika simpul berwarna merah, maka kedua anaknya berwarna hitam.
Untuk setiap node, semua jalur dari node ke node NULL keturunan memiliki jumlah yang sama dari node hitam.

Catatan: kami tidak menghitung node NULL dalam definisi -seimbang di atas. (Meskipun saya percaya itu tidak masalah jika kita melakukannya). $\mu$

data-structures binary-trees search-trees Aryabhata
sumber

@Aryabhata: ada apa dengan keunikan ( ) dalam hasil edit Anda? Saya baik-baik saja dengan fakta bahwa -balanced menyiratkan -balanced. Saya tidak berpikir Anda harus menemukan tepat untuk membuktikan ketinggian adalah . Apakah saya melewatkan sesuatu?

μ^{'} > μ

$\mu'>\mu$

\frac{1}{3}

$\frac13$

\frac{1}{4}

$\frac14$

μ

$\mu$

O (\log n)

$O(\log n)$

jmad

Selain itu, Anda memerlukan pernyataan negatif untuk memberikan rantai sampel tandingan dengan satu pohon untuk setiap . Setiap rantai tak terbatas yang tidak berkurang dalam ukuran simpul akan cukup, bukan?

n \in N

$n \in \mathbb{N}$

Raphael

@jmad: Tanpa edit , setiap pohon sepele -sehingga kami punya jawaban sepele untuk pertanyaan itu. Saya ingin menghindarinya.

μ^{'}

$\mu'$

0

$0$

Aryabhata

@ Raphael: Saya tidak mengerti. Ukuran simpul pohon adalah . Anda mengatakan tidak masalah pohon apa yang kita pilih untuk dan ? Sepertinya tidak jelas bagi saya, dan itulah pertanyaannya!

n^{t h}

$n^{th}$

n

$n$

R B_{n}

$RB_n$

μ_{n} \to 0

$\mu_n \to 0$

Aryabhata

Versi sebelumnya dari pertanyaan ini menyatakan bahwa runtime dari algoritma rekursif pada pohon merah-hitam yang melakukan jumlah pekerjaan linear pada setiap langkah belum tentu . Klaim ini salah; tinggi-keseimbangan menyiratkan bahwa kedalaman pohon merah-hitam -node adalah . Dengan demikian, jika Anda melakukan bekerja di setiap tingkat pohon, pekerjaan total adalah .

O (n \log n)

$O(n\log n)$

n

$n$

O (\log n)

$O(\log n)$

O (n)

$O(n)$

O (n \log n)

$O(n \log n)$

JeffE

Jawaban:

Klaim : pohon Merah-hitam dapat sewenang-wenang un- -balanced. $\mu$

Ide Bukti : Isi subtree kanan dengan node sebanyak mungkin dan kiri dengan node sesedikit mungkin untuk jumlah dari node hitam pada setiap jalur root-leaf. $k$

Bukti : Tentukan urutan pohon merah-hitam sehingga memiliki simpul hitam pada setiap jalur dari akar ke daun manapun (virtual). Tentukan dengan $T_k$ $T_k$ $k$ $T_k = B(L_k, R_k)$

$R_k$ pohon lengkap dengan tinggi dengan tingkat pertama, ketiga, ... berwarna merah, yang lain hitam, dan $2k - 1$
$L_k$ pohon lengkap dengan ketinggian dengan semua node berwarna hitam. $k-1$

Jelas, semua adalah pohon merah-hitam. $T_k$

Misalnya, ini adalah , dan , masing-masing: $T_1$ $T_2$ $T_3$

T_1
^{[ sumber ]}

T_2
^{[ sumber ]}

T_3
^{[ sumber ]}

Sekarang mari kita verifikasi kesan visual dari sisi kanan yang lebih besar dibandingkan dengan yang kiri. Saya tidak akan menghitung daun virtual; mereka tidak memengaruhi hasilnya.

kiri selesai dan selalu memiliki tinggi dan karenanya mengandung node. Subtree kanan, di sisi lain, lengkap dan memiliki tinggi dan karenanya mengandung node. Sekarang nilai -balance untuk root adalah $T_k$ $k-1$ $2^k - 1$ $2k - 1$ $2^{2k}-1$ $\mu$

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

yang membuktikan bahwa tidak ada seperti yang diminta. $\mu > 0$

Raphael
sumber

Tidak. Pertimbangkan pohon merah-hitam dengan struktur khusus berikut.

Subtree kiri adalah pohon biner lengkap dengan kedalaman , di mana setiap node berwarna hitam. $d$
Subtree kanan adalah pohon biner lengkap dengan kedalaman , di mana setiap node pada kedalaman ganjil berwarna merah, dan setiap node pada kedalaman genap berwarna hitam. $2d$

Sangat mudah untuk memeriksa bahwa ini adalah pohon merah-hitam yang valid. Tetapi jumlah node di subtree kanan ( ) kira-kira kuadrat dari jumlah node di subtree kiri ( ). $2^{2d+1}-1$ $2^{d+1}-1$

JeffE
sumber

2^{2 d + 1} + 2^{d + 1} - 1

$2^{2d+1} + 2^{d+1} - 1$

n

$n$

n

$n$

@ Jeff JE: Pada dasarnya rantai counterexample kemudian akan menjadi subset 'padat', bukan subset 'jarang'. Mungkin saya akan mengubah rumusan pertanyaan.

Aryabhata