Avl-ağaçları (Trees) Dengeli İkili Ağaç



Yüklə 461 b.
tarix04.07.2017
ölçüsü461 b.


AVL-Ağaçları (Trees)


Dengeli İkili Ağaç

  • İkili arama ağacının dezavantajı, yüksekliğin N-1 kadar olabilmesidir.

  • Bunun manası: Ekleme ve silme ve diğer bir çoğu işlem gerçekleştirilirken karmaşıklığın en kötü durumda O(N) olmasıdır.

  • İstenen özellik ağacın yüksekliğinin küçük olmasıdır.

  • N tane düğümü olan ikili ağacın yüksekliği en az (log N) ‘ dir.

  • Bu nedenle, amaç ikili arama ağacının yüksekliğini O(log N) olarak tutabilmektir.

  • Bu tür ağaçlara dengeli ikili ağaçlar denilir. Örnekler AVL ağaçlar, kırmızı-siyah ağaçlar (red-black tree)



AVL ağaçlar

  • Bir düğümün yüksekliği

  • Bir yaprağın yüksekliği 1’dir. Null işaretçinn yüksekliği sıfırdır.

  • İç bir düğümün yüksekliği çocuklarının maksimum yüksekliğinin 1 fazlasıdır.

  • Not: Burada yapılan yükseklik tanımı daha önce yapılandan farklıdır.



AVL Ağaçlar

  • AVL ağaç bir ikili ağaçtır ve aşağıdaki şartı sağlar

    • ağaçtaki herbir düğüm için, sol ve sağ altağaçların yükseklikleri en fazla 1 farklılık gösterir.


AVL Ağaç

  • x, yüksekliği h olan bir AVL ağacın kökü olsun.

  • Nh , yüksekliği h olan bir AVL ağaçtaki düğümlerin minimum sayısını göstersin.

  • Açıkça görülebilir ki Ni ≥ Ni-1

  • Böylece

  • Genel form aşağıdaki gibi olur.

  • Sınır şartlar: N1=1 ve N2 =2. Buradan h = O(log Nh) manası çıkarılır.

  • Böylece, AVL ağaç üzerinde yapılacak işlemlerin çoğu O(log N) zaman alır.



Dönüşler (Rotations)

  • Ağaç yapısı değiştiği zaman (ekleme veya silme gibi), AVL ağaç özelliğini sağlama için ağacı değiştirmeliyiz.

  • Bu işlem tek dönüş veya çift dönüş yapılarak sağlanır.



Dönüşler

  • Ekleme/ silme işlemi tek bir düğüm ekleme ve silme içerdiği için, bazı altağaçların yüksekliği 1 kadar artabilir / azalabilir.

  • Böylece, bir x düğümünde, AVL ağaç özelliği ihlal edildiği zaman, bunun manası of left(x) ve right(x) kesinlikle 2 birim fark ediyor demektir.

  • AVL ağaç özelliğini korumak için x’ e dönüpler uygulanacaktır.



Ekleme (Insertion)

  • Öncelikle, sıradan bir ikili ağaca ekleniyormuş gibi yeni anahtarı yeni bir yaprak olarak ekle

  • Yeni yapraktan köke kadar olan yolu takip et. Karşılaşılan herbir x düğümü için left(x) ve right(x) ‘in en fazla 1 farklılık içerip içermediğini kontrol et.

  • Evet ise parent(x) ile devam et. Değilse, ya bir tek dönüş yada bir çift dönüş ile

  • Eklem için, x düğümünde bir dönüş gerçekleştirdikten sonra, x’ in geri kalan ata sında herhangi bir dönüp gerçekleştirilmesine gerek yoktur.



Ekleme

  • X, left(x) ve right(x) değerlerinin birden fazla farklı olduğu yerde bir düğüm olsun.

  • x in yüksekliğini h+3 olduğunu varsayalım

  • Bu halde 4 durum oluşur.

    • left(x) in yüksekliği h+2 (yani right(x) in yüksekliği h)
      • left(left(x)) in yüksekliği h+1  sol çocuk ile (üzerinde) tek dönüş
      • right(left(x)) in yüksekliği h+1  sol çocuk ile çift dönüş
    • right(x) yüksekliği h+2 (yani left(x) in yüksekliği h)
      • right(right(x)) in yüksekliği h+1  sağ çocuk ile (üzerinde) tek dönüş
      • left(right(x)) in yüksekliği h+1  sağ çocuk ile (üzerinde) çift dönüş


Tek dönüş



Tek dönüş





Çift dönüş



Çift dönüş





Genişletilmiş örnek









Silme

  • Sıradan bir ikili ağaçta olduğu gibi x düğümünü sil. Daha sonra köke olan yol aşağıdaki gibi incelenir.

  • Karşılaşılan herbir x düğümü için sol(x) (left(x)) ve sağ(x) (right(x)) altağaçlarının yükseklik farkının 1 olup olmadığına bak. Eğer fark 1 ise ebeveyn(x) üzerinden işleme devam et. Aksi takdirde x üzerinde gerekli dönüşleri yap. Eklemede olduğu gibi silmede de 4 durum vardır.

  • Silme için, x’de dönüş yaptıktan sonra, x’in atalarında da (ancestor) dönüşler yapmamız gerekebilir. Bu işlemi köke ulaşana kadar uygularız.



Deletion

  • Silme için tek dönüşler 4 duruma (iki durum yerine ) ayrılabilir. On closer examination: the single rotations for deletion can be divided into 4 cases (instead of 2 cases)

    • Sol çocukla dönüşler için iki durum.
    • Sağ çocukla dönüşler için iki durum.


Silme işlemindeki tek dönüşler



Silme işlemindeki tek dönüşler



Silmedeki dönüşler

  • Tek dönüş için 4 durum vardır fakat hepsini ayrı ayrı değerlendirmeye gerek olmayabilir.

  • Çift dönüş için eklemede olduğu gibi 2 durum vardır.

  • Dolayısı ile eklemede belirlendiği mantıkla silmede de hangi dönüşlerin gerçekleştirilebileceği belirlenebilir.





Поделитесь с Вашими друзьями:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2019
rəhbərliyinə müraciət

    Ana səhifə