Yayvan ağaçlar, kendi kendini dengeleyen veya kendi kendini ayarlayan ikili arama ağaçlarıdır. Başka bir deyişle yayılım ağaçlarının ikili arama ağaçlarının varyantları olduğunu söyleyebiliriz. İkili arama ağaçları hakkında bilmemiz gereken yayılım ağaçları için ön koşul.
Zaten bildiğimiz gibi, her durumda ikili arama ağacının zaman karmaşıklığı. Ortalama durumda bir ikili arama ağacının zaman karmaşıklığı O(giriş) ve en kötü durumda zaman karmaşıklığı O(n)'dir. İkili arama ağacında, sol alt ağacın değeri kök düğümden küçüktür ve sağ alt ağacın değeri kök düğümden büyüktür; bu durumda zaman karmaşıklığı şu şekilde olur: O(giriş) . İkili ağaç sola çarpık veya sağa çarpıksa zaman karmaşıklığı O(n) olacaktır. Çarpıklığı sınırlamak için, AVL ve Kırmızı-Siyah ağaç fotoğrafın içine geldi, O(giriş ) tüm durumlarda tüm işlemler için zaman karmaşıklığı. Ayrıca daha pratik uygulamalar yaparak bu zaman karmaşıklığını da geliştirebiliriz, böylece yeni Ağaç Yayvan Ağaç Nedir?
Yayvan bir ağaç kendi kendini dengeleyen bir ağaçtır, ancak AVL ve Kırmızı-Siyah ağaçlar da kendi kendini dengeleyen ağaçlardır o zaman. Yayvan ağacı benzersiz kılan şey iki ağaçtır. Onu eşsiz kılan ekstra bir özelliği var; yayılıyor.
Bir yayvan ağaç, bir ağaçla aynı işlemleri içerir. İkili arama ağacı , yani Ekleme, silme ve arama, ancak aynı zamanda bir işlem daha içerir, yani yayma. Bu yüzden. yayılma ağacındaki tüm işlemler yayılma tarafından takip edilir.
Yayvan ağaçlar tam olarak dengeli ağaçlar değildir, ancak kabaca dengeli ağaçlardır. Yayvan ağaçtaki arama işlemini anlayalım.
Aşağıda gösterilen ağaçta 7 öğeyi aramak istediğimizi varsayalım:
Yayılım ağacındaki herhangi bir öğeyi aramak için öncelikle standart ikili arama ağacı işlemini gerçekleştireceğiz. 7 10'dan küçük olduğundan kök düğümün soluna geleceğiz. Arama işlemini gerçekleştirdikten sonra yayma işlemini yapmamız gerekiyor. Burada yayılma, herhangi bir öğe üzerinde gerçekleştirdiğimiz işlemin, bazı yeniden düzenlemeler yaptıktan sonra kök düğüm haline gelmesi gerektiği anlamına gelir. Ağacın yeniden düzenlenmesi rotasyonlar yoluyla yapılacaktır.
Not: Yayvan ağaç, öğe üzerinde gerçekleştirilen herhangi bir işlemin, üzerinde işlemin gerçekleştirildiği öğenin ağacın kök düğümü olacağı şekilde ağacı yeniden düzenleyebileceği, kendi kendini ayarlayan ağaç olarak tanımlanabilir.
Rotasyonlar
Yayılma için kullanılan altı tür döndürme vardır:
- Zig dönüşü (Sağa dönüş)
- Zag dönüşü (Sola dönüş)
- Zig zag (Zig ve ardından zag)
- Zag zig (Zag'ın ardından zig)
- Zig zig (iki sağa dönüş)
- Zag zag (iki sola dönüş)
Bir rotasyon tipinin seçilmesi için gerekli faktörler
Döndürme türünün seçilmesinde kullanılan faktörler şunlardır:
- Döndürmeye çalıştığımız düğümün büyük ebeveyni var mı?
- Düğüm ebeveynin sol çocuğu mu yoksa sağ çocuğu mu?
- Düğüm büyük ebeveynin sol çocuğu mu yoksa sağ çocuğu mu?
Rotasyonlara ilişkin durumlar
Dava 1: Düğümün büyük ebeveyni yoksa ve ebeveynin sağ çocuğu ise sola döndürme gerçekleştiririz; aksi takdirde doğru dönüş gerçekleştirilir.
Durum 2: Düğümün bir büyükanne ve büyükbabası varsa, o zaman aşağıdaki senaryolara göre; rotasyon gerçekleştirilecektir:
Senaryo 1: Düğüm ebeveynin hakkıysa ve ebeveyn aynı zamanda ebeveyninin de hakkıysa, o zaman zig zig sağa sağa dönüş gerçekleştirilir.
Senaryo 2: Düğüm bir ebeveynin solundaysa ancak ebeveyn ebeveyninin sağındaysa, o zaman zig zag sağa sola dönüş gerçekleştirilir.
Senaryo 3: Düğüm ebeveynin sağındaysa ve ebeveyn ebeveynin sağındaysa, o zaman zig zig sola sola dönüş gerçekleştirilir.
Senaryo 4: Düğüm bir ebeveynin sağındaysa ancak ebeveyn, ebeveyninin solundaysa, o zaman zig zag sağa-sola dönüş gerçekleştirilir.
Şimdi yukarıdaki rotasyonları örneklerle anlayalım.
Ağacı yeniden düzenlemek için bazı rotasyonlar yapmamız gerekiyor. Yayılım ağacındaki döndürme türleri şunlardır:
Aranacak öğe bir kök düğüm veya bir kök düğümün çocuğu (yani sol veya sağ çocuk) olduğunda zig dönüşleri kullanılır.
Arama sırasında yayılma ağacında bulunabilecek durumlar şunlardır:
Dava 1: Arama öğesi ağacın kök düğümüyse.
Durum 2: Arama öğesi kök düğümün çocuğuysa, o zaman iki senaryo olacaktır:
- Çocuğun sol çocuk olması durumunda, zig sağa dönüş olarak bilinen sağa dönüş gerçekleştirilecektir.
- Çocuğun sağ çocuk olması durumunda, zig sola dönüş olarak bilinen sola dönüş gerçekleştirilecektir.
Yukarıdaki iki senaryoyu bir örnek üzerinden inceleyelim.
Aşağıdaki örneği düşünün:
Yukarıdaki örnekte ağaçta 7 elementi aramamız gerekiyor. Aşağıdaki adımları takip edeceğiz:
Aşama 1: İlk olarak 7'yi bir kök düğümle karşılaştırıyoruz. 7, 10'dan küçük olduğundan kök düğümün sol çocuğudur.
Adım 2: Eleman bulunduğunda yayma işlemini gerçekleştireceğiz. Sağa dönüş, aşağıda gösterildiği gibi 7'nin ağacın kök düğümü olacağı şekilde gerçekleştirilir:
Başka bir örneği ele alalım.
Yukarıdaki örnekte ağaçta 20 eleman aramamız gerekiyor. Aşağıdaki adımları takip edeceğiz:
Aşama 1: Öncelikle 20'yi bir kök düğümle karşılaştırıyoruz. 20 kök düğümden büyük olduğundan kök düğümün sağ çocuğudur.
Adım 2: Eleman bulunduğunda yayma işlemini gerçekleştireceğiz. Sola dönüş, 20 elemanın ağacın kök düğümü olacağı şekilde gerçekleştirilir.
Bazen aranacak öğenin hem büyükanne hem de büyükbabaya sahip olması durumunda durum ortaya çıkar. Bu durumda yayma için dört dönüş yapmamız gerekiyor.
Bu durumu bir örnek üzerinden anlayalım.
Aşağıda gösterilen ağaçta 1 öğeyi aramamız gerektiğini varsayalım:
Aşama 1: Öncelikle 1 elementini aramak için standart bir BST arama işlemi yapmamız gerekiyor. 1, 10 ve 7'den küçük olduğundan, 7 düğümünün solunda olacaktır. Bu nedenle, öğe 1'in bir ebeveyni, yani 7'si ve aynı zamanda bir büyük ebeveyni, yani 10'u vardır.
Adım 2: Bu adımda yayma işlemini yapmamız gerekiyor. Bazı döndürmeler yardımıyla 1. düğümü kök düğüm yapmamız gerekiyor. Bu durumda basitçe zig veya zag dönüşü gerçekleştiremeyiz; zig zig rotasyonunu uygulamalıyız.
1. düğümü kök düğüm yapmak için zig zig dönüşleri olarak bilinen iki sağa dönüş yapmamız gerekir. Sağa dönüş yaptığımızda aşağıdaki şekilde görüldüğü gibi 10 nolu nokta aşağıya doğru hareket edecek, 7 nolu düğüm ise yukarı doğru gelecektir:
Yine zig sağa dönüş gerçekleştireceğiz, aşağıda gösterildiği gibi 7. düğüm aşağı doğru hareket edecek, 1. düğüm ise yukarı gelecek:
Yukarıdaki şekilde gördüğümüz gibi 1. düğüm ağacın kök düğümü haline gelmiş; bu nedenle arama tamamlandı.
Aşağıdaki ağaçta 20'yi aramak istediğimizi varsayalım.
20'yi aramak için iki sola dönüş yapmamız gerekiyor. 20 düğümü aramak için gereken adımlar şunlardır:
Aşama 1: Öncelikle standart BST arama işlemini gerçekleştiriyoruz. 20, 10 ve 15'ten büyük olduğundan 15. düğümün sağında olacaktır.
Adım 2: İkinci adım yayılımı gerçekleştirmektir. Bu durumda iki sola dönüş gerçekleştirilecektir. İlk dönüşte, 10. düğüm aşağıya doğru hareket edecek ve 15. düğüm aşağıda gösterildiği gibi yukarıya doğru hareket edecektir:
İkinci sola dönüşte, düğüm 15 aşağıya doğru hareket edecek ve düğüm 20, aşağıda gösterildiği gibi ağacın kök düğümü haline gelecektir:
Sola iki dönüş yapıldığını gözlemlediğimiz gibi; bu nedenle zig zig sola dönüş olarak bilinir.
Şu ana kadar hem ebeveyn hem de büyükanne ve büyükbabanın RR veya LL ilişkisi içinde olduğunu okuduk. Şimdi ebeveyn ile büyükanne ve büyükbaba arasındaki RL veya LR ilişkisini göreceğiz.
Bu durumu bir örnek üzerinden anlayalım.
Aşağıda gösterilen ağaçta 13 öğeyi aramak istediğimizi varsayalım:
Aşama 1: Öncelikle standart BST arama işlemini gerçekleştiriyoruz. 13, 10'dan büyük ancak 15'ten küçük olduğundan, 13. düğüm, 15. düğümün sol çocuğu olacaktır.
Adım 2: 13. düğüm 15'in solunda ve 15. düğüm 10. düğümün sağında olduğundan RL ilişkisi vardır. Öncelikle 15. düğümde sağa dönüş yapıyoruz ve aşağıda gösterildiği gibi 15. düğüm aşağı doğru hareket edecek, 13. düğüm ise yukarı gelecek:
Yine de 13. düğüm kök düğüm değildir ve 13. düğüm kök düğümün sağındadır, dolayısıyla zag dönüşü olarak bilinen sola dönüş gerçekleştireceğiz. 10 numaralı düğüm aşağı doğru hareket edecek ve 13 numaralı düğüm aşağıda gösterildiği gibi kök düğüm haline gelecektir:
Yukarıdaki ağaçta gördüğümüz gibi 13. düğüm kök düğüm haline gelmiş; bu nedenle arama tamamlandı. Bu durumda önce zig dönüşünü, ardından zag dönüşünü gerçekleştirdik; bu nedenle zig zag dönüşü olarak bilinir.
Bu durumu bir örnek üzerinden anlayalım.
Aşağıda gösterilen ağaçta 9 öğeyi aramak istediğimizi varsayalım:
Aşama 1: Öncelikle standart BST arama işlemini gerçekleştiriyoruz. 9, 10'dan küçük fakat 7'den büyük olduğundan, 7. düğümün sağ çocuğu olacaktır.
Adım 2: 9. düğüm 7. düğümün sağında ve 7. düğüm 10. düğümün solunda olduğundan LR ilişkisi vardır. Öncelikle 7. düğümde sola dönüş gerçekleştiriyoruz. Aşağıda gösterildiği gibi 7. düğüm aşağı doğru, 9. düğüm ise yukarı doğru hareket edecek:
Yine de 9 numaralı düğüm bir kök düğüm değildir ve 9, kök düğümün solundadır, dolayısıyla zig dönüşü olarak bilinen sağa dönüş işlemini gerçekleştireceğiz. Sağa dönüş gerçekleştirildikten sonra 9. düğüm aşağıda gösterildiği gibi kök düğüm haline gelir:
Yukarıdaki ağaçta da görebileceğimiz gibi 13. düğüm bir kök düğümdür; bu nedenle arama tamamlandı. Bu durumda önce zag dönüşünü (sola dönüş) gerçekleştirdik ve ardından zig dönüşü (sağa dönüş) gerçekleştirdik, bu nedenle zag zig dönüşü olarak bilinir.
Splay ağacının avantajları
- Yayılım ağacında ekstra bilgileri saklamamıza gerek yok. Buna karşılık, AVL ağaçlarında, ekstra alan gerektiren her düğümün denge faktörünü saklamamız gerekir ve Kırmızı-Siyah ağaçlar ayrıca düğümün rengini (Kırmızı veya Siyah) belirten fazladan bir bit bilgi depolamaya ihtiyaç duyar.
- Çeşitli pratik uygulamalar için en hızlı İkili Arama ağacı türüdür. İçinde kullanılır Windows NT ve GCC derleyicileri .
- Sık erişilen düğümler kök düğüme yaklaşacağından daha iyi performans sağlar, bu sayede öğelere yayvan ağaçlarda hızlı bir şekilde erişilebilir. Son zamanlarda erişilen veriler önbellekte saklandığı için önbellek uygulamasında kullanılır, böylece verilere erişmek için belleğe gitmemize gerek kalmaz ve daha az zaman alır.
Splay ağacının dezavantajı
Yayvan ağacın en büyük dezavantajı, ağaçların tam anlamıyla dengeli olmaması, yani kabaca dengeli olmalarıdır. Bazen yayılım ağaçları doğrusaldır, dolayısıyla O(n) zaman karmaşıklığı alacaktır.
Splay ağacına ekleme işlemi
İçinde ekleme işleminde öncelikle öğeyi ağaca yerleştiririz ve daha sonra eklenen öğe üzerinde yayma işlemini gerçekleştiririz.
15, 10, 17, 7
Aşama 1: Öncelikle ağaca 15. düğümü ekliyoruz. Yerleştirdikten sonra yayma işlemi yapmamız gerekiyor. 15 kök düğüm olduğu için yayma işlemi yapmamıza gerek yok.
Adım 2: Bir sonraki eleman 10'dur. 10, 15'ten küçük olduğundan, aşağıda gösterildiği gibi, düğüm 10, düğüm 15'in sol çocuğu olacaktır:
Şimdi gerçekleştiriyoruz yayılıyor . 10'u kök düğüm yapmak için aşağıda gösterildiği gibi doğru döndürme işlemini gerçekleştireceğiz:
Aşama 3: Bir sonraki eleman 17'dir. 17, 10 ve 15'ten büyük olduğundan 15. düğümün sağ çocuğu olacaktır.
Şimdi yayma işlemini gerçekleştireceğiz. 17 yaşında hem bir ebeveyn hem de büyükanne ve büyükbaba olduğu için zig zig rotasyonları gerçekleştireceğiz.
Yukarıdaki şekilde 17'nin ağacın kök düğümü haline geldiğini görebiliriz; bu nedenle ekleme işlemi tamamlanır.
Adım 4: Bir sonraki eleman 7'dir. 7, 17, 15 ve 10'dan küçük olduğundan, 7. düğüm 10'un çocuğu olarak kalacaktır.
Şimdi ağacı yaymamız gerekiyor. 7'nin hem bir ebeveyni hem de büyükanne ve büyükbabası olduğundan, aşağıda gösterildiği gibi iki sağa dönüş gerçekleştireceğiz:
Yine de 7 numaralı düğüm bir kök düğüm değil, kök düğümün yani 17'nin sol çocuğudur. Dolayısıyla, 7 numaralı düğümü aşağıda gösterildiği gibi kök düğüm yapmak için bir sağa dönüş daha yapmamız gerekiyor:
Ekleme işlemi için algoritma
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
Yukarıdaki algoritmada T ağaç ve n eklemek istediğimiz düğümdür. Kök düğümün adresini içeren bir geçici değişken oluşturduk. Temp değeri NULL olana kadar while döngüsünü çalıştıracağız.
Ekleme tamamlandıktan sonra yayma işlemi gerçekleştirilecektir.
Yayılma işlemi için algoritma
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
Yukarıdaki uygulamada x, rotasyonun gerçekleştirildiği düğümdür, oysa y, x düğümünün sol çocuğudur.
left.rotation(T, x) uygulamasının uygulanması
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Yukarıdaki uygulamada x, rotasyonun gerçekleştirildiği düğümdür ve y, x düğümünün sağ çocuğudur.
Splay ağacında silme
Yayılma ağaçlarının İkili arama ağacının varyantları olduğunu bildiğimizden, yayılım ağacındaki silme işlemi BST'ye benzer olacaktır, ancak tek fark yayılma ağaçlarında silme işleminin ardından yayma işleminin gelmesidir.
Silme Türleri:
Yayılım ağaçlarında iki tür silme vardır:
- Aşağıdan yukarıya yayılma
- Yukarıdan aşağıya yayılma
Aşağıdan yukarıya yayılma
Aşağıdan yukarıya yaymada öncelikle öğeyi ağaçtan sileriz, ardından silinen düğüm üzerinde yayma işlemini gerçekleştiririz.
Splay ağacındaki silme işlemini anlayalım.
Aşağıda gösterilen ağaçtan 12, 14'ü silmek istediğimizi varsayalım:
if else ifadeleri java
- Öncelikle 12 elementi silmek için standart BST silme işlemini gerçekleştiriyoruz. 12 bir yaprak düğüm olduğundan, düğümü ağaçtan sileriz.
Silme işlemi henüz tamamlanmadı. Silinen düğümün ebeveynini, yani 10'u yaymamız gerekiyor. Gösterim(10) ağaçta. Yukarıdaki ağaçta gördüğümüz gibi 10 nolu düğümün sağında, 7 nolu düğüm ise 13 nolu düğümün solundadır. Yani önce 7 nolu düğümde sola döndürme işlemi yapıyoruz, ardından 7 numaralı düğümde sağa döndürme işlemi gerçekleştiriyoruz. 13, aşağıda gösterildiği gibi:
Yine de 10. düğüm bir kök düğüm değildir; 10. düğüm, kök düğümün sol çocuğudur. Bu nedenle, 10. düğümü aşağıda gösterildiği gibi bir kök düğüm yapmak için kök düğümde doğru rotasyonu (yani 14) gerçekleştirmemiz gerekir:
- Şimdi aşağıda gösterilen ağaçtan 14. elemanı silmemiz gerekiyor:
Bildiğimiz gibi dahili düğümü kolayca silemeyiz. Düğümün değerini aşağıdakileri kullanarak değiştireceğiz: sıralı öncül veya sıra dışı halef . Değeri sağ alt ağaçta bulunan en düşük değerle değiştirdiğimiz sıralı ardıl kullandığımızı varsayalım. 14. düğümün sağ alt ağacındaki en düşük değer 15'tir, dolayısıyla 14 değerini 15 ile değiştiririz. 14. düğüm yaprak düğüm haline geldiğinden, onu aşağıda gösterildiği gibi silebiliriz:
Ancak silme işlemi henüz tamamlanmadı. Bir işlem daha yapmamız gerekiyor, yani silinen düğümün ebeveynini kök düğüm olarak yapmamız gereken yayılma. Silme işleminden önce, 14. düğümün ebeveyni kök düğümdü, yani 10. dolayısıyla bu durumda herhangi bir yayma işlemi yapmamız gerekiyor.
Yukarıdan aşağıya yayılma
Yukarıdan aşağıya yayılımda öncelikle silme işlemi yapılacak olan yayılımı gerçekleştiriyoruz ve ardından düğümü ağaçtan siliyoruz. Eleman silindikten sonra birleştirme işlemini gerçekleştireceğiz.
Yukarıdan aşağıya yayılmayı bir örnek üzerinden anlayalım.
Aşağıda gösterilen ağaçtan 16'yı silmek istediğimizi varsayalım:
Aşama 1: Yukarıdan aşağıya yayılımda, ilk olarak 16 nolu düğüm üzerinde yayılım gerçekleştiriyoruz. 16 nolu düğümün hem ebeveyni hem de büyük ebeveyni var. Düğüm 16 ebeveyninin sağındadır ve ebeveyn düğüm de ebeveyninin sağındadır, yani bu bir zag zag durumudur. Bu durumda önce 13. düğümde, ardından 14. düğümde aşağıda gösterildiği gibi sola dönüş gerçekleştireceğiz:
Düğüm 16 hala bir kök düğüm değildir ve kök düğümün sağ çocuğudur, bu nedenle düğüm 16'yı kök düğüm yapmak için düğüm 12 üzerinde sola dönüş yapmamız gerekir.
16 nolu düğüm bir kök düğüm haline geldiğinde, 16 nolu düğümü sileceğiz ve aşağıda gösterildiği gibi iki farklı ağaç elde edeceğiz, yani sol alt ağaç ve sağ alt ağaç.
Sol alt ağacın değerlerinin her zaman sağ alt ağacın değerlerinden daha küçük olduğunu biliyoruz. Sol alt ağacın kökü 12 ve sağ alt ağacın kökü 17'dir. İlk adım, sol alt ağacın maksimum elemanını bulmaktır. Sol alt ağaçta maksimum eleman 15 olup, daha sonra 15 üzerinde yayma işlemi yapmamız gerekmektedir.
Yukarıdaki ağaçta görebileceğimiz gibi, 15. elementin hem bir ebeveyni hem de büyük ebeveyni vardır. Bir düğüm ebeveyninin sağındadır ve ebeveyn düğüm de ebeveyninin sağındadır, bu nedenle, 15 numaralı düğümü aşağıda gösterildiği gibi bir kök düğüm yapmak için iki sola dönüş yapmamız gerekir:
Ağaç üzerinde iki dönüş gerçekleştirildikten sonra 15 numaralı düğüm kök düğüm haline gelir. Gördüğümüz gibi 15'in sağ çocuğu NULL olduğundan 17. düğümü aşağıda gösterildiği gibi 15'in sağ kısmına ekliyoruz ve bu işleme katılmak operasyon.
Not: Silinecek öğe yayılma ağacında mevcut değilse yayma işlemi gerçekleştirilir. Yayılma, NULL'a ulaşmadan önce en son erişilen öğe üzerinde gerçekleştirilecektir.
Silme işleminin algoritması
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
Yukarıdaki algoritmada öncelikle kökün Null olup olmadığını kontrol ediyoruz; kök NULL ise ağacın boş olduğu anlamına gelir. Ağaç boş değilse silinecek eleman üzerinde yayma işlemini gerçekleştireceğiz. Yayılma işlemi tamamlandıktan sonra kök verileri silinecek öğeyle karşılaştıracağız; her ikisi de eşit değilse, öğenin ağaçta bulunmadığı anlamına gelir. Eşit olmaları durumunda aşağıdaki durumlar meydana gelebilir:
Dava 1 : Kökün solu NULL'dur, kökün sağı kök düğüm olur.
Durum 2 : Hem sol hem de sağ mevcutsa, sol alt ağaca maksimum öğeyi yayarız. Yayılma tamamlandığında, maksimum eleman sol alt ağacın kökü olur. Sağ alt ağaç, sol alt ağacın kökünün sağ çocuğu olacaktır.