Qırmızı-Qara Ağac Giriş

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Kod milləti Facebook google Über
Qabaqcıl Məlumat Strukturu İkili Axtarış Ağacı İkili ağac Məlumatların quruluşu AğacBaxılıb 69

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Qırmızı Qara Ağac özünü tarazlayan ikili bir ağacdır. Bu ağacda hər düyün ya qırmızı, ya da qara bir düyündür. Bu Qırmızı-qara ağac girişində, onun bütün əsas xüsusiyyətlərini əhatə etməyə çalışacağıq.

Qırmızı-Qara Ağacın xüsusiyyətləri

  1. Hər düyün ya qırmızı, ya da qara kimi təmsil olunur.
  2. Kök nod həmişə qara olur.
  3. Qırmızı düyünün qırmızı bir ana və ya qırmızı uşağı ola bilməz (yəni iki qırmızı düyün bitişik deyil).
  4. Hər hansı bir qovşaqdan NIL nəslinə qədər olan hər bir yol bərabər sayda qara qovşaq içerməlidir.

Qırmızı-Qara Ağacın etibarlı və etibarsız nümunələri

Qırmızı-Qara Ağac GirişPin

Qırmızı-Qara Ağac GirişPin

Zaman Mürəkkəbliyinin Təhlili

Axtarış, yerləşdirmə, silmə və s. Kimi bütün BST əməliyyatları O (h) vaxtında həyata keçirilə bilər, burada h qırmızı-qara ağacın hündürlüyüdür və balanslı BST üçün hündürlük həmişə qaydadır. giriş (n) [n-> qovşaq sayı].

Axtarış = O (log (n))
Taxmaq = O (log (n))
silinməsi = O (log (n))

Qırmızı-Qara Ağacda Qara Boy

Qırmızı-qara ağacdakı Qara Boy, hər hansı bir düyündən yarpağa (NIL-dir) sadə yolda (eyni nodu iki dəfə ziyarət etmirsiniz) qara düyünlərin sayı olaraq təyin olunur. Bh (x) ilə təmsil olunur.

Qırmızı-Qara Ağacın Boyu

Fərqli AVL ağac, boy tarazlığı o qədər də sərt deyil, ancaq qırmızı-qara ağaclarda fırlanma sayı AVL ağaclarına nisbətən daha azdır.
Qırmızı-qara ağacın hündürlüyü h <= 2 (log (n + 1)) {Günlük bazası 2} Ətraflı sübut niyə RB ağaclarının hündürlüyü <= 2 log (n + 1).

Boyundakı tarazlığı qorumaq üçün qırmızı-qara bir ağac yenidən rəngləmə və yenidən quruluşdan istifadə edir.

RB ağaclarının necə rəng aldığını və yenidən qurduğunu görə bilərsiniz burada.

Yenidən rəngləmə

Bəzi qırmızı düyünlərin rəngini qara və əksinə dəyişdirməyə aiddir, qırmızı düyünün qırmızı valideyninin qardaşı qırmızı olduqda edilir.

Qırmızı-Qara Ağac GirişPin

 

Yenidən qurulma

Bu ağacın fırlanmasına aiddir, qırmızı bir uşağın qırmızı bir ata və qara və ya boş əmisi olduqda edilir. Yenidənqurma ilə bağlı dörd hal var,

  • Sağ
  • Sol
  • Sağ Sol
  • Sol sağ

Pin

Applications

  • Özünü balanslaşdıran BST tətbiq etmək üçün real dünya kitabxanalarında istifadə olunur.
  • Kimi istifadə olunur TreeSet və JAVA-da TreeMap və C ++ dilində Sets və Maps.

Axtarış

Qırmızı-qara ağac BST-dir, buna görə də RBT-də axtarış BST-də axtarışla eynidir, düyünün rəngi heç bir əhəmiyyət daşımır.

Crack Sistemi Dizayn Müsahibələri
Translate »