TechCodeview

Anlamadan önce Kırmızı-Siyah ağaç ve AVL ağacı Farklılıklar için Kırmızı-Siyah ağacını ve AVL ağacını ayrı ayrı bilmeliyiz.

Kırmızı-Siyah ağaç nedir?

Kırmızı-siyah ağaç kendi kendini dengeleyen bir ağaçtır. ikili arama ağacı her düğüm, düğümün rengini belirten fazladan bir bit bilgi içerir. Düğümün rengi, düğüm tarafından depolanan bit bilgisine bağlı olarak Kırmızı veya Siyah olabilir.

Özellikler

Kırmızı-Siyah ağaçla ilişkili özellikler şunlardır:

• Ağacın kök düğümü Siyah olmalıdır.
• Kırmızı bir düğümün yalnızca siyah çocukları olabilir. Veya iki bitişik düğümün renginin Kırmızı olamayacağını söyleyebiliriz.
• Düğümün sol veya sağ çocuğu yoksa bu düğüme yaprak düğüm denir. Böylece sol ve sağ çocukları yaprak düğüm olarak bilinen yaprak düğümünün altına yerleştiriyoruz. sıfır

Bir yaprak düğümün siyah derinliği veya siyah yüksekliği, yaprak düğümden kök düğüme gittiğimizde karşılaştığımız siyah sayısı olarak tanımlanabilir. Kırmızı-Siyah ağacın en önemli özelliklerinden biri her yaprak düğümünün aynı siyah derinliğe sahip olmasıdır.

Bu özelliği bir örnek üzerinden anlayalım.

Yukarıdaki ağaçta biri Kırmızı, diğer dördü Siyah olmak üzere beş düğüm vardır. Yukarıdaki ağaçta üç yaprak düğümü vardır. Şimdi her yaprak düğümünün siyah derinliğini hesaplıyoruz. Görebildiğimiz gibi üç yaprak düğümünün de siyah derinliği 2; dolayısıyla Kırmızı-Siyah bir ağaçtır.

Ağaç yukarıdaki üç özellikten herhangi birine uymuyorsa Kırmızı-Siyah ağaç değildir.

Kırmızı-siyah bir ağacın yüksekliği

java veritabanı jdbc

H'yi n düğüme sahip ağacın yüksekliği olarak düşünün. N'nin en küçük değeri ne olabilir? Tüm düğümler siyah olduğunda n'nin değeri en küçük olur. Eğer ağaç tüm siyah düğümleri içeriyorsa, ağaç tam bir ikili ağaç olacaktır. Tam bir ikili ağacın yüksekliği h ise, ağaçtaki düğüm sayısı şöyle olur:

n = 2sa -1

N'nin en büyük değeri ne olabilir?

Her siyah düğümün iki kırmızı çocuğu olduğunda n'nin değeri en büyüktür, ancak kırmızı düğümün kırmızı çocukları olamaz, dolayısıyla siyah çocukları olur. Bu şekilde siyah ve kırmızı çocukların alternatif katmanları vardır. Yani eğer siyah katmanların sayısı h ise kırmızı katmanların sayısı da h'dir; dolayısıyla ağacın toplam yüksekliği 2 saat olur. Toplam düğüm sayısı:

n = 2*2sa-1

AVL ağacı nedir?

Bir AVL ağacı Bir ikili arama ağacı ve dengeli bir ağaç olan aşağıdaki durumu gözlemlersek, kendi kendini dengeleyen bir ikili arama ağacıdır.

Yukarıdaki ağaçta, bir elemanı aramak için en kötü zaman karmaşıklığı O(h), yani ağacın yüksekliğidir. Yukarıdaki durumda 17 elemanı aramak için yapılan karşılaştırma sayısı 4 olup ağacın yüksekliği de 4 olmaktadır.

Aşağıda gösterildiği gibi çarpık ikili ağacı düşünürsek:

Yukarıdaki sağa çarpık ağaçta 17 elemanı aramak için yapılan karşılaştırma sayısı 5 olup, ağaçta bulunan eleman sayısı da 5'tir. Dolayısıyla eğer ağaç çarpık bir ikili ağaç ise o zaman zaman karmaşıklığı diyebiliriz. O(n) olacaktır.

Şimdi bu çarpık ağaçları O(h) zaman karmaşıklığına sahip olacak şekilde dengelememiz gerekiyor. olarak bilinen bir terim vardır. denge faktörü İkili arama ağacının kendi kendini dengelemesi için kullanılır. Denge faktörü şu şekilde hesaplanabilir:

Denge faktörünün değeri 1, 0 veya -1 olabilir. İkili ağaçtaki her bir düğüm 1, 0 veya -1 değerine sahipse bu ağaca dengeli bir ağaç denir. ikili ağaç veya AVL ağacı.

Her düğümün denge faktörü 0 ise ağaç mükemmel dengeli bir ağaç olarak bilinir. AVL ağacı neredeyse dengeli bir ağaçtır çünkü ağaçtaki her düğümün denge faktörü değeri 1, 0 veya -1'dir.

Kırmızı-Siyah ağaç ile AVL ağacı arasındaki farklar.

Kırmızı-Siyah ağaç ile AVL ağacı arasındaki farklar şunlardır:

İkili arama ağacı

Kırmızı-Siyah ağacı bir ikili arama ağacıdır ve AVL ağacı da bir ikili arama ağacıdır.

Java'da liste oluşturma

Tüzük

Kırmızı-Siyah Ağaçta aşağıdaki kurallar uygulanır:

1. Kırmızı-Siyah ağaçtaki düğümün rengi kırmızı veya siyahtır.
2. Kök düğümün rengi siyah olmalıdır.
3. Bitişik düğümler kırmızı olmamalıdır. Yani kırmızı düğümün kırmızı çocukları olamaz, siyah düğümün ise siyah çocukları olabilir diyebiliriz.
4. Her yolda aynı sayıda siyah düğüm bulunmalıdır; o halde yalnızca bir ağaç Kırmızı-Siyah ağaç olarak kabul edilebilir.
5. Dış düğümler, her zaman siyah renkte olan sıfır düğümlerdir.

AVL ağacının kuralı:

Her düğümün denge faktörü -1, 0 veya 1 olmalıdır.

Örnek

Yukarıdaki şekilde ağacın Kırmızı-Siyah ağaç olup olmadığını kontrol etmemiz gerekiyor. Bunu kontrol etmek için öncelikle ağacın ikili arama ağacı olup olmadığını kontrol etmemiz gerekir. Yukarıdaki şekilde de görebileceğimiz gibi ikili arama ağacının tüm özelliklerini karşılamaktadır; bu nedenle ikili arama ağacıdır. İkinci olarak yukarıda belirtilen kurallara uyup uymadığını doğrulamamız gerekiyor. Yukarıdaki ağaç yukarıdaki beş kuralın tamamını karşılamaktadır; dolayısıyla yukarıdaki ağacın Kırmızı-Siyah bir ağaç olduğu sonucuna varılır.

win7 ne zaman çıktı

Yukarıdaki şekilde ağacın AVL ağacı olup olmadığını kontrol etmemiz gerekiyor. Her düğümün -1, 0 veya 1 gibi bir denge faktörü değeri olduğundan bu bir AVL ağacıdır.

Ağaç nasıl dengeli bir ağaç olarak değerlendirilebilir veya değerlendirilemez?

Kırmızı-Siyah ağaç durumunda, yukarıdaki kuralların tümü karşılanırsa, ağacın ikili arama ağacı olması koşuluyla, ağacın Kırmızı-siyah ağaç olduğu söylenir.

AVL ağacı durumunda denge faktörü -1, 0 veya 1 ise yukarıdaki ağacın AVL ağacı olduğu söylenir.

Dengeleme için kullanılan araçlar

Ağaç dengeli değilse Kırmızı-Siyah ağaçta ağacı dengelemek için iki araç kullanılır:

Yeniden renklendirme Döndürme

Ağaç dengeli değilse AVL ağacında ağacı dengelemek için bir araç kullanılır:

Döndürme

Hangi operasyon için verimli

Kırmızı-Siyah ağaç durumunda ekleme ve silme işlemleri etkilidir. Yeniden renklendirme yoluyla ağaç dengelenirse Kırmızı-Siyah ağaçta ekleme ve silme işlemleri verimli olur.

AVL ağacı durumunda arama işlemi, ağacı dengelemek için yalnızca bir araç gerektirdiğinden verimlidir.

Zaman karmaşıklığı

Kırmızı-Siyah ağaç durumunda, ekleme, silme ve arama gibi tüm işlemler için zaman karmaşıklığı O(logn)'dur.

AVL ağacı durumunda, ekleme, silme ve arama gibi tüm işlemler için zaman karmaşıklığı O(logn)'dur.

Tablo biçimindeki farklılıkları anlayalım.