TechCodeview

İlk önce şunu anlayacağız ikili ağaç Ve ikili arama ağacı ayrı ayrı inceleyeceğiz ve sonra ikili ağaç ile ikili arama ağacı arasındaki farklara bakacağız.

İkili ağaç nedir?

A İkili ağaç birSol çocuğun işaretçisi:Sol alt düğümün referansını saklar.Sağ çocuğa işaretçi:Sağ alt düğümün referansını saklar.Veri öğesi:Veri öğesi, düğüm tarafından depolanan verilerin değeridir.

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

Yukarıdaki şekilde her düğümün en fazla 2 çocuk içerdiğini görebiliriz. Herhangi bir düğüm sol veya sağ çocuk içermiyorsa işaretçinin o çocuğa göre değeri NULL olacaktır.

İkili ağaçta kullanılan temel terminolojiler şunlardır:

Kök düğüm:Kök düğüm, ikili ağaçtaki ilk veya en üstteki düğümdür.Ana düğüm:Bir düğüm başka bir düğüme kenarlar aracılığıyla bağlandığında, bu düğüm ana düğüm olarak bilinir. İkili ağaçta ebeveyn düğümün en fazla 2 çocuğu olabilir.Çocuk düğümü:Bir düğümün öncülü varsa, o düğüm bir düğüm olarak bilinir. alt düğüm .Yaprak düğümü:Herhangi bir çocuk içermeyen düğüm olarak bilinen düğüm Yaprak düğümü .Dahili düğüm:En az 2 çocuğu olan düğüm olarak bilinir dahili düğüm .Bir düğümün derinliği:Kök düğümden belirli bir düğüme olan mesafeye denir. bir düğümün derinliği . Kök düğümün derinliği olmadığı için 0 ile etiketlenmesi, kök düğümlerin çocukları 1 ile etiketlenmesi, kök çocuğun çocuklarının 2 ile etiketlenmesi gibi tüm düğümlere etiketler sağlıyoruz.Yükseklik:Kök düğümden yaprak düğüme olan en uzun mesafe düğümün yüksekliği .

İkili ağaçta, bir ağaç olarak bilinen bir ağaç vardır. mükemmel ikili ağaç . Bu bir tüm iç düğümlerin iki düğüm içermesi ve tüm yaprak düğümlerin aynı derinlikte olması gereken ağaç. Mükemmel bir ikili ağaç durumunda, ikili ağaçta bulunan toplam düğüm sayısı aşağıdaki denklem kullanılarak hesaplanabilir:

n = 2^m+1-1

burada n düğüm sayısı, m ise düğümün derinliğidir.

İkili Arama ağacı nedir?

A İkili arama ağacı elemanları düzenlemek için belirli bir sırayı takip eden bir ağaçtır, oysa ikili ağaç herhangi bir sırayı takip etmez. İkili arama ağacında, sol düğümün değeri üst düğümden küçük olmalı ve sağ düğümün değeri üst düğümden büyük olmalıdır.

Örneklerle ikili arama ağacı kavramını anlayalım.

Yukarıdaki şekilde kök düğümün değerinin 15 olduğunu ve bu değerin sol alt ağaçtaki tüm düğümlerin değerinden daha büyük olduğunu görebiliyoruz. Kök düğümün değeri, sağ alt ağaçtaki tüm düğümlerin değerlerinden küçüktür. Şimdi kök düğümün sol çocuğuna geçiyoruz. 10, 8'den büyük ve 12'den küçüktür; aynı zamanda İkili arama ağacının özelliğini de karşılar. Şimdi kök düğümün sağ çocuğuna geçiyoruz; 20 değeri 17'den büyük ve 25'ten küçüktür; aynı zamanda ikili arama ağacının özelliğini de karşılar. Dolayısıyla yukarıda gösterilen ağacın ikili arama ağacı olduğunu söyleyebiliriz.

Şimdi yukarıdaki ikili ağaçta 12'nin değerini 16'ya değiştirirsek bunun hala bir ikili arama ağacı olup olmadığını bulmamız gerekir.

Kök düğümün değeri 15'tir, bu da 10'dan büyük ancak 16'dan küçüktür, dolayısıyla İkili arama ağacının özelliğini karşılamaz. Bu nedenle ikili arama ağacı değildir.

İkili arama ağacındaki işlemler

İkili arama ağacı üzerinde ekleme, silme ve arama işlemlerini gerçekleştirebiliriz. İkili aramada aramanın nasıl yapıldığını anlayalım. Arama işlemini gerçekleştirmemiz gereken ikili ağaç aşağıda gösterilmektedir:

Yukarıdaki ikili ağaçta 10'u aramamız gerektiğini varsayalım. İkili aramayı gerçekleştirmek için sıralanmış bir dizideki tüm tam sayıları dikkate alacağız. Öncelikle arama alanında tam bir liste oluşturuyoruz ve tüm sayılar arama alanında yer alacak. Arama alanı iki işaretçiyle (başlangıç ​​ve bitiş) işaretlenir. Yukarıdaki ikili ağacın dizisi şu şekilde temsil edilebilir:

Öncelikle ortadaki elemanı hesaplayacağız ve ortadaki elemanı aranacak elemanla karşılaştıracağız. Ortadaki eleman n/2 kullanılarak hesaplanır. N'nin değeri 7'dir; dolayısıyla ortadaki eleman 15'tir. Ortadaki eleman aranan elemana yani 10'a eşit değildir.

Not: Aranan eleman ortadaki elemandan küçükse arama sol yarıda gerçekleştirilecektir; aksi takdirde arama sağ yarıda yapılacaktır. Eşitlik durumunda eleman bulunur.

Aranacak eleman orta elemandan küçük olduğundan arama sol dizide yapılacaktır. Şimdi aşağıda gösterildiği gibi arama yarıya indirildi:

Sol dizideki orta eleman 10'dur ve bu da aranan elemana eşittir.

Zaman karmaşıklığı

İkili aramada n öğe vardır. Ortadaki eleman aranan elemana eşit değilse arama uzayı n/2'ye düşürülür ve elemanı bulana kadar arama uzayını n/2 oranında azaltmaya devam edeceğiz. Tüm indirgemede, eğer n'den n/2'ye, oradan da n/4'e vb. gidersek, o zaman log alacaktır.₂n adım.

İkili ağaç ile İkili arama ağacı arasındaki farklar