TechCodeview

İkili arama ağacı ve AVL ağacı farklılıklarını bilmeden önce ikili arama ağacını ve AVL ağacını ayrı ayrı bilmeliyiz.

İkili Arama Ağacı Nedir?

ikili arama ağacı bir ağaç ikili ağaç . Bildiğimiz gibi o ağacın 'n' sayıda çocuğu olabilir, oysa; ikili ağaç en fazla iki çocuğu içerebilir. Dolayısıyla ikili ağacın kısıtlamasını ikili arama ağacı da takip eder. İkili arama ağacındaki her düğümün en fazla iki çocuğu olmalıdır; diğer bir deyişle ikili arama ağacının ikili ağacın bir çeşidi olduğunu söyleyebiliriz.

İkili arama ağacı aynı zamanda ikili aramanın özelliklerini de takip eder. İkili aramada bir dizideki tüm öğelerin sıralı olması gerekir. Orta elemanın sol kısmının orta değerden küçük değeri, orta elemanın sağ kısmının ise orta değerden büyük değerleri içerdiği ikili aramada orta elemanı hesaplarız.

İkili Arama Ağacı'nda ortadaki eleman kök düğüm, sağ kısım sağ alt ağaç ve sol kısım sol alt ağaç olur. Bu nedenle ikili arama ağacının bir kombinasyonu olduğunu söyleyebiliriz. ikili ağaç Ve Ikili arama .

Not: İkili Arama Ağacı, sol alt ağacın tüm elemanlarının kök düğümden küçük olduğu ve sağ alt ağacın tüm elemanlarının kök düğümden büyük olduğu ikili ağaç olarak tanımlanabilir.

İkili Arama Ağacında Zaman Karmaşıklığı

Eğer ikili arama ağacı neredeyse dengeli bir ağaç ise, o zaman tüm işlemler şu kadar zaman karmaşıklığına sahip olacaktır: O(giriş) çünkü arama sol veya sağ alt ağaca bölünmüştür.

python sıralama tuple'ı

Eğer ikili arama ağacı sola ya da sağa çarpıksa tüm işlemler şu kadar zaman karmaşıklığına sahip olacaktır: Açık) çünkü n elemana kadar ilerlememiz gerekiyor.

AVL Ağacı nedir?

Bir AVL ağacı sol ve sağ alt ağaçların yükseklikleri arasındaki farkın birden fazla olamayacağı, kendi kendini dengeleyen bir ikili arama ağacıdır. Bu fark denge faktörü olarak bilinir. AVL ağacında denge faktörünün değerleri -1, 0 veya 1 olabilir.

İkili arama ağacının kendi kendini dengelemesi nasıl gerçekleşir?

AVL ağacının kendi kendini dengeleyen bir ikili arama ağacı olduğunu biliyoruz. İkili arama ağacı dengeli değilse bazı yeniden düzenlemelerle kendi kendine dengelenebilir. Bu yeniden düzenlemeler bazı rotasyonlar kullanılarak yapılabilir.

vijay sinema oyuncusu

Kendi kendini dengelemeyi bir örnekle anlayalım.

Diyelim ki eklemek istiyoruz 10, 20, 30 bir AVL ağacında.

Bir AVL ağacına 10, 20, 30 eklemenin yolları şunlardır:

Ekleme sırası 30, 20, 10 ise.

Aşama 1: Öncelikle aşağıda gösterildiği gibi bir İkili arama ağacı oluşturuyoruz:

Adım 2: Yukarıdaki şekilde 30 nolu düğümün denge faktörü 2 olduğu için ağacın dengesiz olduğunu görebiliyoruz. Bunu bir AVL ağacı yapmak için bazı döndürmeler yapmamız gerekiyor. Eğer 20. düğümde doğru rotasyon yaparsak, aşağıda gösterildiği gibi 30. düğüm aşağı doğru hareket edecek, 20. düğüm ise yukarı doğru hareket edecektir:

Gözlemleyebileceğimiz gibi, son ağaç İkili Arama ağacının ve dengeli ağacın özelliğini takip eder; bu nedenle bir AVL ağacıdır.

Bu durumda, ağaç dengesiz ağaç bırakılmış, böylece düğümde doğru rotasyonu gerçekleştiririz.

Ekleme sırası 10, 20, 30 ise.

Aşama 1: Öncelikle aşağıda gösterildiği gibi bir İkili arama ağacı oluşturuyoruz:

Adım 2: Yukarıdaki şekilde 10. düğümün denge faktörünün -2 olması nedeniyle ağacın dengesiz olduğunu görebiliyoruz. Bunu bir AVL ağacı haline getirmek için bazı döndürmeler yapmamız gerekiyor. Sağa dengesiz bir ağaç olduğundan sola dönüş yapacağız. 20. düğümde sola dönüş yaparsak, aşağıda gösterildiği gibi 20. düğüm yukarıya, 10. düğüm ise aşağıya doğru hareket edecektir:

Görebildiğimiz gibi, son ağaç, İkili Arama ağacı ve bir dengeli ağaç ; bu nedenle bir AVL ağacıdır.

Ekleme sırası 30, 10, 20 ise

Aşama 1: Öncelikle aşağıda gösterildiği gibi İkili Arama ağacını oluşturuyoruz:

Adım 2: Yukarıdaki şekilde kök düğümün denge faktörü 2 olduğundan ağacın dengesiz olduğunu görebiliyoruz. AVL ağacı yapmak için bazı döndürmeler yapmamız gerekiyor. Yukarıdaki senaryo sol-sağ dengesizdir çünkü bir düğüm ana düğümünün solunda, diğeri ise ana düğümünün sağındadır. İlk önce sola dönüş yapacağız ve dönüş 10 ve 20 numaralı düğümler arasında gerçekleşecek. Sola dönüşten sonra aşağıda gösterildiği gibi 20 yukarıya, 10 ise aşağıya doğru hareket edecek:

Yine de ağaç dengesiz olduğundan ağaçta doğru döndürme işlemini gerçekleştiriyoruz. Ağaçta doğru dönüş gerçekleştirildikten sonra ağaç aşağıda gösterildiği gibi olur:

Yukarıdaki ağaçta da görebileceğimiz gibi ağaç, İkili Arama ağacının ve dengeli bir ağacın özelliğini takip eder; bu nedenle bir AVL ağacıdır.

Ekleme sırası 10, 30, 20 ise

Aşama 1: Öncelikle aşağıda gösterildiği gibi İkili Arama ağacını oluşturuyoruz:

denetimli makine öğrenimi

Adım 2: Yukarıdaki şekilde kök düğümün denge faktörü 2 olduğundan ağacın dengesiz olduğunu görebiliyoruz. AVL ağacı yapmak için bazı döndürmeler yapmamız gerekiyor. Yukarıdaki senaryo, bir düğüm ana düğümünün sağında ve başka bir düğüm ana düğümünün solunda olduğundan sağ-sol dengesizdir. Öncelikle 30 ve 20 nolu düğümler arasında gerçekleşen sağa dönüş işlemini gerçekleştireceğiz. Sağa dönüş sonrasında aşağıda gösterildiği gibi 20 yukarıya, 30 ise aşağıya doğru hareket edecektir:

Yine de yukarıdaki ağaç dengesiz olduğundan düğümde sola dönüş yapmamız gerekiyor. Sola dönüş gerçekleştirildikten sonra, 20 nolu düğüm yukarıya doğru hareket edecek ve 10 nolu düğüm aşağıda gösterildiği gibi aşağıya doğru hareket edecektir:

Yukarıdaki ağaçta da görebileceğimiz gibi ağaç, İkili Arama ağacının ve dengeli bir ağacın özelliğini takip eder; bu nedenle bir AVL ağacıdır.

İkili Arama ağacı ile AVL ağacı arasındaki farklar