İkili Ağaç ve İkili Arama Ağacı: İkili Ağaç ve İkili Arama Ağacı Arasındaki Fark

Tanıtım

Sıralama, verilerin daha etkin bir şekilde analiz edilebilmesi için sistematik bir sıraya göre düzenlenmesi işlemidir. Belirli bir kaydı tanımlama işlemine arama denir. Veriler belirli bir düzende düzgün bir şekilde sıralanırsa, arama kolay ve verimli bir görev haline gelir. Bu makale, en önemli doğrusal olmayan veri yapılarından biri, yani ağaçlar ile ilgilidir.

Ağaçlar öncelikle öğeler arasında hiyerarşik bir ilişki göstererek verileri temsil etmek için kullanılır. Örneğin, içindekiler tablosu, soy ağacı. Teknik olarak, bir ağaç bir veya daha fazla düğümün sonlu bir 'T' kümesi olarak tanımlanabilir, öyle ki bir düğüm ağacın kökü olarak atanır ve diğer düğümler n>=0 ayrık kümeler T1, T2, T3, T4…. Tn ve bu kök düğümün alt ağaçları veya çocukları olarak adlandırılır.

İkili Ağaç nedir?

İkili ağaç, bir düğümün 0, 1 veya 2 düğüme sahip olabileceği doğrusal olmayan bir veri yapısıdır. İkili ağaçtaki her bir düğüm, bir ana düğüm veya bir alt düğüm olarak adlandırılır. İkili Ağacın en üstteki düğümüne kök düğüm denir. Her bir üst düğüm, sol alt düğüm ve sağ alt düğüm olmak üzere en fazla 2 alt düğüme sahip olabilir.

İkili ağaçtaki bir düğümün üç alanı vardır:

1. Veri Öğesi – Düğüm tarafından depolanacak veri değerini saklar.
2. Sol alt öğeye işaretçi – Sol alt düğümün referansını (veya adresini) saklar.
3. Sağ alt öğeye işaretçi – Sağ alt düğüme yapılan başvuruyu saklar.

Bu şekilde, bir İkili Ağaç oluşturmak için birkaç düğüm birleştirilir.

Bir İkili Ağaç şu şekilde temsil edilebilir:

Kaynak

Yukarıdaki şekilden, kök düğüm 2'nin iki çocuğu (veya alt düğümleri) vardır, 7 ve 5, 7 sol alt düğüm olarak ve 5, sağ alt düğüm olarak adlandırılır. Bu şekilde, alt düğümlerin her biri, diğer birkaç düğüm için bir üst düğüm görevi görür ve birlikte İkili Ağacı temsil eder.

Kontrol edin: İkili Ağaç Türleri

İkili Ağaçta Kullanılan Terminolojiler

Düğüm : Bir ağaçtaki bir sonlandırma noktasının temel temsili.

Kök Düğüm : İkili Ağacın en üstteki düğümü.

Ana Düğüm : Bir düğüm başka bir düğüme kenarlardan bağlıysa, ana düğüm olarak bilinir. İkili bir ağaçta, bir üst düğümün en fazla 2 alt düğümü olabilir.

Alt Düğüm : Bir düğümün öncülü varsa, alt düğüm olarak bilinir.

Yaprak Düğüm : Alt düğümü olmayan düğüme yaprak düğüm denir.

Bir düğümün derinliği : Kök düğümden derinliği ölçülecek olan belirli düğüme olan mesafedir.

Ağacın yüksekliği : Kök düğümden yaprak düğüme kadar olan en uzun mesafedir.

Bunlar bir İkili Ağacın birkaç temel terminolojisidir. İkili Ağacın bu temel anlayışıyla, İkili Arama Ağacı olarak bilinen İkili Ağacın ilerlemesine geçelim.

Ayrıca Okuyun: İkili Arama Algoritması: İşlev, Yararlar, Zaman ve Mekan Karmaşıklığı

İkili Arama Ağacı Nedir?

Adından da anlaşılacağı gibi, İkili Arama Ağacı veya BST, verileri sıralamak, almak ve aramak için kullanılan bir ağaçtır. Ayrıca, düğümlerin belirli bir sırada düzenlendiği bir tür doğrusal olmayan veri yapısıdır. Bu nedenle “ Sıralı İkili Ağaç ” olarak da adlandırılır . Aşağıdaki özelliklere sahiptir:

• Bir düğümün sol alt ağacında, yalnızca o düğümün anahtarından daha küçük düğümler bulunur.
• Bir düğümün sağ alt ağacında, yalnızca o düğümün anahtarından daha büyük düğümler bulunur.
• Her düğümün ayrı anahtarları vardır ve İkili Arama Ağacında yinelemelere izin verilmez.
• Sol ve sağ alt ağaç da bir ikili arama ağacı olmalıdır.

İkili Arama Ağaçlarını net bir şekilde anlamak için bu kavramı görselleştirelim.

Kaynak

Yukarıdaki şekilde kök düğümün değerinin 8 olduğunu görüyoruz. Daha fazla inceleme ile sol alt ağaçtaki tüm değerlerin kök düğümün değerinden küçük olduğu ve sağ alt ağaçtaki tüm değerlerin aynı olduğu görülmektedir. kök düğümden daha büyük değerler. Ayrıca, İkili Arama Ağacındaki her bir değerin benzersiz olduğu ve herhangi bir yineleme olmadığı belirtilmektedir. Böylece Binary Search Tree'nin yukarıda belirtilen özellikleri doğrulanmış olur.

Yine başka bir örnekte, sol ve sağ alt ağaçların ağaç boyunca benzersiz değerlere sahip ikili arama ağaçları olduğunu görüyoruz. Sol alt ağaçtaki yaprak düğümdeki değer 12'dir ve bu, 12 olan kök düğüm değerinden daha büyüktür. Dolayısıyla bu, BST'nin özelliğini karşılamaz ve dolayısıyla bir İkili Arama Ağacı değildir.

BST'de arama işlemi –

Aşağıda verilen değerlere sahip bir İkili Arama Ağacı düşünün. İkili Arama Ağacından 9 almak için arama işleminin nasıl yapıldığını anlayalım.

Kaynak

İkili aramayı gerçekleştirmek için öncelikle tüm tamsayıları sıralı bir dizide düzenleyeceğiz. Buna arama uzayı denir. Bu arama alanı, başlangıç ​​ve bitiş işaretçileri olarak adlandırılan iki işaretçiden oluşacaktır. Yukarıda verilen İkili Arama Ağacı dizisi şu şekilde temsil edilir:

İlk adım, dizinin orta değerini hesaplamak ve bizim durumumuzda 9 aranacak değerle karşılaştırmaktır. Bu, n/2 hesaplanarak yapılır, burada n dizideki (BST) toplam eleman sayısıdır ve 6'dır. Böylece 3. eleman ortadaki eleman yani 5'tir.

Artık ortadaki eleman 9 ile karşılaştırıldığına ve eşit (büyük) olmadığı için arama işlemi sağ dizi üzerinde yapılacaktır. Bu şekilde, arama işlemi aşağıda gösterildiği gibi yarıya indirilir:

Bir sonraki adımda, ortadaki eleman hesaplanır ve aranacak elemanımızla eşleşen 9 olarak bulunur.

İkili Ağaç ve İkili Arama Ağacı –

Artık hem İkili Ağaç hem de İkili Arama Ağaçları hakkında temel bir anlayışa sahip olduğumuza göre, ikisi arasındaki bazı farkları hızlıca özetleyelim.

Çözüm

Bu nedenle, hem İkili Ağacın hem de İkili Arama Ağacının bir düğüm koleksiyonuyla ortak bir hiyerarşik yapıya sahip olmasına rağmen, uygulamalarında birkaç farklılığa sahip oldukları sonucuna varıyoruz. İkili Ağaç, hiçbir ebeveynin 2'den fazla çocuğu olmaması gereken basit bir kurala sahip temel bir yapıdır, oysa İkili Arama Ağacı, düğümlerin düzenlenmesi gereken belirli bir sırayı izleyen ikili ağacın bir çeşididir.

İkili ağaç ve İkili arama ağacı hakkında bilgi edinmek istiyorsanız, çalışan profesyoneller için oluşturulan ve 10'dan fazla vaka çalışması ve proje, pratik uygulamalı atölye çalışmaları, endüstri ile mentorluk sunan IIIT-B & upGrad'ın Veri Biliminde PG Diplomasına göz atın uzmanlar, sektör danışmanlarıyla bire bir, 400+ saat öğrenim ve en iyi firmalarla iş yardımı.

Dünyanın en iyi Üniversitelerinden çevrimiçi veri bilimi kurslarını öğrenin . Kariyerinizi hızlandırmak için Yönetici PG Programları, Gelişmiş Sertifika Programları veya Yüksek Lisans Programları kazanın.