İkili Ağaçlara Yeni Başlayanlar Kılavuzu

Bilgisayar bilimi derecenizde bir veri yapıları kursu aldıysanız veya kendi kendini yetiştirmiş bir programcıysanız, "İkili Ağaçlar" terimiyle karşılaşmanız olasıdır. Kulağa biraz bunaltıcı ve karmaşık gelse de, ikili ağaç kavramı oldukça basittir.

İkili ağaçları incelerken ve neden programcılar için gerekli bir temel kavram olduklarını okuyun.

İkili Ağaçlar Nedir?

İkili ağaçlar, öğrencilere veri yapıları dersinde öğretilen ilk veri yapılarından biridir. İkili ağaç birçok düğümden oluşur ve ikili ağacın her düğümü, sol ve sağ alt veri düğümlerini gösteren iki işaretçi içerir.

İkili ağaçtaki ilk düğüme “kök” denir. Bir ağaçtaki son seviyedeki düğümlere yaprak denir.

Her düğüm, bir veri öğesi ve iki düğüm işaretçisi içerir. Boş bir ikili ağaç, bir boş gösterici ile temsil edilir. Zaten anlamış olabileceğiniz gibi, ikili ağaçların yalnızca iki çocuğu olabilir (dolayısıyla adı).

İkili Ağaç Yapılarının Türleri

Düğümlerin konumlandırılma şekline bağlı olarak birkaç farklı ikili ağaç yapısı vardır. İkili ağaca, ağaçtaki her düğümün sıfır veya iki çocuğu olduğunda tam ikili ağaç denir. Mükemmel bir ikili ağaçta, tüm düğümlerin iki çocuğu vardır ve yaprakların hepsi aynı derinliktedir.

İlişkili: Ücretsiz Kodlama Öğrenmenin En İyi Yolları

Tam bir ikili ağaç, son seviye hariç her seviyede doldurulmuş düğümlere sahiptir. Tam ikili ağaçlarda düğümler kökün sol tarafında yoğunlaşmıştır. Diğer bir yaygın yapı, dengeli bir ikili ağaçtır; bu yapıda sağ ve sol alt ağaçların yükseklikleri en fazla birer birer farklılık göstermelidir. Ayrıca sol ve sağ alt ağaçların da dengelenmesi gerekir.

Dengeli ikili ağacın yüksekliğinin O(logn) olduğuna dikkat etmek önemlidir; burada n, ağaçtaki düğüm sayısıdır.

Bazı durumlarda, her düğümün yalnızca bir sol veya sağ çocuğu varsa, ikili ağaç çarpık bir ikili ağaca dönüşebilir. Daha sonra bağlantılı bir liste gibi davranır, bu tür ağaçlara dejenere ağaç da denir.

İkili Arama Ağaçları Nelerdir?

İkili arama ağacı (BST), esasen "ikili arama ağacı" özelliği olarak bilinen özel bir özelliğe sahip sıralı bir ikili ağaçtır. BST özelliği, kökten daha küçük bir anahtar değerine sahip düğümlerin sol alt ağaca yerleştirildiği ve kökten daha büyük bir anahtar değerine sahip düğümlerin sağ alt ağacın bir parçası olduğu anlamına gelir.

BST özelliği, ağaçtaki her bir sonraki üst düğüm için doğru olmalıdır.

İkili arama ağaçları, hızlı ekleme ve arama sunar. Ekleme, silme ve arama işlemleri, bağlantılı bir listeye benzeyen en kötü durum zaman karmaşıklığına O(n) sahiptir.

İkili Ağaçların Faydaları

İkili ağaçlar birçok fayda sağlar, bu yüzden çok kullanışlı bir veri yapısı olarak kalırlar. Bir veri setindeki yapısal ilişkileri ve hiyerarşileri göstermek için kullanılabilirler. Daha da önemlisi, ikili ağaçlar verimli arama, silme ve eklemeye izin verir.

İkili bir ağacı uygulamak ve sürdürmek de çok kolaydır. İkili ağaç, programcılara sıralı bir dizinin ve bağlantılı bir listenin faydalarını sunar; bir ikili ağaçta arama, sıralanmış bir dizideki kadar hızlıdır ve ekleme veya silme işlemleri, bağlantılı listelerdeki kadar verimlidir.

İkili Ağaçlar Önemli Veri Yapılarıdır

İkili Ağaçlar çok önemli bir veri yapısıdır ve programcıların bunları programlarında rahatça uygulayabilmeleri çok önemlidir. Görüşmeciler genellikle çapraz geçişler, maksimum derinlik, yansıtma vb. gibi basit ikili ağaç problemlerini sorarlar.

İkili ağaç kavramını anlamanızı ve tipik görüşme problemlerine aşina olmanızı şiddetle tavsiye ederiz.

TreeViz: Veri Yapılarını Görselleştirmenin Basit Bir Yolu

Sonrakini Oku

Yazar hakkında