Binary Search Tree Nedir? Binary Search Tree, veri yapıları arasında sık kullanılan bir yöntemdir Elemanları karşılaştırmak ve sıralamak için kullanılır Tree yapısı ile hızlı bir şekilde arama ve ekleme işlemleri yapılabilir Detaylar için tıklayın!
Binary search tree, veri yapılarından biridir ve birçok programlama dilinde kullanılmaktadır. Bu yapının temelindeki mantık, sıralı bir şekilde yapılandırılmış elemanlara hızlı bir şekilde erişim sağlamasına dayanmaktadır. Bu yapı, kök düğüm, sol alt ağaç ve sağ alt ağaç gibi birçok düğümün yapısını içerir.
Binary search tree yapısı, her bir düğümün en fazla iki alt düğüme sahip olması ve her sol alt ağacın, ebeveyn düğümündeki değerden küçük, sağ alt ağaçların ise büyük olduğu bir sıralama düzeni izler. Bu sebeple binary search tree yapısı, özellikle arama, ekleme ve silme işlemleri gibi veri yapılarına yönelik sorgulama işlemleri yapıldığında oldukça hızlı sonuçlar verir.
Binary Search Tree Özellikleri
Binary search tree, verileri tutmak için kullanılan en yaygın veri yapılarından biridir. Binary search tree yapısı, bir kök düğümden başlar ve her düğüm, kendinden küçük olanların solunda ve kendinden büyük olanların sağında yerleştirilir. Binary search tree özellikleri şunlardır:
- Her düğüm en fazla iki çocuğa sahip olabilir.
- Sol alt ağaçtaki tüm düğümlerin değeri, üst yani ana düğümünden küçük olmalıdır.
- Sağ alt ağaçtaki tüm düğümlerin değeri, üst yani ana düğümünden büyük olmalıdır.
- Binary search tree yapısı, hızlı bir şekilde arama işlemini gerçekleştirebilir.
Binary search tree yapısının avantajlarından biri, ağaç yapısının yönlendirilmesidir. Bu nedenle, bireysel düğümlere erişmek kolaydır ve hızlı bir şekilde arama işlemleri gerçekleştirilebilir. Binary search tree ayrıca, elemanların eklenmesi ve çıkarılması gibi değişiklikler yapmak için de ideal bir yapıdır.
| Avantajlar | Dezavantajlar |
|---|---|
| Eleman ekleme ve silme işlemleri hızlı ve kolaydır. | Yapı, elemanları düzgün bir şekilde yerleştirmedeki beceriye bağlıdır. |
| Arama işlemleri hızlıdır ve birleşik olaylar için uygundur. | Yapının dengeli bir şekilde tutulması gerekiyor, aksi halde karmaşıklık artar. |
| Tutulan verilerin ayrıştırması kolaydır. | Yapının düğümlerinde oluşabilecek arızalar veri kaybına neden olabilir. |
Depth-First Traversal Yöntemleri
Binary search tree yapısında yer alan depth-first traversal yöntemleri; pre-order, in-order ve post-order olarak üçe ayrılır. Bu yöntemler ağaç yapısındaki elemanların gezilirken hangi sırayla ziyaret edileceğini belirler.
Pre-order traversal yöntemi, bir elemanın sol alt ağacının tamamı gezildikten sonra, sağ alt ağacının tamamına geçilerek işlemler yapılır. In-order traversal yöntemi ise, elemanlar sol alt ağaçtan başlayarak sırayla gezilir. En son sol alt ağaç gezildikten sonra, ana elemandan sağa doğru devam edilerek elemanlar gezilir. Post-order traversal yöntemi ise, önce sol sonra sağ alt ağaç gezilerek, daha sonra ana elemana geçilir.
Aşağıdaki tabloda, depth-first traversal yöntemlerinin gezilme sıraları ve işlevleri gösterilmiştir:
| Traversal Yöntemi | Gezilme Sırası | İşlevi |
|---|---|---|
| Pre-order Traversal | Önce ana eleman, sonra sol alt ağaç, en son sağ alt ağaç | Elemanların işlenmeden önce özellikle sıralı bir şekilde sıralanması için kullanılır. |
| In-order Traversal | Sol alt ağaç, ana eleman, sağ alt ağaç | Elemanların sıralı bir şekilde işlenmesi için kullanılır. |
| Post-order Traversal | Sol alt ağaç, sağ alt ağaç, ana eleman | Elemanların bir işlem sonucu işlemlerin her iki alt ağaçta çalıştırıldıktan sonra işlenmesi için kullanılır. |
Depth-first traversal yöntemleri, birçok programlama dili ve kullanım alanı için önemli bir yapıdır ve binary search tree yapısının işleyişinde büyük bir rol oynar.
Pre-order Traversal
Pre-order traversal, binary search tree yapısındaki elemanları kök, sol alt ağaç ve sağ alt ağaç sırası ile gezinir. Bu gezinme yöntemi, elemanları ekrana yazdırma veya arama işlemlerinde kullanılabilir.
Örneğin, aşağıdaki binary search tree yapısı düşünüldüğünde pre-order gezinme yöntemi şu sırayı takip eder: 50 - 30 - 20 - 40 - 80 - 60 - 90.
| Kök | Alt Ağaçlar |
|---|---|
| 50 |
|
Yukarıdaki örnekte, 50 değeri kök eleman olarak belirlenmiştir. Sol taraftaki alt ağaçta yer alan 30 değeri, bunun solunda yer alan 20 ve sağında yer alan 40 değerleriyle birlikte ekrana yazdırılır. Daha sonra sağ taraftaki alt ağaçta yer alan 80 değeri, üstüne eklenen 60 ve 90 değerleriyle birlikte ekrana yazdırılır.
Pre-order traversal yöntemi sayesinde binary search tree yapısındaki elemanların gezinme işlemleri daha hızlı ve pratik bir şekilde gerçekleştirilebilir.
In-order Traversal
In-order traversal, binary search tree yapısındaki elemanların sıralı şekilde listelenmesini sağlayan bir traversing yöntemidir. Bu yöntem, öncelikle sol alt ağaçtan başlayarak düğümlerin sıralı olarak listelenmesine izin verir. Sol alt ağaçtaki tüm düğümler işlendikten sonra, düğümler kendi değerlerine göre sıralı olarak listelenir. Daha sonra, sağ alt ağaç düğümleri de aynı şekilde işlenir ve son olarak en üst düğümlerin işleyicisi çağrılır. Bu işlem, tüm ağacın düğümlerini sıralı bir şekilde listeler.
In-order traversal yöntemi, binary search tree yapısındaki elemanların sıralı şekilde listelenmesinde yaygın olarak kullanılır. Bu yöntem, öncelikle ağaçta arama işleminin gerçekleştirilmesinde kullanılır. Ayrıca ağaçtaki elemanların sıralı bir şekilde listelenmesi gerektiğinde kullanılabilir.
Aşağıda, bir örnek kullanım senaryosu verilmiştir:
| Düğümler | In-order Traversal Listesi |
|---|---|
| A | |
| B | |
| C | |
| D | |
| E | |
| F |
Yukarıdaki tabloya göre, öncelikle 'A' düğümü listelenir. Daha sonra, 'B', 'C' ve 'D' düğümleri sırayla listelenir. En son olarak da 'E' ve 'F' düğümleri listelenir. Toplamda, in-order traversal liste şu şekilde olacaktır: 'A B C D E F'.
Post-order Traversal
Post-order traversal, binary search tree yapısında ağacın dal ve yapraklarında yer alan elemanların gezilmesinde kullanılan bir yöntemdir. Post-order traversal yöntemi ile öncelikle sol alt ağaç gezilir, ardından sağ alt ağaç gezilir ve son olarak kök eleman gezilir. Bu şekilde tüm ağaç gezilir ve elemanlar sırayla listelenir.
Post-order traversal yöntemi, birçok uygulamada kullanılan bir gezinme yöntemidir. Örneğin, bir binary search tree yapısında kökten başlayarak yapılan post-order traversal gezinmesi, ağacın alt kısımlarındaki verilere erişmek için kullanılabilir.
Aşağıda bir binary search tree yapısındaki elemanların post-order traversal gezinmesi yapılırken sırayla hangi elemanların gezildiği görülebilir.
| Eleman | Post-order Traversal Gezgini |
|---|---|
| 13 | |
| 5 | |
| 19 | |
| 3 | |
| 7 | |
| 17 | |
| 23 |
Yukarıdaki tabloya göre, post-order traversal, sırasıyla 3, 7, 5, 17, 23, 19, ve 13 elemanlarının gezilerek listelendiği bir yol izler. Sonuç olarak, post-order traversal yöntemi, binary search tree yapısı içerisindeki elemanlara ulaşmak için oldukça etkili bir yol sağlar.
Breadth-First Traversal Yöntemi
Breadth-First Traversal yöntemi, ağacın seviye seviye gezilmesine dayanır. Yukarıdan aşağıya doğru bir seviye gezinirken, her seviyede soldan sağa doğru gezinme işlemi yapar.
Breadth-First Traversal yöntemi, her bir seviyedeki düğümleri keşfetmek için geniş bir kuyruk kullanır. Her seviyede, sol’dan sağa doğru hareket edilir. İlk önce kök node seviye 0 olarak gezilir, sonra seviye 1, seviye 2 gibi ilerlenir.
Aşağıdaki şekilde genişlik öncelikli gezinme tekniği ile gezintinin nasıl ilerlediği görülebilir.
| 1. İterasyon | 2. İterasyon | 3. İterasyon | 4. İterasyon |
| 1 | 2 | 3 | 4 |
| / \ | / \ | / \ | / \ |
| 2 3 | 4 5 | 6 7 | 8 9 |
Yukarıdaki şekilde gösterildiği gibi, kök düğümden başlayarak her seviyedeki tüm düğümleri gezdik. Yeni bir seviyeye geçtikçe, her düğüm düğüm üzerindeki düğümlerin sihirbazlarını kuyruğa ekledik. Bu şekilde tüm elemanları tek tek ziyaret edebilir ve ağacı dolaşabiliriz.
Breadth-First Traversal yöntemi, genellikle belirli bir düğümü bulmak için kullanılır. Örneğin, belirli bir değerin ağaçta olup olmadığını sorgularken bu yöntemi kullanabilirsiniz. Bu yöntemin büyük ölçüde zaman karmaşıklığı O(n)’dir.
Örnek Kullanımlar
Binary Search Tree yapısı, verileri düzenli olarak depolamak ve hızlı bir şekilde erişim sağlamak amacıyla kullanılır. Bu yapı, sıralı verileri ele alır ve her düğümde büyük-küçük kontrolü yaparak verileri kaydeder. Örnek kullanımlarını incelediğimizde ise, binary search tree yapısı genellikle arama işlemi gerektiren uygulamalarda sıklıkla kullanılır.
Örneğin, bir sözlük uygulamasında binary search tree yapısı kullanarak, verilerin hızlı bir şekilde aranması sağlanabilir. Aynı şekilde, bir hesap defteri uygulamasında da yine binary search tree yapısı kullanılarak, hesapların düzenlenmesi ve hızlı bir şekilde erişilebilmesi sağlanabilir.
| Uygulama | Kullanım Alanı |
|---|---|
| Sözlük Uygulamaları | Verilerin hızlı bir şekilde aranması |
| Hesap Defteri Uygulamaları | Hesapların düzenlenmesi ve hızlı bir şekilde erişilebilmesi |
| İlaç Listesi Uygulamaları | İlaçların düzenli olarak kaydedilmesi ve hızlı bir şekilde erişilebilmesi |
- Binary search tree yapısı, düzgün bir şekilde uygulandığı takdirde, verilerin hızlı bir şekilde aranmasını sağlar.
- Bu yapı, özellikle sıralı verilerin depolanması gerektiği uygulamalarda oldukça başarılıdır.
- Binary search tree yapısı, daha karmaşık yapılardan daha hızlı çalışır ve daha az bellek kullanır.
Binary search tree yapısının uygulama alanları oldukça geniştir. Uygun bir biçimde kullanıldığı takdirde, veri erişim süreleri kısaltılabilir ve veri yönetimi daha verimli hale getirilebilir. Yukarıdaki örnekler de göstermektedir ki, binary search tree yapısı sadece programlama alanında değil, hayatımızın birçok alanında kullanılabilecek bir yapıdır.
Eleman Ekleme ve Silme İşlemi
Binary search tree yapısında eleman ekleme ve silme işlemi oldukça kolaydır. Bu işlemler yapılırken tree yapısının açısından hiçbir şey bozulmadan yapılmaktadır.
Eleman ekleme işlemi yaparken öncelikle, eklemek istediğimiz eleman root düğümünden başlayarak tree yapısında gezinilir. Gezilirken eklemek istediğimiz elemanın değeri mevcut düğümün değerinden büyük ya da küçük olduğuna bakılır. Eğer eklemek istediğimiz elemanın değeri mevcut düğümün değerinden büyükse sağa, küçükse sola geçilir. Boş düğüm bulunana kadar bu işlem tekrarlanır ve eleman ağacın uygun bir yerine yerleştirilir.
Silme işlemi yaparken ise silinmek istenen eleman ağaçta aranır. Eğer silmek istediğimiz eleman mevcut düğümün değerine eşit ise, söz konusu düğüm çıkarılır. Çıkarılacak düğüm yaprak düğüm ya da yalnızca bir çocuk düğümden oluşuyorsa, düğümün tamamı silinir. Ancak çocuk düğümleri mevcutsa, düğümün silinmesiyle birlikte sağ ya da sol çocuk düğümleri geri kalan ağaca yerleştirilir.
Örneğin, eleman ekleme işlemini şu şekilde gerçekleştirebiliriz:
| Ağaç yapısı | Eleman | Eklenen elemanın ağacı |
|---|---|---|
10
| 12 | 10
|
Yukarıdaki ağaç yapısına 12 elemanını eklediğimizi varsayalım. Öncelikle 12 elemanı root olan 10 elemanından büyük olduğu tespit edilir ve sağ düğüme (15) geçilir. Ancak burada yaprak düğüm olmadığından, 12 elemanı sağ alt düğüm olarak yerleştirilir. Sonuçta ağaç yapısı yukarıdaki gibi oluşur.
Eleman silme işlemini de şu örnekteki gibi gerçekleştirilebilir:
| Ağaç yapısı | Silinecek Eleman | Silinen Elemanın ağacı |
|---|---|---|
10
| 10 | 15
|
Bu örnekte 10 elemanı silinecek eleman olarak seçilmiştir. Öncelikle 10 elemanı ağaçta bulunur ve mevcut düğümün sağ çocuk düğümü yerine, sol çocuk düğümü (5) bağlanır. Sonuçta yukarıdaki ağaç yapısı oluşur.
Arama İşlemi
Binary search tree yapısında eleman arama işlemi oldukça önemlidir ve yapının avantajlarından biridir. Arama işlemi, verilen bir anahtarın yapının kökünden başlayarak bir sonraki adımın sağ mı yoksa sol mu olduğuna karar vererek, anahtarı bulmak için ilerler. Eğer anahtar, bulunduğu düğümün anahtarı ile aynıysa, arama işlemi tamamlanmış olur.
Örneğin, aşağıdaki şekildeki binary search tree yapısında '35' anahtarının aranması işlemi ele alınsın:
| 100 | 200 | 300 | |||
| 50 | 80 | 250 | |||
| 35 | 90 | 150 |
İlk adımda, '35' değeri root olan 100 düğümündedir. '35' değeri, 100 düğümünden küçüktür, bu nedenle sol tarafı aramaya devam edilir. İkinci adımda, '35' değeri olan düğüm bulunur ve arama işlemi tamamlanır.
Eğer aranan anahtar binary search tree yapısında yoksa, sondaki düğüme ulaşıldığında anahtarın yapıda olmadığı sonucuna varılır. Örneğin, yapının önceki örneğinde 15 anahtarı aransa bulunmayacak bir anahtar olarak sonuca ulaştırılacaktır.
Arama işlemi, binary search tree yapısının hızlı bir şekilde verilen bir anahtarı aramak için güçlü ve etkili bir yöntemdir.
Kullanım Alanları
Binary search tree yapısı, özellikle veri yönetimi, arama ve sıralama işlemlerinin yapıldığı birçok alanda kullanılabilir. Örneğin, bir veri tabanı yazılımında, verilerin hızlı ve etkin bir şekilde aranması gerektiğinde binary search tree yapısı tercih edilebilir. Ayrıca, bilgisayar bilimleri ve yapay zeka alanlarında kullanılan birçok algoritmanın temelinde binary search tree yapısı yatar.
Binary search tree yapısı, aynı zamanda internet tarayıcılarındaki adres çubuğunda kullanılır. Bir URL adresi, bir binary search tree yapısında saklanır ve adresin tarayıcıdan istendiği zaman, arama işlemi binary search tree yapısı üzerinde gerçekleştirilir. Binary search tree yapısı, benzer şekilde, sözlük yazılımlarında da kullanılabilir. Kelimelerin hızlı aranabilir ve etkin bir şekilde sıralanabilir hale getirilmesinde binary search tree yapısı tercih edilebilir.
- Binary search tree yapısının faydaları:
- - Verilerin hızlı bir şekilde sıralanması ve aranması
- - Bellek (memory) kullanımının ölçülü olması,
- - Verilerin düzenlenmesinin kolay olması,
- - Elemanların birbirinden bağımsız şekilde eklenebilmesi
Yukarıdaki olanakları sağlaması ve pek çok alanda kullanımı mümkün olması, binary search tree yapısının popülerliğini korumasını sağlar.