İkili Arama Ağacı (Binary Search Tree)
Yazan : Şadi Evren ŞEKER
İkili ağaçların (Binary Tree) özel bir hali olan ikili arama ağaçlarında, düğümlerde duran bilgilerin birbirine göre küçüklük büyüklük ilişkisi bulunmalıdır. Örneğin tam sayılardan(integer) oluşan veriler tutulacaksa bu verilerin aralarında küçük-büyük ilişkisi bulunmaktadır.
İkili arama ağacı, her düğümün solundaki koldan ulaşılabilecek bütün verilerin düğümün değerinden küçük, sağ kolundan ulaşılabilecek verilerin değerinin o düğümün değerinden büyük olmasını şart koşar.
Örneğin yukarıda bir ikili arama ağacı tasvir edilmiştir. Bu ağaçta dikkat edilecek olursa kökün solunda bulunan bütün sayılar kökten küçük ve sağında bulunan bütün sayılar kökten büyüktür.
İkili arama ağacına bu kurala uygun olarak ekleme çıkarma veya silme işlemleri yapılabilir. Ancak yapılan her işlemden sonra ikili arama ağacının yapısı bozulmamış olmalıdır.
İkili arama ağacında arama işlemi:
Yukarıda da anlatıldığı üzere ağacın üzerinde duran verilerin özel bir şekilde sıralı bulunması gerekir. Buna göre herhangi bir değeri arayan kişi ağacın kök değerine bakarak aşağıdaki 3 eylemden birisini yapar:
- Aranan sayı kökteki değere eşittir -> Aranan değer bulunmuştur
- Aranan sayı kökteki değerden küçüktür -> Kökün sol kolu takip edilir
- Aranan sayı kökteki deüerden büyüktür -> Kökün sağ kolu takip edilir
İkili arama ağaçlarının önemli bir özelliği ise öz çağıran(recursive) oluşudur. Buna göre bir ağacın sol kolu veya sağ kolu da birer ağaçtır. Bu özellikten faydalanarak örneğin C dilinde aşağıdaki şekilde bir arama fonksiyonu yazılabilir:
dugum * ara(dugum *kok, int deger){
if(deger == kok->veri){
return kok;
}
else if(deger > kok->veri ){
return ara(kok->sag, deger);
}
else{
return ara(kok->sol,deger);
}
}
Yukarıdaki bu örnekte daha önce ikili ağaçlar konusunda tanımlanmış bir düğüm struct’ı kullanılmıştır. Koda dikkat edilecek olursa özçağıran bir yapı görülebilir. Yani fonksiyonun içerisinde kendisi çağrılmış ve yeni kök değeri olarak mevcut kökün sol veya sağ değeri verilmiştir. Arana değer her durumda değişmediği için alt düğümlere kadar aynı olarak indirilmiştir.
Yukarıdaki koddaki önemli bir eksiklik ise kodun ağaç üzerinde bir sayıyı bulamaması durumunun tasarlanmamış olmasıdır. Bu durumda basitçe NULL değer kontrolü ile aşılabilir. Buna göre sol veya sağa gitmeden önce sol veya sağda bir değer olduğuna bakılmalı şayet değer varsa gidilmelidir. Şayet değer yoksa ağaçta bu sayının bulunma ihtimali yoktur ve bu sayının olmadığını belirten bir ifade (örneğin NULL) döndürülmelidir. Kodun bu şekilde tashih edilmiş hali aşağıda verilmiştir:
dugum * ara(dugum *kok, int deger){
if(deger == kok->veri){
return kok;
}
else if(deger > kok->veri ){
if(kok->sag != NULL)
return ara(kok->sag, deger);
else
return NULL;
}
else{
if(kok->sag != NULL)
return ara(kok->sol,deger);
else
return NULL
}
}
Çok yararı oldu, anlatım için teşekkürler 🙂
Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search
for the number 363. Which of the following sequences could not be the sequence of nodes
examined ?
a. 2, 252, 401, 398, 330, 344, 397, 363.
b. 924, 220, 911, 244, 898, 258, 362, 363.
c. 925, 202, 911, 240, 912, 245, 363.
d. 2, 399, 387, 219, 266, 382, 381, 278, 363.
e. 935, 278, 347, 621, 299, 392, 358, 363.
Hocam selamlar,
Bir problem ile karşı karşıyayım, açıkçası sorunun ne demek istediğini de çok anlayamadım, bu problemi çözmek için uğraştım ama beceremedim. Bu konuda bana yardımcı olabilir misiniz?
Teşekkürler, iyi çalışmalar.
Önce soruyu anlayalım. Soru şıklardan hangisinin bir ikili arama ağacındaki (binary search tree) dolaşım yollarından birisi olamayacağını sormaktadır.
İkili arama ağacında, basitçe sağdaki sayılar düğümden büyük ve soldaki sayılar düğümdeki sayıdan küçüktür. Diğer bir deyişle, örneğin bir düğümün önce sağına sonra bu sağdaki düğümün soluna gidilirse, artık gezilen sayılar bu iki sayı arasında olmalıdır.
şeklinde verilen bir ağaç için, A->C yolundan sonra, sayıların tamamı A’dan büyük ve C’den küçük olmalıdır. Benzer şekilde A->B yolundan sonra da sayılar B’den büyük ve A’dan küçük olmalıdır.
Bu gerçek göz önüne alındığında yukarıdaki sorunuzda verilen bazı şıklar hatalı olur.
a şıkkını ele alalım:
2->252->401 yolundan sonra sayılar küçülmeye başlamış. Bunun anlamı bu aşamadan sonraki sayıların 252 ve 401 arasında olması gerektiğidir ki bu durum sağlanıyor. Ardından 398->330 dönüşü gelmiş ki buradan sonraki sayıların tamamı da 398 ve 330 arasındadır. Kısacası a şıkkı ikili arama ağacının dolaşmasına uygundur.
b şıkkını ele alalım:
924->220 yolundan sonra gelen sayılar 220 ile 924 arasına olmalıdır ki sağlanmıştır.
220->911 yolundan sonraki sayılar bu arada olmalıdır ki sağlanmıştır.
911->244 aralığı sağlamıştır
244->898 sağlanmıştır
898->258 sağlanmıştır
c şıkkını ele alalım:
925->202 dönüşünden sonraki sayılar 925 ile 202 arasında olmalıdır ki sağlanmıştır.
202->911 dönüşünden sonraki sayıların hepsi 202 ve 911 arasında olmalıdır ancak bu şart sağlanmamıştır ve dizilimde 912 bulunmaktadır.
Bu durumu daha iyi anlamay çalışalım. Yukarıdaki dizilimin olması için aşağıdaki ağaç yapısı bulunmalıdır:
925 / 202 911 / 240 912yukarıdaki gösterim ağaçta sol ve sağ şeklindeki hareketlerin neticesidir. Görüldüğü üzere 240 sayısından sonra sağ düğüme yani büyük olan tarafa gidilmiştir. Oysaki 240’ın sağında 912 olamaz!!!
Bunun sebebi 912 gibi bir sayının ağaçta bulunması halinde 911’in sağında olması gerekliliğidir.
Kısacası c şıkkı bir ikili ağaç dolaşımı olarak kabul edilemez.
Diğer şıklara hızlıca baktım ve sanırım e şıkkında da problem var.
347->621 geçişinden sonra 299 gelmesi mümkün değildir. 299 sayısı 347’nin solunda olması gereken ve bir kere 621 yolu ile sağa gidildikten sonra karşılaşılmaması gereken sayıdır.
Başarılar
Hocam anlatımınız için çok teşekkür ederim oldukça faydalı oldu. Çalışmalarınızda kolaylıklar.
Hocam merhaba,
Let T be a binary search tree, let x be a leaf node, and let y be its parent. Show that key[y] is
either the smallest key in T larger than key[x] or the largest key in the tree smaller than key[x].
—————————————–
Soruda belirtildiği üzere x’in y düğümünün yavrusu olduğundan bahsedilmiş. Cümlenin ikinci kısmında ise T ağacında y’nin değerinin hem en küçük hem de yavrusu olan x değerinden büyük olması gerektiğinden bahsedilmiş. Bu durum ağacın sol kısmının olmaması durumunda mümkün oluyor. Ancak diğer durum için karşılamıyor.
Bu konuda ne yapabilirim.
Teşekkürler.
Önce sorunun Türkçesini anlayalım:
Soruda, herhangi bir T ağacında, x yaprak düğüm olması halinde, ve y bu düğümün atası olması halinde iki şarttan biri gerçekleşir denilmiş:
y, x’ten büyük, ağaçtaki (Tree) en küçük düğümdür , veya
y, x’ten küçük, ağaçtaki (Tree) en büyük düğümdür.
Yukarıdaki şartları ispatlamamız istenmiş. İspata geçmeden önce durumu canlandırmak için bir iki hali gösterelim.
Sorudaki durum aşağıdaki şekilde yorumlanabilir:
ancak bu y düğümünün (node) ağacın neresinde olduğu hakkında bir bilgi yok. Sadece x’in bir yaprak düğüm olduğunu biliyoruz (leaf node). Bu durumda ağacın herhangi bir yerinde olabilir, ağacın en solunda veya sağında olabileceği gibi, ortalarda da yer alabilir.
A / B C / / D y y y / xx x xYukarıdaki ağaçta gösterilen dört farklı durumda y-x ilişkisi, soruda verilen ata-çocuk (parent child) ilişkisini sağlamakta ve yine x için soruda verilen yaprak düğüm şartı (leaf node) sağlanmaktadır.
Gelelim ispattan önceki son yorumumuza. Yukarıdaki örnek ağaç için, x ile y arasında bir değer ağaca girilirse (dört durum için de ayrı ayrı düşünülebilir), x düğümü artık yaprak düğüm olmaktan çıkar çünkü bu yeni değer x’in altına yerleştirilir. O halde yukarıdaki ağaçta gösterilen bütün durumlar için x-y ilişkisi ata-çocuk ilişkisi olmak ve x’te yaprak düğüm olmak şartıyla x ile y arasında başka sayı yoktur diyebiliriz.
Yorumun en başında yazıdığım üzere, iki durum bulunuyordu:
durumlarının ilkinde y, x’ten küçük olmak zorundayken ikincisinde y, x’ten büyük olmak zorundadır.
şimdi bu iki ihtimal ile bir önceki adımda bulduğumuz “y ile x arasında başka sayı yoktur” gerçeğini birleştirirsek:
y, x’ten küçüktür ve y ile x arasında başka sayı yoktur
y, x’ten büyüktür ve y ile x arasında başka sayı yoktur
iki ihtimali okuduğumuzda, ispatlanması istenen duruma ulaşmış oluruz ve
y, x’ten büyük en küçük sayıdır çünkü x, y’nin sağında bir yaprak düğümdür , veya
y, x’ten küçük en büyük sayıdır çünkü x, y’nin solunda bir yaprak düğümdür.
Yorumu yapılabilir.
Yukarıdaki yorumu basit bir dille anlatmaya çalıştım ancak daha resmi bir dil (formal) kullanırsak aşağıdaki yorum yapılabilir:y şartı bulunur.x ve ix ve i>y ise, sağ(i,y) olacaktır ve ağaçtaki x y şartı vardır.
x, yaprak olmak üzere, sol(x,y) veya sağ(x,y) ihtimalleri için aralarında simetri olmasının yanında; sol(x,y) için x
i, herhangi bir sayı olmak şartıyla sol(x,y) ihtimali için aşağıdaki durumlar geçerlidir:
i
Yukarıdaki 3 ihtimal ağacın bütün sol(x,y) şartı taşıyan düğümleri için doğrudur ve sağ(x,y) şartı için yukarıdaki 3 ihtimalin simetrisi geçerlidir.
Başarılar
mrb hocam;
1)Suppose that we have numbers between 1 and 100 in a Binary Search Tree, and want to search for the number 68. Which of the following sequences could not be sequence of node examined?
a)50,70,65,67,68
b)30,70,65,58,68
yukardaki sorunun aynısı sanırım ama doğru yaptığımdan emin olamadım.bu soruyu da açıklayabilirmisiniz rica etsem?
2)- Draw Binary Search Tree of height 4 on the set of keys
{2,4,6,8,10,12}
a)which key is a minimum on BINARY-SEARCH-TREE
b)which key is a maximum on BINARY-SEARCH-TREE
bu da 2. sorum hocam kolay ama konuya hakim olmadığım için sormak istedim.
teşekkür ederim.
1. sorunuzda sizden istenen aslında BST’yi doğru anlamış mısınız bunu görmek. Şimdi ilk aranan sayı 50 ve sayımız 68 ise sağa bakılacak (daha büyük bir sayı) ve sonra 70 ise sola bakılacak (daha küçük bir sayı çünkü 68 < 70). Bu mantıkla devam edersek b şıkkındaki 65'den sonra 58 gelmesi durumu hatadır çünkü 65'den büyük bir sayı aranırken 65'in sağına bakılması gerekirken 68'in sağında olamayacak bir sayı olan 58'e bakılması mümkün değildir (böyle bir sayı BST üzerinde yanlış konuma yerleştirilmiş dolayısıyla bu ağaç BST değildir denebilir). Gelelim ikinci sorunuza. Verilen sayıları sırasıyla BST'ye yerleştirelim:
2 \ 4 \ 6 \ 8 \ 10 \ 12 görüldüğü üzere bir BST oluştu ancak sorudaki şart yüksekliğin 4 olması gerektiğiydi, bizim ise yükseklik 5. Nasıl çözebiliriz? Çözüm olarak bir yerde dengeleme yaparsak seviye bir azalır. Örnek olarak 8 – 10 -12 diziliminde 10 yukarı 8, sola ve 12 sağa konabilir:2 \ 4 \ 6 \ 10 / \ 8 12Veya dengeleme herhangi başka bir noktada da yapılabilir. Örneğin 4 yukarı alınıp 2 sola geri kalan bütün ağaç ise sağa konabilir.
Ağaç oluştuktan sonra nereden dengeleme yaptığınız hiç önemli olmaksızın iki şıkkında cevabı hep aynıdır. BST için en küçük hep 2 en büyük hep 12 çıkacaktır.
Başarılar
merhabalar;
birinci sorunuz aynı mantıkta ancak verdiğiniz şıklardan ilki olabilir. ikincisi olamaz. (şayet ben hata yapmıyorsam)
2. sorunuz için, soruda 4 derinliğinde bir bst çizmeniz istenmiş. Önce çizelim sonra cevaplandıralım:
4 derinliğinde olacağına göre ve sayılarımız sıralı verildiğine göre kök düğüm olarak 2 ihtimalden birini seçmek zorundayız.Ya 4’ü seçeriz ve 6,8,19,12 şeklinde giden yol 4 derinliğinde (yüksekliğinde, height) bir ağaç oluşturur
4 / 2 6 8 10 12ya da 10’u seçeriz ve 8,6,4,2 şeklinde bir kolumuz olur:
10 / 8 12 / 6 / 4 / 2bu sayılarla iki ihtimal dışında 2 ve 12 ‘nin de kök olma durumu bulunur.
2 4 6 8 / 10 12Görüldüğü üzere, 2’nin kök olması halinde 12 dışındaki düğümlerden bir tanesinin iki çocuğu bulunması ve diğerlerinin tek çocuğu olması yeterli olur.
Aynı durum 12’nin kök olması halinde de geçerlidir.
Sanıyorum bunlardan bir tanesini çizmeniz soru açısında yeterli olacaktır. Sadece BST daha iyi anlaşılsın diye bütün ihtimalleri göstermek istedim.
Gelelim sorunuza, BST üzerinde asgari sayı bulunurken (minimum) sürekli sola gidilir. Sola gidilemeyen noktada durulur ve bulunan sayı minimum ilan edilir.
Yukarıdaki ağaçlar için,
4 kök olduğu durumda en solda 2 bulunur
10 kök olduğu durumda, en solda 2 bulunur.
2 kök olduğu durumda, en solda kökün kendisi yani 2 bulunur.
Bunun dışında çizilebilecek bütün ağaçlar için de durum aynıdır.
Azami değer için (maximum) algoritma tersten çalışır. Gidilebilecek en sağdaki değere gidilir. Daha sağda düğüm olmayınca durulur. Yukarıdaki bütün durumlar bu koşulu sağlar.
Örneğin biraz daha karıştırmak için yine yukarıdaki sayılardan üretilen ve 4 derinliğindeki aşağıdaki ağacı ele alalım:
2 4 8 / 6 12 / 10Yukarıdaki ağaç bir ikili arama ağacı özelliği taşımaktadır. Sorumuza dönüp azami değeri ararsak (maximum) ağacın gidilebildiği kadar sağına gideceğiz ve gidemediğimiz noktada duracağız.
2’nin sağında 4
4’ün sağında 8
8’in sağında 12
12’nin sağında ise null (boşluk) var burada duruyoruz ve 12 en büyük sayıdır diyoruz.
başarılar
iterative tree search hakkında tutorial var mı acaba?şöyle bi soru var da:
50 / a) Use ITERATIVE-TREE-SEARCH algorithm .How many times the while loop executed 40 60 / / to find the node 56. 35 45 56 70aynı ağaç için şu sorular da var cevaplayabilirseniz.
b)Insert number 47 into a binary search tree show the step by step.
c)Delete number 40 from binary search tree.
şekil için özür dilerim kopy paste yapmaya çalıştım fakat hatalı olmuş sanırım. root 50. sağında 60 var. 60 ın sağında 70,solunda 56. 50 nin solunda 40. 40 ın sağında 45,solunda 35 var.anlatmaya çalıştım ama oldu sanırım:)
Iterative tree search algoritması, ağacın döngü ile arandığı algoritmadır. Basitçe bir döngü içerisinde bütün düğümler dolaşılır.
Sorunuzda verilen örnek ağaç için 56 sayısını bulurken bu döngünün kaç kere döndüğü sorulmuştur.
Anlaşılması için öncelikle bu algoritmanın döngüsünü yazalım:
a = aranan anahtar i = kök düğüm while( i != NULL){ if(i==a) bulundu else if( i < a ) i=i.sağ else i=i.sol }Yukarıdaki döngüde basitçe bir gösterici (iterator) ağaç üzerinde hareket etmekte ve aranan değere göre ağaçtaki düğümde sola veya sağa yönelmektedir.
Sorunuz için 56 sayısı, aranırken döngü öncelikle kökten başlayacak ve birinci dönüşten sonra 50 < 56 olduğu için ilk dönüşten sonra i = 60 olacaktır. ikinci dönüşte 56 < 60 olduğu için ağacın soluna yönlenecek ve nihayet aranan sayıyı bulacaktır. Bu durumda arama algoritmamızdaki while döngüsü 2 kere dönmüş olacaktır. b şıkkına gelince 47 sayısının eklenmesi sırasında önce 50'nin soluna sonra 40'ın sağına ve sonra 45'in sağına gidilerek bulunan NULL değere ekleme işlemi yapılır ve ağaç aşağıdaki hali alır:
50 / 40 60 / / 35 45 56 70 47c şıkkında 40 sayısının silinmesi sorulmuş. Ağaçtan silme işlemi yapılırken, silinen değer yaprak düğüm ise (leaf node) doğrudan silinir ancak bunun dışındaki düğümler silinirken sağdakilerin en küçüğü (min of right) veya soldakilerin en büyüğü (max of left) ile yer değiştirilir.
iki yöntemde doğrudur ve örneğin sizin sorunuz için biz soldakilerin en büyüğünü getirmek isteyelim:
50 / 35 60 / 45 56 70 47Şeklinde silinmiş olur.
hocam bu silme işlemini javada nasıl yazabiliriz ?
mrb şadi hocam benim odevim var c de agac yapısıyla ilgili ben gerceklemeye calıstım ama gercekleyemedim yardımcı olursanız sevinirim
oncelikle odevde bana verilen
typedef struct _Dugum { char *kelime; struct _Dugum *sol; /* sol cocuk */ struct _Dugum *sag; /* sag cocuk */ } Dugum; Dugum *kok;Ağaç yapısı programlama yapılarında sıklıkla kullanılan soyut veri türlerindendir (SVT). İkil
ağaç maksimum iki çocuğu olan özel ağaçtır. Ağaç ise özyineli bir tarifle verilir: “ağacın her bir
düğümü, kökü ve/veya sol/sağ çocuklu ağaçtır”. Yani her bir düğümde bir değer (burada “kelime”),
sol ve sağında başka bir ağaç uzanır. Bu amaçla ağaçtaki her bir düğümü temsilen Dugum SVT
verilmiştir. Buna göre,
ve benden istenenler ise
1)/* dugum_ekle: hangi çocuk bossa o tarafa dugum ekler. Her ikisi
de doluysa hata verir. */
Dugum dugum_ekle(Dugum *d, char *k) {
}
2)/* dugum_yazdir: d dugum listesini sirali bir sekilde yazdir. *
*
Ozyineli olarak once sol, sonra dugum degeri, en son sag */
void dugum_yazdir(Dugum d) {
}
1 ve 2 yi gerceklemem gerekiyor hocam yardımcı olursanız cok sevinirim
Aşağıda müsvette bir şekilde kodları veriyorum. Çalıştırıp deneme şansım olmadı ancak sanırım fikir verir:
Dugum * dugum_ekle(Dugum *d, char *k) { if(d == NULL) return (Dugum *)malloc(sizeof(Dugum)); if(strcmp(k,d->kelime)>0){ d->sol = dugum_ekle(d->sol,k); return d; } else{ d->sag = dugum_ekle(d->sag,k); return d; } } void dugum_yazdir ( Dugum d){ if(d == NULL) return; dugum_yazdir(d.sol); printf(" %s", d.kelime); dugum_yazdir(d.sağ); }Sanırım yukarıdaki kodlamalarda hata yoktur. Açıkçası ikinci fonksiyon için Dugum *d şeklinde parametre almayı tercih ederdim ancak sorunuzu bu şekilde sorduğunuz için soruya benzer prototipte kodladım.
Ayrıca daha önce verdiğim veri yapıları dersinde benzer çok sayıda kodu yazıp yayınlamıştım:
http://www.sadievrenseker.com/vy/
Adresindeki 8. hafta koduna ve
http://www.sadievrenseker.com/datastr2009/
Adresindeki 8 ve 9. hafta kodlarına bakmanızda yarar var.
Başarılar
mrb hocam kodda bu kısmı anlayamadım
if(strcmp(k,d->kelime)>0)
birde hocam dugum_ekle: hangi çocuk bossa o tarafa dugum ekler. Her ikisi
de doluysa hata verir. */
yazdıgınız kodda bu sartı gercekleyen kısım neresi
Sorunuzun cevabı zaten sitede bulunuyor:
http://www.bilgisayarkavramlari.com/2008/12/27/dizgi-karsilastirma-string-comparison/
ikinci sorunuzun cevabı ise ilgili yorumda yazılan fonksiyonun kendisidir ve fonksiyonun ismi dugum_ekle olarak geçmiştir.
Başarılar
hata verdiği kısmı soracaktım onu asagıdaki sekilde oldugu gibi return ifadesini bos donerek sagladınız heralde
if(d == NULL)
return;
Hocam selamlar.Yukarda dugum ekle,ara,yazdir kodlarına örnekler yazmışsınız ya, bizim hocamız da ikili arama ağacıyla bunlardan ayrı olarak güncelleme,kopyalama,sıralı kopyalama,birleştir(kopyalananla,ana kodu) gibi kodlamalar istiyor.Bunları nasıl yazacağım hakkında bilgim yok.kısaca anlayacağım şekilde bu kodlara örnekler yazabilir misiniz.
1- Aşağıdaki özellikleri sağlayan bir “liste” veri yapısını programlayarak gerçekleyiniz:
a. Liste elemanlarının her biri aşağıdaki bileşenlere sahip olan öğrenci kayıtlarıdır. Öğrenci kayıtlarını birbirlerinden ayırt eden tek bileşen öğrenci numarasıdır.
– Ad
– Soyad
– Fakülte
– Bölüm
– Numara
– GNO (genel not ortalaması)
– İkametgah İli
b. Öğrenci kayıtları listesi, “İkili Arama Ağacı” (Binary Search Tree) modeli ve dinamik bellek ayırımı kullanılarak gerçeklenecektir.
c. Veri yapısı aşağıdaki işlemleri sağlayacaktır.
– L oluştur()
– L ekle(L, e)
– e ara(L, e) (bir kayıdı öğrenci numarası ile ara)
– L çıkar(L, e) (çıkarılacak kayıt öğrenci numarası ile aranacak)
– L güncelle(L, e)
– L’ kopya(L) (listenin yeni bir tıpkı kopyası dönülür)
– L’ sıralıKopya(L) (listenin sıralı ve yeni bir kopyası dönülür)
– L birleştir(L1, L2)
– yazdır(L)
– L boşalt(L)
Yardımcı olursanız sevinirim…
Hocanızın ikili arama ağacı için bunları istediğinden emin misiniz? Sanki bağlı liste (linked list) gibi duruyor. Örneğin sıralıKopya için listenin sıralı ve yeni bir kopyası döndürülür demişsiniz. Ayrıca ikili arama ağacında zaten sıralama gibi bir işlem yapılmaz sadece dolaşırken sıralanmış olunur.
Yine de ikili arama ağacı olduğuna eminseniz aşağıdaki bağlantıda bulunan kodlar işinize yarayabilir. Örneğin iki adet ağacı alıp toplayan koddan esinlenebilirsiniz. Sanırım yukarıdaki kodların tamamına yakını bu adreste çeşitli kodlar altında bulunuyor.
http://www.sadievrenseker.com/datastr/
Başarılar
Hocam oldukça geç gördüm cevabınızı…
Şöyle ki bizim ilk proje ödevimiz BAĞLI LİSTEyle ögrenci kayıtları listesi hazırlayıp,istenenleri yapmaktı.2.projemiz ise İKİLİ ARAMA AĞACIyla öğrenci kayıtları listesini yapmaktı.Ve bu iki ödevde de istenen işlemler aynıydı…Ben ödevi yarım yapabildim:(
Hocam siteniz çok verimli ve de dolu dolu.Özellikle de görsel anlatımlı dersler çok iyi.Vizelerde sıralama algoritmalarından yararlandım,finale de kruskal,prim,dijkstra…dan inş:)) Maşallah.Allah gayretinizi artırsın.Emeğinize sağlık.Çok teşekkürler…
bana yardım edebilirmisiniz ödevim ağaçta dolaşım algoritmaları bunun c kodu lazım bana
ihtiyacınız olan algoritmaları yazarsanız yardımcı olmaya çalışayım. ağacın tipine ve dolaşma şekline göre çok sayıda algoritma bulunuyor. tam olarak nasıl bir algoritmaya ihtiyacınız var? Bir de bu algoritmalardan bir kısmı zaten bu yazıda ve yorumlarda bulunuyor, bunlar işnize yaramıyor mu?
Başarılar
Merhaba Hocam,
Benim veri yapıları proje ödevim de ikili arama ağacının hem dizilerle, hem de bağlantılı liste kullanarak gerçeklemek.
Programların bütün bilgileri “data.txt” isimli dosyadan okunması gerekiyor.
İlgili Kodlar;
Diziyle gerçekleme:
struct Node { float Latitude; float Longitude; float Magnitude; char Region[60]; }; enum ETraverse {PREORDER=1, INORDER, POSTORDER}; // 1,2,3 olarak kodlanmış enum EAttribute {LATITUDE=1, LONGITUDE, MAGNITUDE}; //1,2,3 olarak kodlanmış #define N 500 struct Tree { int root; // Kökün indeksi Node array[N]; char filename[30]; FILE *datafile; void read_tree_from_file(); void additem(Node newitem); void deleteitem(char * region); void traverse(int root, ETraverse TraverseCode); // Ağaçtaki bütün düğümleri göster // Aşağıdakiler bulunan düğümün indeksini döndürür. int findRegion(char * region); int findMin(EAttribute AttributeCode); int findMax(EAttribute AttributeCode); int size(); // ağaçtaki düğüm sayısını verir int count_leaves(); // ağaçtaki sadece yaprak olan düğümlerin sayısını verir int depth(); // ağacın derinliğini hesaplar float AvgMagnitude(); // büyüklüklerin ortalamasını hesaplar }; Bağlı liste yapısıyla gerçekleme; struct Node { float Latitude; float Longitude; float Magnitude; char Region[60]; Node *left; Node *right; }; enum ETraverse {PREORDER=1, INORDER, POSTORDER}; //1,2,3 olarak kodlanmış enum EAttribute {LATITUDE=1, LONGITUDE, MAGNITUDE}; //1,2,3 olarak kodlanmış struct Tree { Node *root; char filename[30]; FILE *datafile; void read_tree_from_file(); void remove_tree_from_memory(Node * root); void addItem(Node * newitem); void deleteItem(char * region); void traverse(Node * root, ETraverse TraverseCode); // Ağaçtaki bütün düğümleri göster // Aşağıdakiler bulunan düğüme işaret eden bir işaretçi döndürür. Node * findRegion(char * region); Node * findMin(EAttribute AttributeCode); Node * findMax(EAttribute AttributeCode); int size(); // ağaçtaki düğüm sayısını verir int count_leaves(); // ağaçtaki sadece yaprak olan düğümlerin sayısını verir int depth(); // ağacın derinliğini hesaplar float AvgMagnitude(); // büyüklüklerin ortalamasını hesaplar };Sorunuzu tam olarak anlayamadım. Şayet ikili arama ağacını bir dizi üzerinde kullanmak istiyorsanız. Yani ağacı gösterici (pointer) kullanmadan doğrudan dizide tutmak istiyorsanız aşağıdaki yazı yardımcı olacaktır:
http://www.bilgisayarkavramlari.com/2008/08/09/dizi-uzerinde-agac-kodlamasi/
Kodunuzda diziyle geçrekleme yorumu yaptığınız satırdan itibaren olan satırlarda sanırım önce bir ikili arama ağacı kodlamaya çalışmış, ardından da bu ağacı diziye taşımışsınız.
Buradaki fonksiyonlarınızın sadece prototipleri bulunuyor. Sanırım bunları kodlamanız gerekiyor. Bu durumda yukarıdaki yazıyı okuyarak bir deneme yapın. Kritik nokta ikili arama ağacını dizide tuttuğunuzda sol ve sağ düğümlerin aşağıdaki şekilde bir formül ile hesaplanıyor oluşudur:
sol = düğüm *2 +1
sağ = (düğüm+1) *2
Yukarıda düğüm sayısının 0’dan başladığı kabulü yapılmıştır. Yani sizin kodunuzdaki kök değişkeni her zaman 0 olacaktır.
Gelelim bağlı liste (linked list) uygulamasına. İşte bunu bir ağacı tutmak için nasıl kullanabiliriz hiçbir fikrim yok. Yani bağlı liste zaten yapı olarak sonraki elemanları tutan doğrusal erişime sahiptir. Bu yapıda dizi gibi düşünerek belirli sayılardaki karşılıklara eleman eklemek mümkün değildir çünkü bağlı listede elemanların indisi olmaz, araya elemanlar eklenip silinebilir. Öte yandan bağlı listedeki pointer yapısı da ağacı tutmak için uygun değildir çünkü ağaçta her düğümün iki çocuğu varken bağlı listede tek çocuğu vardır. Dolayısıyla burada bir hayal sorunumuz var. Şayet bir ikili ağacın bağlı listede tutulması ile tam olarak neyi kast ettiğinizi anlayabilirsem yardımcı olabilirim.
Kodlama ile ilgili konuya gelince yukarıda bağlantısını verdiğim yazıyı okuyun. Kodlamayı deneyin, şayet sorun yaşarsanız tekrar yazın fonksiyonlardan bir iki tanesini kodlayarak yol gösterebilirim.
Başarılar
Dizide kodlamada verilerimizi bell bir dosyadan okumamız istendiği için a[3] gibi belli bir sıraya koymam mümkün değil. Bahsettiğim txt dosyasını size gönderdim.
Bakabilirseniz sevinirim
hocam benim iki soru var cevaplar mısınız ?
1.si : oluşturulmuş bir ikili ağacın manx ve min derinliklerinin bulan bir c programı yazınız
2.si: Verilen bir ağacın sağ ve sol kollarının sayısını ayrı ayrı bulan bir alt program yazınız
AVL ağaçları yapısı itibariyle zaten her düğümün derinlik bilgisini tutar:
http://bilgisayarkavramlari.sadievrenseker.com/2008/05/15/avl-agaci-avl-tree/
bağlantılı olarak dengeleme işlemi için şu yazı faydalı olabilir:
http://www.bilgisayarkavramlari.com/2008/05/15/agaclarda-dengeleme-rotation-balancing/
Yine internal path için şu yazıya bakabilirsiniz:
http://bilgisayarkavramlari.sadievrenseker.com/2009/12/03/internal-path-reduction-trees-ic-yol-indirgeme-agaclari/
Sorunuzun tam cevabına gelince her çocuk için 1 arttıran ve dolayısıyla leaf ulaştığında duran bir kod yazmak gerekiyor ve kabaca aşağıdaki şekilde yazılabilir (geç bir saatte yorgun bir şekilde yazıyorum hata olması yüksek ihtimal):
int maxderinlik (node *r){ if(r == null) // leaf (yaprak) düğümün çocuğu 0 derinlikte return 0; int sag = maxderinlik(r->sag); int sol = minderinlik(r->sol); if(sag>sol) return sag+1; return sol+1; }Yukarıda max derinliği veren kodu yazdım, kabaca bir root verdiğinizde sol derinliğe ve sağ derinliğe bakıyor, bunlardan büyük olanın 1 fazlasını döndürüyor. Min de tam tersi olacak (büyüktür yerine küçüktür).
2. soruuzu ise ne yalan söyliyeyim anlamadım. Sağ ve solda tek bir kolu vardır (ikili ağaçsa) alt kollarını kastediyorsanız (Edge anlamında) o zaman internal path sayısına bakmanız gerek (bkz. yukarıda linkini verdiğim yazı), şayet sağ ve sol kolların derinliğini kastediyorsanız yazdığım kod yardımcı olacaktır.
Başarılar
Sabahtan beri ingilizce kaynaklardan anlamaya çalışıyordum.
Bu çok iyi oldu teşekkürler. 🙂
Bir metin dosyası içerisinde verilen sayıları ikili arama ağacına yerleştirip ekrana ağaç yapısını çizen bir C# programı geliştiriniz. veri yapıları ödevimdir yardım eder misiniz
ikili arama ağacını pointer kullanarak nasıl gerçekleştiririz yardım edebilirmisiniz?
Yukarıdaki kodlar zaten pointer kullanılarak yazılmış kodlardır. Tam olarak istediğiniz nedir?
İkili arama ağacında (binary search tree), verilen bir key değerinden bir küçük sayının ne olduğunu bulmak istiyoruz. Bu sayıya “predecessor” denmektedir. Bu işlem nasıl yapılır? yalancı kod yada anlatım ile?***
Bakın LNR ile ağacı dolaşırken sayılar küçükten büyüğe sıralıdır ancak RNL ile dolaşırken tam tersi. Sizin istediğiniz durum şu şekilde, RNL ile dolaşırken bir sayı bulunduktan sonra sayı bulundu şeklinde dönmeyecek bir adım daha ileriye gidecek. Aşağıdaki yazı faydalı olabilir:
http://bilgisayarkavramlari.sadievrenseker.com/2010/12/29/order-theory-sira-teorisi-nazariyatul-tertib/
Kabaca kodlamayı da özyineli (recursive) olarak şöyle yapabilirsiniz:
int ara(node * r, int a, int s){ if(ara (r->right,a,s)==1){ printf("bulunan sayı : %d",r->veri); s= 0; } if( s == 1) return r->veri; if(r->veri == a) s= 1; if( ara (r->left,a,s)==1){ printf("bulunan sayı : %d",r->veri); s=0; } return s; }kabaca RNL ile ağacı dolaşırken aranan sayıyı bulduğu anda s değerini 1 yapıyor bu sayede bir sonraki eleman ekrana basılıyor.
Kodu yazdım, deneme fırsatım olmadı ama sanırım çalışır. Zaten sanırım sizin istediğiniz de biraz fikir vermesiydi. Belki bazı durumlarda hata olabilir bir bakmak gerek.
Başarılar.
Hocam iyi günler benim ödevim ikili arama ağacında kişi bilgileri string nasıl kullancam kodlarınızı inceledim anlayamadım kişilere ait bilgiler nasıl ekliycem ağaca acaba yardımcı olur musunuz?
C++ programlama dili ile yazacağınız program İkili Arama Ağacı ve Tek Yönlü Bağlı Liste veri yapısı kullanmalıdır. İkili Arama Ağacı veri yapısının içerisinde Bağlı liste veri yapısı bulunmaktadır. Program çalıştığında bir txt dosyasından verileri almalıdır. Örnek txt dosyası aşağıda verilmiştir. Txt dosyasından alınan ilk satırdaki boşluğa kadar olan kısım ağacın verisini boşluktan sonraki kısım ise ağacın içindeki listenin verisini belirtmektedir. Okunan her bir satırda eğer ağaçta ilgili düğüm yoksa ağaç düğümü oluşturulmalıdır ve liste verisi eklenmelidir, eğer ilgili ağaç düğümü varsa ilgili düğümün sadece liste verisi listenin sonuna eklenmelidir. Düğümler oluştuktan sonra oluşan ağaç inorder, preorder ve postorder şeklinde ekrana yazılmalıdır. Yazdırılma işleminde her düğüm ekrana yazdırılacağı sırada düğümün içerisinde barındırılan liste baştan sona kadar ekrana yazdırılmalıdır.
Dosya Formatı
Anakartlar AMD
Bellekler DDR3L
Bellekler DDRE4
Islemciler AMD
Bellekler DDR2
Anakartlar Intel
Bellekler DDR3
Islemciler Intel
***
Inorder Yazım
Anakartlar
AMD Intel
Bellekler
DDR3L DDR4 DDR DDR2 DDR3
Islemciler
AMD Intel
****
Merhba hocam böyle bir ödevi vvar ödev sınıflarımı oluşturup dosyanın ilk satırdaki leri alıp agacıma ekliyorum fakat 2. satrdaki değerleri o agacın içinde baglı listeye nasıl ekliyceğimi bulamadım bi türlü her agac verisi için nasıl ayrı bir baglı liste çağırcaz
boşluğa kadar okutma işlemini nasıl yaptın paylaşırmısın bende kendı projemde takıldıgım noktayı duzeltıyım
hocam ikili arama ağacında gelen bir çok soru için algoritmayı nasıl kurmalıyız,?
örnek javada ağacın yüksekliğini döndüren kodu veya yaprak düğümlerin toplamını bulan kod?denilse tekrardan kolay gelsin iyi günler…
19,9,15,21,6,36,8,5 inordera göre ağaca nasıl yerleştiririz Hocam
Merhabalar Hocam,
İkili Arama Ağacının simetrik olup olmadığını bulan kök düğümü kok değişkeninde tutulan Simetrik(Agaclar *kok) fonksiyonuna ihtiyacım var.Görsel olarak tanımlamam gerekirse;
9 9
/ \ / \
5 13 5 13
\ / / /
6 12 2 12
SİMETRİK SİMETRİK DEĞİL
typedef struct Agac{
int no;
struct Agac *sol,*sag;
}Agaclar;
Şimdiden teşekkür ederim.
hocam veri yapıları finalinde şu soruyla karşılaştım net bi çözüme hala ulaşamadım.
soru şu:Bir ağaç yapısı tanımlı structın içinde ekstra kök seviyesi tanımlanmış.
atıyorum ilk kökün seviyesi 0,bi tık aşağı kollara inince 1 oluyor ve bizden o kök seviyesindeki sayıların toplanmasını istiyor.ne kadar açıklayıcı oldu bilemiyorum ama yardımcı olursanız sevinirim ..
merhaba hacam .ikili ağaçlarda ortalama değeri hesaplayan ağaç dolaşma yöntemleri nasıl olur yardımcı olursanız sevinirim