Python ile Binary Search Tree ve Türevleri-III

Merhabalar yeni bir yazı dizisiyle karşınızdayım. Aşağıdan bu serinin ilk yazısına 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İkili Olmayan Ağaçlar(Non-Binary Tree)
İkili Olmayan Ağaç yapısına bir örnek(stackoverflow.com kaynağından alındı.)

Ağaç veri yapısını hiyerarşi için kullanıyoruz ve sizin de bildiğiniz gibi dünyadaki bütün hiyerarşiler ikili hiyerarşi değiller. Yukarıdaki ağaçta görebileceğiniz İkili Olmayan Ağaç bu ilişkileri modellemek için kullanılıyor. Yazının geri kalanında bu ağaç yapısının nasıl gerçeklendiğini açıklayacağız. Bu yazıyı takip ederken boşluk kalmaması adına başlamadan önce lütfen ilk yazıyı okuyun.

İkili Olmayan Ağaç için Düğüm Yapısı

Bu düğüm yapısının ikili ağaçtan farkı çocukların sol ve sağ çocukla sınırlı olmamasıdır. Bu ağaçların düğümlerinde çocuklar bir liste olarak tutulur ve işlemler buna göre değiştirilir. Burada şunu gözlemleyebiliriz: İkili Ağaçlar, aslen çocuk listesinin boyutunun ikiden fazla olamadığı İkili-Olmayan Ağaçlardır. Bu bağlamda, İkili Olmayan Ağaç yapısı daha genelleştirilmiş bir yapıdır. Aşağıda bu yapıyı gözlemleyelim:

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

İkili Olmayan Düğüm yapısında işlemler

‘getID’: Bu tip ağaçlarda düğümleri birbirinden ayırt edebilmek için oluşturulmuş objenin ID’sini veren ‘id’ fonksiyonunu kullanıyoruz.

İkili-Olmayan Ağaçlarda İşlemler

Arama İşlemi

Yukarıda Python’ın kendi özelliği olan ID fonksiyonuyla içlerindeki değerler aynı olsa bile düğümleri birbirinden ayırt edebiliriz. Bu sayede yukarıdaki İkili Olmayan Ağaç yapısında olduğu gibi aynı değeri barındıran birden çok düğüm oluşturabiliriz.

Ekleme İşlemi

İkili Olmayan Ağaçlarda ekleme işlemi

Silme İşlemi

İkili Olmayan Ağaçlarda genel-geçer bir silme işlemi bulunmamakta. Burada siz verinizin yapısına göre özgürce davranabilirsiniz. Benim karşılaştığım silme mekanizmaları:

  • Taht teslimi: Silinen düğümün ilk çocuğunu düğümün yerine geçir. Bu durumda ilk düğüm kardeşlerinin ebeveyni oluyor :)
  • Alt ağacı silme: Silinen düğümün bütün alt düğümlerini silme.
  • Himaye: Silinen düğüme ait alt ağaç, başka bir düğümün altına taşınır.

İkili-Olmayan Ağaçlarda Dolaşma(Traversal)

Bu bölümdeki dolaşma algoritmalarının mantığı İkili Arama Ağacı ile aynı. Orada yığın veya kuyruk yapılarına sağdaki ve soldaki çocukları eklerken İkili Olmayan Ağaç yapısında ‘çocuklar’ listesindeki bütün elemanlar yığın(DFS ise) ya da kuyruk(BFS ise) yapılarına ekleniyor.

Derinlemesine Arama(Depth First)

İkili Olmayan Ağaçta Derinlemesine Arama

Enine Arama(Breadth First)

İkili Olmayan Ağaçta Enine Arama

Aşağıda örnek çıktıları görebilirsiniz:

İkili Olmayan Ağaçta İşlemler ve Çıktıları

Bir sonraki yazıda görüşmek üzere.