Veri Yapıları — Binary Search Tree Nedir?
Bu yazının Gist dosyası bulunmaktadır — Demo kodlarının bulunduğu Gist → Gist
Merhaba arkadaşlar. Bugün sizlere veri yapılarından (Data Structures) biri olan Binary Search Tree’den bahsetmek istiyorum.
Binary Search Tree Nedir?
Binary Search Tree, node’lardan oluşan ve her bir node’un en fazla 2 child node’a sahip olduğu veri yapılarından bir tanesidir.
Node Nedir?
A node is a basic unit of a data structure, such as a linked list or tree data structure. Nodes contain data and also may link to other nodes. Links between nodes are often implemented by pointers.— Wikipedia
- Node, bir veri yapısının en temel birimidir.
- Node’lar veriler içerebilirler ve aynı zamanda diğer nodelar ile aralarında bir bağlantı bulundurabilirler.
Görselde gördüğünüz her bir veri node olarak geçmektektedir ve node’lar arasında bağlantılar bulunmaktadır:
- Binary Search Treede en üstte bulunan node Root olarak adlandırılır.
- Root’tan küçük değere sahip olan node’lar Root’un sol tarafında yer alır
- Root’tan büyük değere sahip olan node’lar Root’un sağ tarafında yer alır.
Bu kural Recursive olarak sol ve sağ tarafta yer alan subtree’ler içinde geçerlidir.
Binary Search Tree’nin Avantajları Nelerdir ?
Binary search tree kullanarak oluşturan bir yapıda, bir elemanı silmek, eklemek veya bulmak gibi işlemler hızlı gerçekleştirilebilir. Burada bir elemanı bulabilmek için tek tek tüm elemanları dolaşmak yerine her seferinde veri setini ikiye bölerek ilerleme sağlanır. Örnek verecek olursak eğer;
Sözlükten bir kelime baktığımızı düşünelim. Sözlüklerde, her kelimenin alfabetik olarak sıralı olduğunu biliyoruz. Aradığımız kelimeyi bulmak için şu iki algoritmayı deneyebiliriz:
A algoritması:
- Kitabın en başından başlayarak aradığımız kelimeyi bulana kadar sırasıyla tüm kelimeleri incelemek.
B algoritması:
- Kitabın ortasından açıp ilk kelimeye bakmak. Eğer aranan kelime, alfabetik olarak kitabın ortasında bulunan ilk kelimeden büyükse kitabın sağ tarafına, değilse sol tarafına bakmaya devam etmek.
A algoritmasında kelime kelime gideceğimizden dolayı Time complexity değeri O(N)’dir.
Time Complexity
Time complexity bir algoritmanın çalışması için gerekli olan süredir. Ancak buradaki süre, saniyeleri hesaplayarak değil, kaç tane işlem gerçekleştirdiğine göre hesaplanmaktadır.
B algoritmasının Time Complexity’si O(logN)’dir. Her iterasyonda problemi ikiye böler.
Time complexity hesaplama işlemlerine ve diğer complexity’lere değindiğim şu yazıyı inceleyebilirsiniz :) → Nedir Bu “Big O Notation”?
Demo
Şimdi bir binary tree nasıl oluşturabiliriz, bir binary tree’ye nasıl eleman ekleyip çıkartabiliriz, binary tree içerisinde bulunan elemanları nasıl sıralı şekilde gösterebiliriz bu gibi işlemlere bir bakalım:
Binary tree’de her bir verinin Node olarak isimlendirildiğini söylemiştik. Her bir Node’un da left ve right olmak üzere child node’ları olabilir. Bu yüzden öncelikle bir Node Sınıfı oluşturalım.
Şimdi Binary Tree’miz için bir sınıf oluşturalım. Bir Binary Tree’de ilk olarak bize root bir değer gerekeceği için bir root property’si tanımlayalım.
Şimdii ekleme,çıkarma, spesifik node’u bulma gibi diğer işlemlerin metodlarını yazmaya başlayabiliriz.
Göstereceğim metodların tek çözüm olmadığını unutmayınız :)
Binary Tree’ye Node Ekleme — create()
create metodumuz ile ağacımıza node’ları eklemeye başlayalım. Ağacın ilk node’u her zaman root node’dur. Eğer bir root yoksa ilk eklenen node’u root’a atarız.
Eğer bir root değerimiz varsa ikinci gelen node değerinin root’un hangi tarafında yer alacağını belirlemek için insertNode adlı metodumuzu çağırıyoruz:
Binary Search Tree’nin özelliklerini hatırlayacak olursak eğer;
- Gelen yeni değer parent node’un değerinden küçükse solunda, değilse sağında yer alacaktı.
Eğer yeni gelen değer, parent node değerinden küçükse parent node’un sol tarafında bulunan child olarak atanır. Ancak parent’ın bu child’ı boş değilse demek ki daha önceden eklenmiş bir değer bulunmaktadır. Yeni eklemeye çalıştığımız değeri bu child’ın hangi tarafında bulunması gerektiğini belirlemek için tekrardan insertNode metodunu çağırırız. Bu çağırdığımız child aslında yeni değerin parent’ı olmuş olur. Biliyorum çok karıştı ortalık :) Lütfen altta bulunan gif’i inceleyiniz. İnceledikten sonra tekrar burayı okuyabilirsiniz veya daha detaylı açıklamasına gif’in altında bulabilirsiniz :)
Hazırsanız yukarıdaki uygulamanın detaylarına başlıyorum :)
1- Öncelikle 15 değerini ekliyoruz. Daha önceden eklenmiş bir değer olmadığı için 15 değeri ağacımızın root değeri olarak belirlenmiş olur.
2- Daha sonrasında 21 değeri geliyor. 21, 15'ten büyük olduğu için root’un sağında yer alır.
3- Daha sonrasında 10 değeri geliyor. 10, 15'ten küçük olduğu için root’un solunda yer alır.
4- Daha sonrasında 6 değeri geliyor. 6, 15'ten küçük olduğu için root’un solunda yer alır. Ancak 15'in solunda daha önceden eklediğimiz 10 değerli node bulunmaktadır. Ozaman bu 6 değerinde olan node’u bu seferde 10 değeri ile karşılaştırırız. Böylelikle 6 değerine sahip node’un 10 değerine sahip node’un hangi tarafına child node olarak ekleneceği belirleriz. Kodu tekrar inceleyecek olursanız eğer, bu işlemi recursive bir şekilde uygulayarak gerçekleştiriyoruz.
5- 21 değeri de aynı şekilde bir işlemden geçerek Binary Tree’ye ekleme işlemini gerçekleştiririz.
Node ekleme işlemleri için yazdığımız tüm kod:
Node Bulma — find()
find() fonksiyonumuz ile spesifik olarak belirtilen node’u bulma işlemini gerçekleştiririz.
Kullanıcı direkt olarak find fonksiyonunu çağırırsa, başlangıçta bir root değeri olmayacağı için “There is no Root” mesajını döndürürüz.
Bir root değeri varsa, aranan değeri karşılaştırmaya root değerimizden başlarız. Bunun için yardımcı bir fonksiyon yazalım.
Öncelikle değerlerin karşılaştırılması ile işlemimize başlıyoruz. Eğer değerler aynıysa aradığımız node’u bulmuşuz demektir. Bulduğumuz node’u döndürerek metoddan çıkarız.
Eğer değerler aynı değilse, aranan değerin parametre olarak gönderilen node değeri ile karşılaştırırız. Eğer aradığımız değer, node’un değerinden küçükse arama işlemlerine node’un sol tarafında bulunan child node ile devam ederiz.
Aynı şekilde, eğer aradığımız değer, node’un değerinden büyükse arama işlemlerine node’un sağ tarafında bulunan child node ile devam ederiz.
Aradığımız değer, oluşturulan Binary Tree’de yoksa fonksiyondan null değerini döndürürüz.
En Küçük Ve En Büyük Node Değerini Bulma
En Küçük Değeri Bulma — FindMinNode()
Yazının başında belirttiğim özellikleri hatırlayacak olursak eğer, bir Binary Tree’de root’tan küçük değerler tree’nin sol tarafında yer almaktaydı.
En küçük node’u bulmaya root değeri ile başlıyoruz.
current adında bir değişken oluşturduk. Bu değişken, o anki node değerini içerisinde bulundurur.
eğer current node’un left child’ı boş değilse, current değişkenine, node’un current.left node değerini atayarak bu şekilde current.left falsy yani null değerine ulaşana kadar devam ederiz. En sonunda da while işlemini tamamladıktan sonra en son current değerini döndürerek en küçük node değerine ulaşmış oluruz.
En Büyük Değeri Bulma — findMaxNode()
En büyük node değerini bulurken bu sefer root’un sağ tarafında bulunan node’lar ile işlemlerimizi gerçekleştiriyor oluruz.
Sıralı Şekilde Yazdırma — inOrder()
Bir Binary Tree’de bulunan node değerlerini nasıl sıralı şekilde yazdırabiliriz buna bir bakalım:
- Burada inOrder fonksiyonumuzu çağırarak başlıyoruz. Inorde içerisinde getInOrder adlı bir yardımcı fonksiyon bulundurmaktadır. getInOrder’a parametre olarak root değerimizi verdik.
- getInorder içerisinde öncelikle en küçükten başlamamız gerektiği için o an olduğumuz node’un left child’ı olup olmadığına bakarız. Eğer node varsa, getInorder metodumuzu node’un left child node’unu argüman olarak vererek tekrar çağırırız bu şekilde o anki node’un left child değeri null olana kadar recursive şekilde getInorder’ı çağırmaya devam ederiz.
- null değerine ulaştığımız zaman ilk if kontrolünü atlarız.
- console.log ile o anki node değerini yazdırırız.
- Daha sonrasında node’un right child’ı olup olmadığına bakarız. Yine aynı şekilde, eğer node’un right child değeri boş değilse getInorder metodu bu seferde node’un right child node değeri argüman olarak yazılarak tekrar çağrılır.
Demo kodlarının bulunduğu Gist → Gist
Umarım faydalı bir yazı olmuştur. Eksik veya yanlış olduğunu düşündüğünüz kısımları bana iletirseniz çok sevinirim :)
İletişim kanalları: Twitter — LinkedIn — Mail
Bir sonraki yazıda görüşmek üzere!
Bu yazının referansları :
https://en.wikipedia.org/wiki/Node_(computer_science)
https://www.digitalocean.com/community/tutorials/js-binary-search-trees
https://www.geeksforgeeks.org/implementation-binary-search-tree-javascript/
