Python ile Binary Search Tree ve Türevleri-I

Merhabalar yeni bir yazı dizisiyle karşınızdayım. Aşağıdan bir önceki yazıma ulaşabilirsiniz.

Eğer programlamayla teorik düzeyde uğraşıyorsanız, ağaç “tree” veri yapısı bir yerlerde karşınıza çıkmıştır. Bilgisayarda veriyi hiyerarşik şekilde ifade etmek bir dizgisel olarak ifade etmekten daha zordur. Hiyerarşinin ifadesi geçmişten günümüze ağaç veri yapısı kullanılarak sağlanmıştır. Bu yazı dizimizde ağaç veri yapısını, özelliklerini ve türevlerini ele alacağız. Konularımız aşağıdaki gibi olacak:

  • Düğüm ve Ağaç Kavramları
  • Binary Search Tree Yapısı ve Temel İşlemler
  • Array-Binary Search Tree Arasında Çevrim Yapmak
  • Ağaç Yapısını Dosyada Saklama: Serialization-Deserialization
  • Non-Binary Tree Yapısı ve Temel İşlemler
  • Quad-Tree ve Oc-Tree: 2 ve 3 Boyutlu Oyunlarda Ağaç Yapısı
  • B-Tree: Veritabanı ve Saklama Sistemlerinde Ağaç Yapısı

Düğüm Yapısı

Görsel http://www.introprogramming.info/ sitesinden alındı.

Her ağaç yapısı düğümlerden oluşur. Düğümler içlerinde bizim istediğimiz veriyi tutarlar ve diğer düğümlerle bir akrabalık ilişkisi içindedirler. Örnek bir düğüm yapısını aşağıda Binary Search Tree(İkili Arama Ağacı)’ye ait bir düğümde görebilirsiniz.

İkili Arama ağacının Binary(İkili) bir ağaç olması, ağacın her düğümünün yukarıda olduğu gibi iki adet çocuğunun olduğu gösteriyor bize. Eğer her düğümün üç çocuğu olsaydı bu durumda oluşan düğüme Ternary(Üçlü) Node; oluşan ağaça Ternary Tree diyecektik.

Düğüm Yapısındaki İşlemler

Düğüm Yapısının Temel İşlemleri

Setter(Atama) metotlarımızda yukarıda belirttiğimiz düğüm yapısındaki içeriklere uygun atamaları yapıyoruz. Sorgularımız da aşağıdaki işlevleri görüyor:

  • ‘isLeftNull’ = Sol tarafta bir çocuk var mı? Yoksa ‘None’ mı?
  • ‘isRightNull’ = Sağ tarafta bir çocuk var mı? Yoksa ‘None’ mı?
  • ‘isRoot’ = Sadece kök düğümün ebeveyni yoktur. Cümleyi tersten de kurabiliriz: ebeveyni olmayan düğüm kök düğümdür.
  • ‘isLeaf’ = İki çocuğu da olmayan bir düğüme yaprak düğüm denir.

Tree(Ağaç) Yapısı

Görsel https://commons.wikimedia.org/ kaynağından alındı.

Her ağaç yapısı en az bir düğüme sahiptir. En tepedeki düğüm geçen bölümde anlattığımız ‘Root(Kök)’ düğümdür ve bir ağaç tanımlamak için bir kök düğüm yeterlidir. Aşağıda genelleştirilmiş bir ağaç sınıfını görebilirsiniz.

Yukarıdaki ağaçta İkili Arama Ağacı’nın en önemli özelliğini görebilirsiniz. Soldan sağa doğru ilerlediğinizde sayılar büyüyor. Bu özellik arama işlemlerinde(veritabanı benzeri sistemlerde) indeksleme işleminin temelini oluşturuyor. (Dikkatli okuyucularımız 19 sayısının yanlış yerleştirildiğini gözlemleyebilirler. Bu muhtemelen bir yazım veya çizim hatası.)

Ağaç yapısının genel hatları yukarıdaki kod örneğindeki gibidir.

Binary Search Tree’de İşlemler

Ekleme İşlemi

Ağaçta Ekleme İşlemi

İkili Arama ağacının ekleme aşamaları

  1. O anda üzerinde çalışılan düğümü gösteren bir değişken(‘current’) oluşturulur ve kök düğümden çalışmaya başlanılır.
  2. Eğer eklenecek değer mevcut değerden küçükse sola, değilse sağa yönlenilir.
  3. Sola yönlenildiğinde solda bir düğüm mevcut değilse ya da sağa yönlenildiğinde sağda bir düğüm yoksa ekleme işlemi gerçekleştirilir.

Arama İşlemi

Ağaçta Arama İşlemi

Arama işleminin aşamaları ekleme işlemine benziyor. Fakat burada eşit bir değerle karşılaştığımızda sola yönlenmek yerine arama işlemi amacına ulaştığından bulduğumuz düğümü döndürüyoruz. Bir yerde düğümleri sonuna gelirsek aramanın başarısız olduğunu belirtmek için “None” döndürüyoruz.

Silme İşlemi

Ağaçta Silme İşlemi

Silme işlemi yukarıdaki işlemlere göre daha karışık(Bütün ağaç tipleri için silme işlemleri daha karışık oluyor genelde).

  1. Silinmesi gereken eleman önce bulunur ve eğer varsa işlem devam eder yoksa hiçbir şey döndürmez.
  2. Silinmesi gereken elemanın bir ebeveyni var mı diye bakılır. Kök düğüm haricindeki bütün düğümlerin bir ebeveyni vardır. Bu durumdan dolayı kontrol ifadesi doğruysa kök olmayan bir düğüm silinecek demektir. Eğer yanlış ise kök düğüm silinmek istenmiştir bu durumda yeni bir düğümün kök düğüm olması gerekmektedir.
  3. Buradan sonraki kısım silme işleminin en kafa karıştırıcı kısmı. Eğer silinen düğümün sağda çocuğu yoksa ebeveynin sol çocuğu olarak silinen düğümün sol çocuğunu atıyoruz. Böylece silmek istediğimiz eleman ağaç yapısından ayrılmış oluyor.
  4. Fakat eğer sağ çocuk var ise silinecek düğümün sol çocuğu sağ çocuğa bağlı ağaçtaki en sol düğüme ekleniyor. Sağ çocuğun altından sürekli sola gitmek suretiyle erişeceğimiz düğüme, en sol düğüme, silinecek düğümün sol çocuğunu atıyoruz. Böylece ikili arama ağacının soldan sağa doğru gidince sayıların artmasını sağlayan özelliğini korumuş oluyoruz. Bu işlem bitince sağ çocuk ebeveynin sol çocuğu yapılıyor.
Ekleme, silme ve bulma işlemlerinin animasyonu

Yukarıdaki videoda gerçeklediğimiz işlemlerin aşama aşama görselleştirilmiş halini bulabilirsiniz.

Ağaçta Dolaşma(Traversal) Yöntemleri

Derinlemesine Arama(Depth First Search)

Depth First Search Traversal

Derinlemesine arama bir stack(yığın) yapısı kullanılarak gerçekleştirilir. Kök düğümden başlayarak düğümler ve çocukları yığın veri yapısına eklenir. Her seviyede en yukarıdaki düğüm yığın yapısından “pop(üstten alma)”lanır ve çocukları yığına eklenir.

Her seviyede en son eklenen çocuklar yığından çıkarılacağından ilerleme sürekli aşağı yönlüdür bu yüzden bu dolaşma yöntemine derinlemesine denir.

Yukarıdaki gerçeklemede ekstra bir gözlem ağacın ilk sağ tarafına doğru derinlemesine ilerleme yapılmasıdır. Bu durumu 8. ve 9. satırı değiştirerek sola doğru ilerleyecek hale getirebiliriz.

Enine Arama(Breadth First Search)

Breadth First Search Traversal

Enine arama bir queue(kuyruk) yapısı kullanılarak gerçekleştirilir. Kök düğümden başlayarak düğümler ve çocukları kuyruk veri yapısına eklenir. Her seviyede kuyruğun en önündeki düğüm çıkarılır ve çocukları kuyruğun sonuna eklenir.

Her seviyede ilk eklenen çocuklar kuyruktan ilk çıkarılacağı için her seviye sırasıyla işlenir. Bu aşama aşama ilerleyiş sebebiyle bu yönteme enine arama denir.

Bu zamana kadar oluşturduğumuz yapıyı test edelim:

Aşağıdaki videoda bu iki yöntemin görselleştirilmiş halini görebilirsiniz.

Bloguma bu zamana kadar verdiğiniz destek için teşekkürler. Bir başka yazıda buluşmak üzere.