Bilgisayar biliminin en cok hasir nesir oldugu yapi budur.
Cok soyut anlamda bilgisayar bilimini, agac cizgelerin calisilmasi olarak tanimlayabiliriz.
Bu cevapta agaclarin kullanimina cesitli ornekler vermek istiyorum
Trie
Trie, hafizada belli bir alfabeden gelen sozcukleri saklamak ve aramak icin kullanilan bir veri yapisi.
Kullanacagimiz alfabedeki sembol sayisi $n$ ise, Trie yapisi bir $n$-agac.
Bu yapiya yeni bir sozcuk eklemek, sozcugun harflerini indeks olarak kullanip agacta ilerlemek ve eger o harf cocuk olarak eklenmemisse yeni bir cocuk yaratmaktan ibaret. Sozcugun son harfi icin son eklenen cocugu boyamak gerekiyor ki sozcuk bitislerini ayirt edebilelim. Bu operasyon eklenen sozcugun harf sayisi ile dogru orantili.
Bir sozcugun Triede olup olmadigina bakmak icin gene sozcugun harfleri indeks olarak kullanilir ve son harfin boyanip boyanmadigina bakilir. Bu operasyon gene sozcugun harf sayisi ile dogru orantili.
Trie yapisi sayesine cok hizli bir sekilde(ne kadar hizli) $x$ sozcugu ile baslayan butun sozcukleri bulabiliriz
Huffman Agaclari (Huffman Tree)
Huffman agaclari, bir alfabeden ve alfabadeki sozcuklerin kullanilma sikligindan , optimal ve prefixi olmayan bir kod sozcugu yaratir.
Yukaridaki cumle cok karisik oldu ne demek biraz parcalara bolelim.
Elimizde bir alfabe olsun ornegin Turkce. Turkcede 29 tane harf var.
Turkce alfabesini naiv bir sekilde 5 bit ile ifade edebiliriz . Simdi bize $n$ uzunlugunda sozcuk verilmis olsun. Bu sozcugu yazmak icin $5n$ bit kullanmam gerekiyor. Daha iyisini yapabilir miyiz? Ornegin Turkcede "e" harfi cok kullaniliyor, Eger "e" harfini daha az bitle ifade edersek hafiza kullanimimizi azaltabiliriz."e" harfine mesela bir bit atayalim ve 0 ile ifade edelim. Onemli bir nokta alfabamizden olusturdugumuz kod sozcuklerinin baslangiclarinin farkli olmasi. Eger ayni olurlarsa arka arkaya yazdigimizda karistiririz.
Huffman algoritmasi, en az kullanilan iki tane sembolu alip bir agac yaratiyor ve bu agacin kullanilma sikligini cocuklarinin sikliginin toplami olarak kaydediyor. Bu islem elimizde tek bir tane ikili agac kalana kadar devam ediyor. Agacin yapraklarinda semboller var. Sembole denk gelen kod sozcugunu bulmak icin kokten baslayin, Saga giderseniz "0", sola giderseniz "1" yazin. Yapraklara vardiginizda elinize gecen dizi kod sozcugunuz.
Huffman algoritmasi yukarida anlattigim mantik ile calisiyor. Kayipsiz ve kendi klasinda optimal bir sikistirma algoritmasi.
Soyut Sozdizimi Agaclari (Abstract Syntax Tree)
Bilgisayar dillerinde yazilan kodlar, dilin derleyicisi (compiler)/cevirmeni (interpretter) tarafindan dilin sozdizimine gore bir agaca donusturulur. Bu agaca Soyut Sozdizimi agaci diyoruz. Derleyicinin/cevirmenin anladigi ve uzerinde calistigi yapi budur.
Genel olarak derleyicinin/cevirmenin isi , ""bu" agaci gorursem "sunu" yapmaliyim " a indirgenebilir. Bir baska degisle bu programlar cizgeleri girdi olarak alip yeni cizgeler yaratirlar.
Derleyici ve cevirmenler cizge teoresi ile ic icedir.
Karar Agaclari (Decision Trees)
Bu agaclar yapay zeka uygulamalarinda kullaniliyor. Bir veri setindeki verileri, belli evet hayir sorularin kullanarak sinifliyoruz. Huffman agaci gibi bu da rastsal bir algoritma. Temel olarak aradigimiz agac ,her mertebede (level?) bilgi kazanimini (information gain) minimize eden agac. Daha fazla yazmak isterdim ama machine/statistical learning fobim yuzunden ancak bu kadarina tahammul edebiliyorum.
Arama Agaclara (Search Trees)
Bu veri tipi kume.sirali liste, oncelikli kuyruk gibi bircok yapiyi yaratmak icin kullanilabilir.
Bunlarin bir cok cesiti var (avl tree, red-black tree etc.) ama temel mantik su:
Aradigimiz deger, Agacin koku ile karsilastirilir:
Esit ise degeri buldunuz tebrikler.
Kucuk ise agacin sol cocuguna bakin,
Buyuk ise agacin sag cocuguna bakin
Kok yok ise deger agaca eklenmemis.
Agaci kurarken de bu mantigi kullaniyoruz. Dikkat edilmesi gereken onemli bir nokta, arama algoritmasinin agacin boyu ile baglantili olmasi. Bu nedenle yeni degerler eklerken agaci yeniden dengelemek daha iyi performans saglar
Aklima gelen ilk agaclarin kullanimina verebilecegim ornekleri bunlardi ama liste kesinlikle bunlarla sinirli degil . Biraz ustunkoru oldu ama idare edin