Python’da Binary Tree (İkili Ağaç) Veri Yapısının Nested List (İç İçe Liste) Şeklinde Uygulanması
Selamun aleyküm. Ben Lütfullah Erkaya. Bu yazımda Python’da ikili ağaçlardan (binary tree) bahsedeceğim.
Bilgisayar biliminde ağaç (tree), düğümlerden (node) ve düğümler arasındaki ilişkileri gösteren kenarlardan (edge) oluşan bir Soyut Veri Tipi’dir (Abstract Data Type). Düğümler içerisinde veri bulunur. Ters bir ağaca benzer. Biyoloji’deki soy ağacı örnek olarak gösterilebilir.
Kök düğümünün özelliği üst düğüme (parent node) sahip olmamasıdır. Yaprak düğümün (leaf node) özelliği ise alt düğüme (child node) sahip olmamasıdır. Ağacın yüksekliği 4'tür (bazı kaynaklara göre 3 de denebilir).10 tane düğüme sahiptir. Yaprak düğümleri: H, I, J, F, G. Her bir düğüme giden tek bir yol (path) vardir. Mesela J’ye ulaşmak için A,B,E yolundan gidilebilir sadece. Bir düğümün derinliği, o düğümün köke uzaklığıdır.
Ağacın yapısı recursive’dir çünkü ağacın bir koluna bakarsanız kendisi de bir ağaçtır. Mesela yukarıdaki ağaçta köke iki tane ağaç bağlıdır diyebiliriz. Böyle olduğu için de ağaç için yazacağımız fonksiyonları recursive olarak kolayca yazabiliyoruz.
Diyeceksiniz ki iyi hoş da ne gerek var buna? Liste bize yetmez mi? Ağacın işe yaradığı bir durum göstereyim sizlere. Mesela elimizde bir liste var. Bu listede bir kelime arıyoruz. Listede n kelime var diyelim. İstediğimiz kelimeyi bulmak için listenin her elemanına bakmamız gerekir kelimemize eşit mi diye. Bu algoritmanın karmaşıklığı O(n)’dir. Mesela listemizde 1000 tane kelime varsa en kötü durumda 1000 tane karşılaştırma işlemi gerekir. Ama eğer kelimelerimizi liste olarak değil de ağaç olarak tutuyor olsaydık mesela şöyle bir ağaç oluşturabilirdik:
Böyle bir ağaçta kelime aramak çok daha hızlıdır. Kelime uzunluğu kadar işlem yapmak yeterlidir. Ağaçta 10000 kelime bile olsa yine kelime uzunluğu kadar işlemle kelimeyi bulabiliriz. Bu ağacın ismi Trie’dir. Retrieval’dan gelir.
Ağacın listeye göre bir avantajı da eleman eklemenin (insert) karmaşıklığıdır. n elemanlı listeye eleman eklemenin karmaşıklığı O(n)’dir çünkü listeye eleman ekleyince (sonuna eklemiyorsanız) eklediğiniz yerin sağındaki tüm elemanların indekslerinin 1 artırılması gerekir. Ama ağaca bir değer eklemenin karmaşıklığı her zaman O(n) değildir. Mesela elinizde n tane elemanlı dengeli bir binary tree varsa yeni eleman ekleme karmaşıklığı, ağacın yüksekliği yani O(log₂(n)) olur. Tabii, ağacınız en dengesiz hâlde, yani linked list halindeyse karmaşıklık O(n) olur ki zaten liste gibidir bu yapı. Yazının devamında bunlara tekrar değineceğiz. Aşağıdaki resimde liste metotlarının karmaşıklıkları yer alıyor:
Tabloya bakınca Get Lenght’in O(1) olması dikkat çekiyor. Bir listenin eleman sayısını bulmak için normalde aklıma tüm listeyi gezip saymak geliyor, böylelikle karmaşıklık O(n) oluyor ama listenin uzunluğu liste nesnesinde her zaman kayıtlıdır çünkü bu bilgi listeyi Ram’da belirtmek için gereklidir. Bu kayıtlı bilgiyi çekmek de O(1) oluyor.
Ağaçlar başka birçok yerde kullanılır. Mesela işletim sistemlerindeki dosya/klasör sistemi de bir ağaçtır. Bu yazımızda sadece Binary Tree’ye ve Binary Search Tree’ye değineceğiz.
İkili Ağaç (Binary Tree)
Her bir düğümde en fazla 2 tane alt düğüm bulunan ağaçtır. Eğer her iki yaprak düğümü (leaf node) arası derinlik farkı 1 veya 0 ise ağaç dengeli ağaçtır (balanced tree).
İkili Arama Ağacı (Binary Search Tree)
İkili ağaçtır. Özelliği her bir düğümde, sol kolun değerinin düğümün değerinden küçük, sağ kolun değerinin ise düğümün değerinden büyük olmasıdır.
Bu ağacın kullanışlılığı değer aramanın verimli olmasıdır. Ağaçta sayı araması yapmanın karmaşıklığı O(h)’dır. Yani yükseklik kadardır. Eğer ağaç dengeliyse, ağaçta n düğüm varsa, yüksekliği log₂(n) olur, bu da bize O(log₂n) karmaşıklık verir. Ama mesela ağaca bir sıralı listenin elemanlarını koyarsak, tüm değerler bir tarafa birikecektir.
Mesela [1, 2, 3, 4, 5, 6] listesini ağaca bu sırayla eklersek, yukarıdaki resimde sağdaki ağaç oluşur. Sağdaki ağaçta bir değer aramanın karmaşıklığı O(n)’dir. Ama [4, 2, 1, 3, 5, 6] sırasıyla ekleseydik soldaki ağaç oluşacaktı ve karmaşıklık O(log₂n) olacaktı.
İkili Ağaç’ın (Binary Tree) Python’da Nested List Şeklinde Uygulanması
Şu ana kadar ağacı grafik halinde gösterdik. Python’da göstermenin bir yolu nested list şeklinde göstermektir. Bu şekilde göstermek çok verimli olmayabilir ama öğrenmek için iyidir.
Mesela yukarıdaki ağaç Python’da [1, [2, [4, [], []], [5, [], []]], [3, [], []]] şeklinde gösterilebilir. Çok karışık gözüküyor olabilir ama yazının devamında buna uygun fonksiyonlar yazdıktan sonra işimiz kolaylaşacak. Bu nested list’i ekrana ağaç olarak yazdıran fonksiyon bile yazacağız. Önce temel şeylerden başlayalım. Bir düğümü şöyle ifade ederiz:
[dugum_degeri, sol_agac, sag_agac]Fonksiyonların olduğu dosyası aşağıda github’da paylaşacağım, açıklamalar da kodun içerisinde olacak.
binary_tree.py
Başka bir yazıda görüşmek üzere.
https://github.com/lutfullaherkaya/kucuk-kodlar/tree/main/binary_tree
