16 MAYIS 2017
CUMARTESİ
21.30
Ayrık Matematik - Binary Search Tree (İkili Arama Ağacı)

Ağaç şekline benzetildiği için Binary Search Tree ismini alan ikili arama algoritmasının gösterimini bir örnek üzerinden inceleyeceğiz.

 

ÖRNEK

Dizimiz: 5, -3, 10, 5, 7, 12, 1, -4, 15, -3, 10, 9, 9, 7,8

Yukarıdaki diziyi Binary Search Tree ile gösterin ve aşağıdaki soruları cevaplayın.

  • Ağacın seviyesi kaçtır? (level)
  • Kaç tane düğümlenmiş yaprak olduğunu gösterin. (leaf nodes)
  • 8 sayısına kaç adımda ulaştığınızı ve adımları gösterin. Genişlik ve Derinlik yöntemlerinin ikisiyle de gösterin. (Breadth and Depth)
  • -4 sayısına kaç adımda ulaştığınızı ve adımları gösterin. Genişlik ve Derinlik yöntemlerinin ikisiyle de gösterin. (Breadth and Depth)

ÇÖZÜM

İlk olarak ağacı nasıl yapacağımızdan bahsedelim. Binary Search Algoritmasını hatırlıyorsak ortanca elemanı buluyor ve ona göre devam ediyorduk. Burda ise dizinin ilk elemanını ortanca eleman kabul ediyoruz ve geri kalanları ona göre sıralıyoruz. Dikkat etmemiz gereken kuralı ise dizinin ilk 2 elemanını göstererek anlatıyorum;

  • 5
  • EĞER -3 > 5 KOŞULU SAĞLANIYORSA -3 DEĞERİNİ SAĞ TARAFA YAZ
  • EĞER -3 < 5 VEYA -3 = 5 KOŞULLARI SAĞLANIYORSA -3 DEĞERİNİ SOL TARAFA YAZ

Bu iki kurala göre aşağıdaki ağacı çizebiliriz.

Dikkat: Ağaçta aynı dalda 2'den fazla yaprak bulunamıyor. Bu yapraktan kastımız yukarıdaki sarı kutularımız. Çünkü bir sayıdan küçük veya büyük olayı vardır. Dahası yoktur. Şimdi ilk birkaç adımı inceleyelim;

Dizimizi hatırlayalım: 5, -3, 10, 5, 7, 12, 1, -4, 15, -3, 10, 9, 9, 7,8

1. Değer: 5
En tepede ortada yerini aldı.

2. Değer: -3
-3 > 5 koşulu yanlış. Sol tarafa yeni bir dal ekledik ve yaprağına -3 yazdık.

3. Değer: 10
10 > 5 koşulu doğru. Sağ tarafa yeni bir dal ekledik ve yaprağına 10 yazdık.

4. Değer: 5
5 > 5 koşulu yanlış. Sol tarafa yöneldik.
5 > -3 koşulu doğru. Sağ tarafa yeni bir dal ekledik ve yaprağına 5 yazdık.

5. Değer: 7
7 > 5 koşuğu doğru. Sağ tarafa yöneldik.
7 > 10 koşulu yanlış. Sol tarafa yeni bir dal ekledik ve yaprağına 7 yazdık.

....

Şeklinde devam ediyor.


Ağacın seviyesi kaçtır? (level)


Ağacın seviyesinden kastedilen kaç satırdan oluştuğudur. Satırları aşağıdaki gibi sayabiliriz.

Toplamda 7 satırdan oluşmaktadır.


Kaç tane düğümlenmiş yaprak olduğunu gösterin. (leaf nodes)


Düğümlenmiş yaprak olarak ifade edebileceğimiz bu alanlar ağacımızda hiçbir dala sahip olmayan alanlardır. Aşağıdaki görselimizde inceleyebiliriz;

Toplamda 5 tane düğümlenmiş yaprak vardır.


8 sayısına kaç adımda ulaştığınızı ve adımları gösterin. Genişlik ve Derinlik yöntemlerinin ikisiyle de gösterin. (Breadth and Depth)


Genişlik ve Derinlik ibareleri şunu kasteder;

Breadth (Genişlik-En) : Arama yapılırken ağacın tepesinden başlanır. Sonrasında satır satır gidilir. Yani bu örneğimizde aradığımız 8 sayısı için Breadth yöntemiyle arama yaparsak şöyle bir diziye ulaşırız;

5, -3, 10, -4, 5, 7, 12, -3, 1, 7, 10, 15, 9, 9, 8 ve toplamda 15 adımda ulaşmış oluruz. (En kötü senaryo olur.)

Depth (Derinlik) : Bunda ise yine ağacın en tepesinden başlarız fakat bu kez sürekli sola giderek arama yaparız. Yani şöyle bir arama yöntemimiz olur;

5, -3, -4, -3, 5, 1, 10, 7, 7, 10, 9, 9, 8 ve toplamda 13 adımda ulaşmış oluruz.


-4 sayısına kaç adımda ulaştığınızı ve adımları gösterin. Genişlik ve Derinlik yöntemlerinin ikisiyle de gösterin. (Breadth and Depth)


Bu soru için yeniden görsel hazırlamıyorum. Direkt olarak iki yöntemimizde adımlarımızı yazıyorum (önceki soru ile aynı);

Breadth: 5, -3, 10, -4 ve toplamda 4 adımda ulaşmış olduk.

Depth: 5, -3, -4 ve toplamda 3 adımda ulaşmış olduk.

YORUMLAR 0
Bu konuya henüz kimse yorum yapmadı.
İlk yorumu sen yapmak ister misin?
YORUM BIRAK
Şuanda bu yoruma cevap yazıyorsunuz:
İptal Et