Bugün de Binary Search Tree konusuna değineceğiz. Bu teknik diğerlerinden iyi mi derseniz, pek öyle olduğunu söyleyemem ancak bu teknikteki önemli nokta verilerin geliş sırasıdır. Hemen örnekleyelim.
a)5,6,1,7,3,2 şeklinde veriler gelmiş olsun.
b)5,6,2,7,3,1 şeklinde veriler gelmiş olsun.
Yukarıdaki şekle bakalım. a şıkkında, önce 5 geldi. Ardından 6 geliyor. 6>5 olduğundan, 5'in sağına koyduk. Ardından 1 geliyor. 1<5>5 olduğundan sağa geçtik. 7>6 da olduğundan, 6'nın da sağına koyduk. Hemen peşinden 3 geldi. 3<5>1 olduğundan da, 1'in soluna koyduk. Aynı şekilde 2'yi de yerleştirdik.
b şıkkında da aynı şekilde büyüklük küçüklük sıralamasına göre yerleştirdik. 2, 1'den daha önce geliyor, a şıkkından farklı olarak. Bu da ağacın farklılaşmasına sebep olmakta.
Ağacın derinliği kısa olursa, veriyi bulmak da o denli hızlı olur. Kaldı ki, ağaç dengeli olursa, derinlik de kısa olur takdir edeceğiniz gibi. Normal şartlarda veri artsa da, derinlik hemen artmasın isteriz fakat bu algoritmada zor gibi...
Veri arama ve ekleme bu şekilde rahatlıkla yapılabilir. Peki silme işlemi nasıl yapılır? Hemen açıklayalım...
3 maddede inceleyeceğiz silme işlemini.
1) Silinecek olan düğüm, yaprak düğüm(leaf node) ise, silme işlemi hiçbir ekstra işlem yapmadan, direkt gerçekleştirilir.
2) Silinecek olan düğümün bir çocuğu(child node) varsa, o düğümün atasının bilgisi çocuğuna aktarılır.
3) Silinecek olan düğümün iki çocuğu varsa, silinen düğüm yerine, o düğümün sağdaki alt ağacındaki en küçük değerleri düğüm yazılır. Daha sonra da getirilen düğüm, eski yerinden silinir.
Şimdi tüm bu anlattıklarımı örnek üzerinde açıklayalım. Google'dan bir resim yürüttüm hemen.
Gördüğünüz gibi, ilk etapta X düğümü silinmiş. X, yaprak bir düğüm olduğu için sorunsuz bir şekilde yok ediliyor.
İkinci örnekte ise, G silinmiş. G düğümünün bir çocuğu var(X). Dolayısıyla G, atasının(F) bilgisini, çocuğuna(X) vermeli. Yani başka bir deyişle, atası ile çocuğunu birbirine bağlamalı. F ile X birbirine bağlanır...
Son örnekte ise D silinmiş. D düğümünün B ve F adında iki çocuğu var. Az önce açıkladığımız üzere, D'nin sağ alt ağacına bakıyoruz, yani F-E-G-X'in oluşturduğu ağaç. Ardından bu ağaçtaki en küçük değerli düğümü, sileceğimiz D düğümünün yerine getiriyoruz. Bu alt ağaçtaki en küçük değer E'ye ait. E düğümü D'nin yerine konduktan sonra da, E düğümü silinir...
Silme işlemi de bu kadar arkadaşlar. Genel anlamda BST(Binary Search Trees)'yi görmüş olduk.
Görüşmek üzere..
Hiç yorum yok:
Yorum Gönder