AVL Ağacı, 1962'de GM Adelson - Velsky ve EM Landis tarafından icat edildi. Ağaca, mucitlerinin onuruna AVL adı verildi.
AVL Ağacı, her düğümün, sağ alt ağacının yüksekliğinin sol alt ağacının yüksekliğinden çıkarılmasıyla hesaplanan bir denge faktörüyle ilişkilendirildiği, yüksekliği dengeli ikili arama ağacı olarak tanımlanabilir.
Her düğümün denge faktörü -1 ile 1 arasındaysa ağacın dengeli olduğu söylenir, aksi takdirde ağaç dengesiz olur ve dengelenmesi gerekir.
Denge Faktörü (k) = yükseklik (sol(k)) - yükseklik (sağ(k))
Herhangi bir düğümün denge faktörünün 1 olması, sol alt ağacın sağ alt ağaçtan bir seviye daha yüksek olduğu anlamına gelir.
Herhangi bir düğümün denge faktörünün 0 olması, sol alt ağaç ile sağ alt ağacın eşit yüksekliğe sahip olduğu anlamına gelir.
Herhangi bir düğümün denge faktörü -1 ise, sol alt ağacın sağ alt ağaçtan bir seviye daha aşağıda olduğu anlamına gelir.
Aşağıdaki şekilde bir AVL ağacı verilmiştir. Her düğüme ilişkin denge faktörünün -1 ile +1 arasında olduğunu görebiliriz. bu nedenle AVL ağacının bir örneğidir.
Karmaşıklık
| Algoritma | Ortalama durum | En kötü durumda |
|---|---|---|
| Uzay | Açık) | Açık) |
| Aramak | o(log n) | o(log n) |
| Sokmak | o(log n) | o(log n) |
| Silmek | o(log n) | o(log n) |
AVL ağacındaki işlemler
AVL ağacı aynı zamanda bir ikili arama ağacı olduğundan, tüm işlemler ikili arama ağacında yapıldığı gibi gerçekleştirilir. Arama ve geçiş, AVL ağacının özelliğinin ihlaline yol açmaz. Ancak ekleme ve silme işlemleri bu özelliği ihlal edebilecek işlemler olduğundan tekrar gözden geçirilmesi gerekmektedir.
| SN | Operasyon | Tanım |
|---|---|---|
| 1 | Ekleme | AVL ağacına ekleme, ikili arama ağacında yapıldığı gibi gerçekleştirilir. Ancak AVL ağaç özelliğinde ihlallere yol açabilir ve dolayısıyla ağacın dengelenmesi gerekebilir. Ağaç rotasyonlar uygulanarak dengelenebilir. |
| 2 | Silme | Silme işlemi, ikili arama ağacında yapıldığı gibi aynı şekilde de gerçekleştirilebilir. Silme işlemi aynı zamanda ağacın dengesini de bozabilir, bu nedenle ağacı yeniden dengelemek için çeşitli döndürme türleri kullanılır. |
Neden AVL Ağacı?
AVL ağacı, ikili arama ağacının yüksekliğini, çarpık olmasına izin vermeyerek kontrol eder. Yüksekliği h olan ikili arama ağacındaki tüm işlemler için harcanan zaman Ah) . Ancak şu şekilde genişletilebilir: Açık) BST çarpık hale gelirse (yani en kötü durum). AVL ağacı, bu yüksekliği log n ile sınırlandırarak her operasyona bir üst sınır uygular. O(log n) burada n, düğüm sayısıdır.
AVL Rotasyonları
AVL ağacında rotasyonu yalnızca Denge Faktörünün aşağıdakilerden farklı olması durumunda gerçekleştiririz. -1, 0 ve 1 . Temel olarak dört tür rotasyon vardır:
- L L döndürme: Eklenen düğüm A'nın sol alt ağacının sol alt ağacındadır
- R R döndürme : Eklenen düğüm A'nın sağ alt ağacının sağ alt ağacındadır
- L R döndürme: Eklenen düğüm A'nın sol alt ağacının sağ alt ağacındadır
- R L döndürme : Eklenen düğüm A'nın sağ alt ağacının sol alt ağacındadır
A düğümü, denge faktörü -1, 0, 1'den farklı olan düğümdür.
İlk iki dönüş LL ve RR tek dönüştür ve sonraki iki dönüş LR ve RL çift dönüştür. Bir ağacın dengesiz olması için minimum yüksekliğin en az 2 olması gerekir, Her dönüşü anlayalım
1. RR Rotasyonu
BST, A'nın sağ alt ağacının sağ alt ağacına bir düğüm yerleştirilmesi nedeniyle dengesiz hale geldiğinde, RR rotasyonu gerçekleştiririz, RR rotasyonu, denge faktörü -2 olan bir düğümün altındaki kenara uygulanan saat yönünün tersine bir rotasyondur.
sanjay dutt ve
Yukarıdaki örnekte, A düğümü -2 denge faktörüne sahiptir çünkü bir C düğümü, A sağ alt ağacının sağ alt ağacına eklenmiştir. RR rotasyonunu A'nın altındaki kenarda gerçekleştiriyoruz.
2. LL Rotasyonu
BST dengesiz hale geldiğinde, C'nin sol alt ağacının sol alt ağacına bir düğüm eklenmesi nedeniyle LL rotasyonu gerçekleştiririz, LL rotasyonu saat yönünde rotasyondur ve bu, denge faktörü 2 olan bir düğümün altındaki kenara uygulanır.
Yukarıdaki örnekte, C düğümü denge faktörü 2'ye sahiptir çünkü bir A düğümü, C sol alt ağacının sol alt ağacına eklenir. LL rotasyonunu A'nın altındaki kenarda gerçekleştiriyoruz.
3. LR Dönüşü
Çift dönüşler, yukarıda açıklanan tek dönüşe göre biraz daha zordur. LR döndürme = RR döndürme + LL döndürme, yani ilk RR döndürme alt ağaçta gerçekleştirilir ve ardından LL döndürme tam ağaçta gerçekleştirilir, tam ağaç derken, denge faktörü -1 dışında olan eklenen düğümün yolundaki ilk düğümü kastediyoruz. , 0 veya 1.
Her adımı çok net bir şekilde anlayalım:
| Durum | Aksiyon |
|---|---|
 | Bir B düğümü, A'nın sağ alt ağacına, C'nin sol alt ağacına eklenmiştir, bu nedenle C, denge faktörü 2'ye sahip dengesiz bir düğüm haline gelmiştir. Bu durum L R dönüşüdür, burada: Eklenen düğüm, sol alt ağacın sağ alt ağacındadır. C |
 | LR döndürme = RR + LL döndürme olduğundan, ilk olarak A'da köklü alt ağaçta RR (saat yönünün tersine) gerçekleştirilir. RR rotasyonu yapılarak düğüm A , sol alt ağacı haline geldi B . |
 | RR rotasyonu gerçekleştirildikten sonra, C düğümü hala dengesizdir, yani eklenen A düğümü sol veya sol tarafta olduğundan denge faktörü 2'ye sahiptir. C |
 | Şimdi tam ağaçta, yani C düğümünde LL saat yönünde dönüş gerçekleştiriyoruz. C artık B düğümünün sağ alt ağacı haline geldi, A, B'nin sol alt ağacı oldu |
 | Her düğümün denge faktörü artık -1, 0 veya 1'dir, yani BST artık dengelenmiştir. |
4. RL Dönüşü
Daha önce tartışıldığı gibi, bu çift dönüşler, yukarıda açıklanan tek dönüşten biraz daha zordur. RL döndürme = LL döndürme + RR döndürme, yani ilk önce LL döndürme alt ağaçta gerçekleştirilir ve ardından RR döndürme tam ağaçta gerçekleştirilir, tam ağaç derken, denge faktörü -1 dışında olan eklenen düğümün yolundaki ilk düğümü kastediyoruz. , 0 veya 1.
Java'nın sonu
| Durum | Aksiyon |
|---|---|
 | Bir düğüm B sol alt ağacına eklendi C sağ alt ağacı A , bu nedenle A, denge faktörü -2 olan dengesiz bir düğüm haline geldi. Bu durum RL rotasyonudur: Eklenen düğüm, A'nın sağ alt ağacının sol alt ağacındadır. |
 | RL döndürme = LL döndürme + RR döndürme olduğundan, alt ağaçta LL (saat yönünde) köklüdür. C ilk olarak gerçekleştirilir. RR rotasyonu yapılarak düğüm C sağ alt ağacı haline geldi B . |
 | LL döndürme işlemini gerçekleştirdikten sonra düğüm A hala dengesizdir, yani denge faktörü -2'ye sahiptir, bunun nedeni sağ alt ağaç düğümü A'nın sağ alt ağacıdır. |
 | Şimdi tam ağaçta, yani A düğümünde RR döndürme (saat yönünün tersine döndürme) gerçekleştiriyoruz. C artık B düğümünün sağ alt ağacı haline geldi ve A düğümü, B'nin sol alt ağacı oldu. |
 | Her düğümün denge faktörü artık -1, 0 veya 1'dir, yani BST artık dengelenmiştir. |
Soru: Aşağıdaki öğelere sahip bir AVL ağacı oluşturun
H, I, J, B, A, E, C, F, D, G, K, L
1. H, I, J'yi ekleyin
Yukarıdaki elemanların eklenmesi üzerine, özellikle H durumunda, H'nin Denge Faktörü -2 olduğundan BST dengesiz hale gelir. BST sağa çarpık olduğundan H düğümünde RR Döndürme işlemi gerçekleştireceğiz.
Ortaya çıkan denge ağacı şu şekildedir:
2. B, A'yı ekleyin
Yukarıdaki elemanların eklenmesi üzerine, özellikle A durumunda, H ve I'nin Denge Faktörü 2 olduğundan BST dengesiz hale gelir, son eklenen düğümden yani H'den ilk düğümü dikkate alırız. H'den gelen BST sola çarpık olduğundan, H düğümünde LL Dönüşü gerçekleştireceğiz.
Ortaya çıkan denge ağacı şu şekildedir:
3. E'yi takın
E eklendiğinde, I'in Denge Faktörü 2 olduğundan BST dengesiz hale gelir, çünkü E'den I'ye gidersek, I'in sağ alt ağacının sol alt ağacına yerleştirildiğini görürüz, I düğümünde LR Döndürme gerçekleştiririz. LR = RR + LL dönüşü
3 a) İlk önce B düğümünde RR rotasyonu gerçekleştiriyoruz
RR döndürmesinden sonra ortaya çıkan ağaç şöyledir:
3b) İlk önce I düğümünde LL rotasyonunu gerçekleştiriyoruz
LL döndürmesinden sonra ortaya çıkan dengeli ağaç şöyledir:
4. C, F, D'yi ekleyin
C, F, D'yi eklediğimizde BST dengesiz hale gelir, çünkü B'nin Denge Faktörü ve H -2'dir, çünkü D'den B'ye gidersek B'nin sol alt ağacının sağ alt ağacına yerleştirildiğini görürüz. Düğüm I'de RL Döndürme. RL = LL + RR döndürme.
meşale kurulumu
4a) İlk önce E düğümünde LL rotasyonu gerçekleştiriyoruz
LL döndürmesinden sonra ortaya çıkan ağaç:
4b) Daha sonra B düğümünde RR rotasyonu gerçekleştiririz
RR döndürmesinden sonra ortaya çıkan dengeli ağaç şöyledir:
5. G'yi takın
G eklendiğinde, H'nin Denge Faktörü 2 olduğu için BST dengesiz hale gelir, çünkü G'den H'ye gidersek, H'nin sağ alt ağacının sol alt ağacına yerleştirildiğini görürüz, I düğümünde LR Döndürme gerçekleştiririz. LR = RR + LL dönüşü.
5 a) İlk önce C düğümünde RR rotasyonu gerçekleştiriyoruz
RR döndürmesinden sonra ortaya çıkan ağaç şöyledir:
5 b) Daha sonra H düğümünde LL rotasyonu gerçekleştiririz
LL döndürmesinden sonra ortaya çıkan dengeli ağaç şöyledir:
6. K'yi ekleyin
K eklendiğinde, I'in Denge Faktörü -2 olduğundan BST dengesiz hale gelir. BST I'den K'ye sağa çarpık olduğundan, I düğümünde RR Döndürme işlemi gerçekleştireceğiz.
RR döndürmesinden sonra ortaya çıkan dengeli ağaç şöyledir:
7. L'yi takın
L ağacı eklenirken her düğümün Denge Faktörü artık -1, 0, +1 olduğundan hala dengelidir. Dolayısıyla ağaç Dengeli bir AVL ağacıdır
