BİL207U-VERİ YAPILARI
Ünite 7: İkili Ağaçlar ve İkili Arama Ağaçları
Giriş
Bilgisayar bilimlerinde verileri listelemek için kullanılan yaygın yapılardan biri ağaç yapılarıdır. Verileri hiyerarşik bir düzende depolamak için kullanılan, doğrusal olmayan bir veri yapısıdır.
Ağaç Yapıları
Bilgisayar bilimlerinde ağaç; verilerin düğümlerde tutulduğu, düğümlerin birbirlerine kenarlar ile bağlandığı doğrusal olmayan bir veri yapısıdır. Ağaç yapısını günlük yaşamda verileri sıralamak için kullanabiliriz. Örneğin aile soy ağacı veya bir şirketin yönetim şeması ağaç yapısına örnek olarak verilebilir.
Teknik olarak ağaç, düğüm (node) adı verilen varlıklar topluluğudur. Düğümler kenarlar ile birbirine bağlanır. Her düğüm bir değer veya veri içerir. Aynı zamanda alt düğümlere sahip olabilir. Ağacın ilk düğümüne kök (root) denir. Kök, düğüme başka bir düğüm bağlanırsa kök düğüm ebeveyn düğüm (parent node) olarak; bağlanan düğüm ise çocuk düğüm (child node) olarak adlandırılır. Ağaç yapısının diğer önemli parçası ise düğümleri birbirine bağlayan bağlantılardır. Bağlantılar aynı zamanda kenar (edge) olarak da adlandırılır. Düğümler arasındaki ilişkiyi yönetir. Ağaç yapısındaki son düğümler ise yaprak (leaves) olarak adlandırılır. Bu düğümlerin çocuk düğümleri yoktur. Bu terimlerin yanında ağacın boyutu hakkında bilgi veren yükseklik (height) terimi vardır. Bir ağacın yüksekliği, kök düğümünden en uzaktaki yaprak düğümüne kadar olan mesafeyi belirtir. Herhangi bir düğümün derinliği (depth) ise o düğümün kök düğümüne olan mesafesi için kullanılır.
Bilgisayar bilimlerinde sıkça kullanılan ağaç yapılarının avantajları aşağıdaki gibi sıralanabilir;
• Veri depolamak için hiyerarşik bir yol sağlar. • Bir veri kümesindeki yapısal ilişkiyi yansıtır. • Bir diziden veya bağlantılı listeden daha hızlı sonuç veren ekleme, silme ve arama işlemlerine izin verir. • Verileri tutmak ve taşımak için esnek bir yol sağlar. • Birçok düğümün depolanmasına izin verir.
Ağaç Yapısı Türleri
Verileri saklama türlerine veya izin verilen çocuk sayılarına göre farklı ağaç yapıları mevcuttur. Geliştirilen uygulamanın ihtiyacına göre aşağıdaki yapılardan birisi seçilebilir.
Genel Ağaç (General Tree)
Genel ağaç, hiyerarşik yapı üzerinde hiçbir kısıtlaması olmayan bir tür ağaç veri yapısıdır. Genel bir ağaçta her düğümün sonsuz sayıda çocuğu olabilir. Hiyerarşik yapıya sahip herhangi bir ağacı genel ağaç olarak sınıflandırabiliriz. Ayrıca düğümler, 0 ile n arasında herhangi bir dereceye sahip olabilir. Genel bir ağaç, bir
bilgisayar sistemindeki klasör yapısı gibi hiyerarşik yapıları depolar.
İkili Ağaç (Binary Tree)
Adından da anlaşılacağı gibi ikili ağaçlar, iki çocuk düğüme sahip düğümlerden oluşur. İkili ağaçtaki herhangi bir düğüm yalnızca sıfır, bir veya iki düğüme sahip olabilir. Bu ağaçlar son derece işlevseldir ve veri yapısında birçok amaca hizmet etmeye yardımcı olur. Bir ikili ağaç kullanarak veri bilimciler ve analistler; çatallı bir yapı aracılığıyla verilerin bir temsilini oluşturabilir, düğümlere kolayca erişebilir ve bunları uygun şekilde etiketleyebilir.
İkili Arama Ağacı (Binary Search Tree)
İkili arama ağacı, bazı kısıtlamalara sahip ikili ağacın bir uzantısıdır. Yalnızca bir düğümün sol çocuğu ana değerden küçük veya ona eşit olduğunda ve aynı düğümün sağ çocuğu ana değerden büyük veya ona eşit olduğunda ağaç ikili arama ağacı olur. İkili ağacın bu benzersiz alt türü, verilerin daha hızlı yerleştirilmesine veya aranmasına yardımcı olur. Verilerin eklenmesini ve çıkarılmasını kolaylaştırır. Veri bilimcileri ve veri analistleri, basit algoritmaları sıralamak için ikili arama ağaçlarını sıklıkla kullanırlar. Bunun yanında ikili arama ağaçları, sürekli olarak veri ekleyip çıkardığınız arama uygulamalarında kullanılır.
AVL Ağacı
AVL ağacı, kendi kendini dengeleyen bir ikili arama ağacıdır. Bu ağaç, yüksekliğini otomatik olarak dengeleyebilir çünkü her düğüm, sağ alt ağaç ile sol alt ağacın yüksekliğindeki farkı temsil eden “denge faktörü” adı verilen bir değeri depolar. Bir ikili arama ağacının tüm özelliklerine sahiptir. Adını kurucuları Adelson-Velshi ve Landis’den alır. Veri bilimciler ve analistler, arama işlemlerini ve sık veri eklemenin gerekli olduğu durumlarda AVL ağaçlarını yaygın olarak kullanırlar. Linux çekirdeğinin bellek yönetimi alt sistemlerinde bulunur.
Kırmızı-Siyah Ağaç (Red-Black Tree)
AVL’ye benzer şekilde kırmızı-siyah ağaçlar, kendi kendini dengeleyen bir ikili arama ağacıdır. Tek fark, kırmızı-siyah bir ağaçtaki her düğümün kırmızı veya siyah olmasıdır. Bu düğümlerin rengi her değer eklediğinde veya çıkarıldığında ağacın kendi kendine dengeli kalmasını sağlar. Kırmızı-siyah ağacın kök Düğümü siyahtır. Kırmızı-Siyah ağaçtaki bir düğümden herhangi bir yaprak düğüme giden her yol, aynı sayıda siyah düğümden geçer. Hesaplama geometrisi bu tür ağaç veri yapısını kullanır.
Yaylı Ağaç (Splay Tree)
Kendi kendini dengeleyen başka bir ikili arama ağacı türü, yay ağacıdır. Veri bilimcileri ve analistleri, önbellek yönetimi ve çöp toplayıcıları (garbage collector) uygulamak için bir yayılma ağacı kullanır. Ekleme ve silme işlemini gerçekleştirdikten sonra yaylı ağaç devreye
girerek yayılma işlemini gerçekleştirir. Yayılma sırasında doldurulduğu bir ikili ağaçtır. Eksiksiz bir ikili ağaç, tam ağaç, belirli ögeler ağacın kökünde olacak şekilde yeniden ikili ağaç yapısına benzer düzenlenir. Çöp toplama (Garbage Collector), C# ve Java Bir ağaç yapısının eksiksiz ikili ağaç olabilmesi için iki gibi programlama dillerinde yerleşik olarak bulunan bir şart vardır; bellek kurtarma özelliğidir. B-Ağaç (B-Tree) • • B-Ağaç, verileri belirli bir sırada saklamak için birçok düğüm içeren kendi kendini dengeleyen başka bir arama ağacıdır. Her düğümün ikiden fazla alt düğümü vardır ve Dejenere Ağaç her düğüm birden fazla anahtar içerir. B-ağaçları, daha Yapıyı oluşturan düğümlerin, tek çocuğu olduğu ağaçtır. büyük veri bloklarını yazabilen ve okuyabilen dosya Çocuk düğümler sol veya sağ çocuk düğüm olabilir sistemleri ve veri tabanları ile uyumludur. Veri bilimcileri; B-Ağaç kullanarak verileri aramaya izin verecek, sıralı Çarpık İkili Ağaç (Skewed Binary Tree)
erişim sağlayacak ve logaritmik zamanda verilerin Çarpık ikili ağaç, tüm düğümlerin yalnızca bir çocuğu eklenmesine ve silinmesine izin verecek şekilde olduğu veya hiç sıralayabilir. Diskler gibi daha büyük depolama sistemleri, Dejenere ağaç yapısına benzer ancak bu yapıda tüm çocuk B-ağacı veri yapılarını kullanır. B-ağacındaki yapraklar düğümler aynı taraftan eklenmiştir. Çarpık ikili ağaçtaki hiçbir bilgi taşımazlar ve aynı seviyede görünürler. düğümler soldan eklenirse, Sola Eğik İkili Ağaç (Left Skewed Binary Treee), sağdan eklenirse Sağa Eğik Treap Ağacı (Treap Tree) Ağaç (Right Skewed Binary Tree) olarak adlandırılır.
Treap ağacı, bir ikili arama ağacı ve bir Heap birleşimidir. Treap adı İngilizce ağaç anlamına gelen “tree” ve öbek Dengeli İkili Ağaç (Balanced Binary Tree)
anlamına gelen “heap” sözcükleri kullanılarak oluşmuştur. Dengeli ikili ağaçlar, Yükseklik Dengeli İkili Ağaçlar Heap, öncelik sıralarını uygulayan ikili bir ağaçtır ve olarak da adlandırılır. Herhangi bir düğümün sol ve sağ alt bunları mantıksal olarak bir dizide saklayabilirsiniz. Treap ağacının yükseklik farkının 1’den fazla ağacındaki her düğümün iki değeri vardır: bir anahtar ve ağaç olarak tanımlanır. Bir ağacın dengeli ikili ağaç olarak bir öncelik. Treap, rastgele bir ikili arama ağacı adlandırılması için gereken koşullar aşağıda verilmiştir. oluşturmak için mükemmel bir veri yapısıdır. Diğer ağaç 1. veri yapılarından farklı olarak treap, yönetim ve karmaşık algoritmalar gerektirmeyen kendi kendini organize eden 2. bir yapıdır. 3. İkili Ağaçlar Ağacın dengeli olabilmesi için her düğümün sol ve sağ
Bilgisayar bilimlerinde en çok kullanılan ağaç yapısı ise çocuklarının yüksekliklerinin farkı alınmalıdır İkili Ağaçlar (Binary Trees) olarak adlandırılır. Daha önce de belirtildiği gibi ikili ağaçlar, düğümlerin en fazla iki İkili Arama Ağaçları (Binary Search Tree)
çocuk düğüme sahip olabildiği yapılardır. İkili arama ağacı; mevcut düğümün değerinden düşük değerli verilerin sol ço İkili ağaç yapısı için ilave olarak 2 tane daha terim vardır. verilerin ise sağ çocuk düğümlerde depolandığı bir ikili Bunlar; ebeveyn düğümün alt düğümlerini ifade eden, sol ağaçtır. Özel bir ikili ağaç türü olan ikili arama ağacında düğüm (left node) ve sağ düğüm (right node) terimleridir. verilerin ağaca eklenme sırası da önemlidir. İkili arama Aynı zamanda sol çocuk düğüm ve sağ çocuk düğüm ağaçlarının olarak da adlandırılırlar. İkili ağaç yapıları, düğümlerin verilebilir. yerleşimine göre farklı gruplara ayrılmıştır. Grupları kelimeden itibaren aranan kelimeyi bulana kadar sıra ile belirleyen faktör, çocuk düğümlerin ağaçtaki dağılımıdır. gidilebilir ancak aranan kelime, sözlüğün ortalarında veya Bu gruplardan popüler olanların bazıları şu şekildedir: sonlarında ise arama işlemi oldukça fazla zaman alacaktır. Tam İkili Ağaç (Full Binary Tree) Arama işlemi yaparken daha p Tüm düğümlerin çocuk sayısı, iki veya sıfır olan ağaçlar, olarak, sözlükten rastgele bir sayfa açılır ve bir kelime Tam İkili Ağaç Yapısı olarak adlandırılır. seçilir. Aranan kelime, alfabetik olarak, seçilen kelimeden sonra geliyorsa kalan sayfalara bakılır. Önce geliyorsa Mükemmel İkili Ağaç (Perfect Binary Tree) öndeki sayfalara bakılır. Aranan kelime bulunana ka
Mükemmel bir ikili ağaç, her dahili düğümün tam olarak işlem tekrar edilir. İki farklı arama tekniği incelenecek iki alt düğüme sahip olduğu ve tüm yaprak düğümlerinin olursa ikinci aramanın çok daha hızlı olduğu görülecektir aynı seviyede olduğu bir ikili ağaç türüdür. Zaman Karmaşıklığı
Eksiksiz İkili Ağaç (Completely Binary Tree) Yukarıda verilen sözlük örneği incelendiğinde ilk arama
Eksiksiz bir ikili ağaç, çocuk düğümleri soldan doldurulan tekniğinin zaman karmaşıklığının O(n) olduğu en düşük seviye hariç tüm seviyelerin tamamen anlaşılır çünkü veri sayısı arttıkça arama süresi artar. İkili
.
Tüm yaprak elemanları sola doğru yaslanmalıdır. Son düğümün tek çocuk düğümü varsa bu sağ çocuk olamaz.
.
çocuğu olmadığı bir tür ikili ağaçtır.
İkili
olmadığı bir ikili
Herhangi bir düğüm için sol ve sağ alt ağaç arasındaki fark birden fazla olmamalıdır. Sol alt ağaç dengeli olmalıdır. Sağ alt ağaç dengeli olmalıdır.
.
cuk düğümlerde, büyük değerli
çalışmasına günlük yaşamdan örnekler Örneğin, sözlükte bir kelimeyi ararken ilk
ratik bir yol daha vardır. İlk
dar bu
.
kolayca
arama ağacında ise durum biraz daha farklıdır. İkili arama ağaçlarında süreyi ağacın yüksekliği belirler. Aranan ögeye en fazla ağacın yüksekliği kadar adımda ulaşılabilir. Ağacın yüksekliğine h dersek ikili arama ağacının zaman karmaşıklığı O(h) olacaktır.
İkili arama ağaçlarının avantajlarını listeleyecek olursak;
• Arama işlemi çok hızlıdır. • Ağacın temsili basit ve kolaydır. • Ebeveynden çocuk düğüme veya tersi yönde geçişler kolaydır. • Uygulaması basittir. • Veri setinde mevcut olan yapısal ilişkileri yansıtır. • Verileri sıralı eklemek diğer veri yapılarına göre daha kolaydır. • Verileri hafızada saklamak kolaydır. • Sayıları depolarken kapasite sınırı yoktur. İkili arama ağaçlarının dezavantajları ise aşağıdakiler gibidir; • Düğüm silme işlemi zordur. • Verilere rastgele erişim işlemi diziden daha zordur. İndeks kullanılarak verilere erişilemez. • Temel operasyonlar ağacın yüksekliğine bağlıdır.
İkili Arama Ağacı Oluşturma
Düğümde verilerin yanında sağ ve sol çocuk düğümler için alan ayrılmıştır. Bunun yanında düğümde saklanan verileri görebilmek için DugumYazdir yöntemi eklenmiştir. Düğümde veriler tam sayı olarak tutulacaktır ancak depolanmak istenilen veri türü değiştirilebilir. Düğüm oluşturulduktan sonra İkili arama ağacı yani BST sınıfı oluşturulabilir. Bu ünitenin devam eden konularında BST ikili arama ağacını belirtmek için kullanılacakır. Sınıf yalnızca ağacın kök düğümü temsil ettiği öge ile oluşturulur. Varsayılan yapısı yöntemi ile boş bir kök düğümü oluşturulur. Ağaç yapımıza yeni düğümler eklemek için Ekle yöntemi hazırlanmıştır. Yöntemdeki ilk adım, bir Dugum nesnesi oluşturmak ve depolanacak veriyi düğüme kaydetmektir. Düğümü oluşturduktan sonraki adım ise bu düğümün kök olup olmadığını belirlemektir. Bu adımda kök düğümü boş(null) ise yeni düğümü kök olarak atayıp ekleme işlemi sonlandırılır. Kök düğüm boş değilse bir sonraki aşamaya geçilir. Bu aşamada, eklenecek değerin konumunun belirlenmesi için ağaç yapısındaki düğümlerin değerleri ile karşılaştırma yapılmalı. Bağlantılı listelerdeki gezinmeye benzer bir gezinmeyi bu aşamada gerçekleştireceğiz. İlk olarak kök düğümüne depolanan değer ile eklenecek değer karşılaştırılıyor. Eğer kök düğümünden küçük ise ağacın sol çocuk düğümüne, büyük ise sağ çocuk düğümüne geçiliyor. Bu işlem, geçilen seviyedeki düğüm boş olana kadar devam eder. Boş düğüm yakalandığında yeni düğüm buraya eklenir ve program çalışması sonlandırılır.
İkili Arama Ağacında Gezinme (Traversal)
Verileri depolayabileceğimiz ikili arama ağacını oluşturduktan sonra düğümleri gezerek verilere
ulaşabileceğimiz yöntemleri geliştirebiliriz. İkili arama ağaçlarında, kökün gösterilme sırasına göre üç farklı şekilde gezinme yapılabilir. Gezinmede kullanılan yöntemler; kökün çocuklardan önce gösterildiği Önce Kök(prefix), kökün çocuklardan sonra gösterildiği Sonra Kök(postfix) ve kökün çocuklar içinde gösterildiği İç Kök(infix) olarak adlandırılır. Bu üç yöntem de hangi çocuğun öncelikli olduğunu belirten 2 farklı alt yönteme ayrılmıştır. Yöntemler aşağıdaki gibi listelenebilir;
Gezinme yöntemlerinin kullanımları kolay ve anlaşılırdır. Önce Kök ve Sonra Kök yöntemleri düğüm silme gibi işlemlerde sıklıkla kullanılmaktadır. İç Kök ile gezinme ise daha çok ağaç yapısındaki verileri sıralamak için kullanılabilir. Verileri küçükten büyüğe sıralamak için Sol-Kök-Sağ yöntemi, büyükten küçüğe sıralamak için ise Sağ-Kök-Sol yöntemleri kullanılabilir. Gezinme yöntemlerini incelemeye İç Kök yöntemini hazırlayarak başlayabiliriz. Yöntemi yazarken özyinelemeli (recursive) fonksiyona ihtiyacımız olacaktır. IcKok yöntemi ilk, parametre olarak kök düğümünü aldıktan sonra ağacın sol çocuk ağacını gezer. Sol çocuk ağacı içerisindeki tüm elemanları yazdırdıktan sonra kök düğümünü yazdırır ve ardından ağacın sağ çocuk ağacı içindeki elemanları yazdırır.
Değer Bulma İşlemleri
İkili arama ağacında veriler sıralı olarak tutulduğu için değer bulma işlemleri oldukça basittir. Özellikle en küçük ve en büyük değerlerin yeri oldukça kolay tespit edilebilir.
En Küçük Sayıyı Bulma
İkili arama ağacına veri eklenirken veri mevcut düğümün verisinden küçük ise sol alt ağaca yönelinir. Ağaç üzerindeki en küçük değer, bu özellik kullanılarak kolayca tespit edilebilir. Bir ikili ağacın en küçük verisi, her zaman en soldaki düğümde bulunan değerdir. Bu değere ulaşmak için Kök->Sol Çocuk->Sol Çocuk->Sol Çocuk… rotası takip edilebilir. Mevcut düğümün Sol Çocuk alanı boş olarak işaretli ise en küçük değere ulaşılmıştır.
En Büyük Sayıyı Bulma
İkili arama ağacında, en küçük sayının en soldaki düğüme yerleştirilmesi gibi, en büyük sayıda en sağdaki düğüme yerleştirilir. EnKucukBul yöntemine benzer bir yöntemi, en büyük sayıyı bulmak için yazabiliriz. Bu kez Kök->Sağ Çocuk->Sağ Çocuk->Sağ Çocuk… rotası izlenmelidir. Yöntemin içinde yapmamız gereken tek değişiklik ise Sol Çocuk Düğümü kontrolü yerine Sağ Çocuk Düğümünün kontrol etmektir.
Değer Bulma
İkili arama ağaçlarında inceleyeceğimiz son değer bulma yöntemi, verilen bir sayının ağaç yapısında olup olmadığını kontrol edecektir. Aradığımız değeri bulmak için kullanacağımız Bul metodu, parametre olarak bir değer alır. İlk olarak yeni bir Dugum oluşturur ve kök değerine eşitler. Kök düğümünden başlayarak mevcut değer ile aranan değeri karşılaştırır. Aranan değer mevcut
düğümün verisinden küçükse mevcut düğümün sol çocuk düğümüne, büyükse sağ çocuk düğümüne geçer ve mevcut düğümü çocuk düğümüne eşitler. Bu işlem, aranan değer ile mevcut düğümün değeri eşit olana kadar veya mevcut düğüm boş olana kadar devam eder. Bul metodu aranan değer, ağaçta depolanıyorsa değeri döndürür. Depolanan değer arasında yoksa boş(null) döner.
İkili Arama Ağacında Düğüm Silme
İkili arama ağacında şimdiye kadar incelediğimiz ekleme, gezinme, bulma yöntemleri, kolayca kodlanabilen işlemlerdi. Düğüm silme işlemi ise diğer yöntemlere nazaran biraz daha zor bir operasyondur. Silinecek düğüm, yaprak düğüm ise ağaç yapısını bozmayacağı için kaldırılması kolay olabilir ancak silinecek düğüm, kök düğümse veya çocuk düğüme sahip ise ağaç yapısı bozulabilir. Kodlama işleminin dikkatli yapılması gerekir. Ağaç yapısında silme işlemi, düğümün farklı konumlarına göre adım adım incelenecektir.
Yaprak Düğümü Çıkarma
İkili arama ağacı yapısından en kolay çıkartılacak düğüm, hiç çocuk düğüme sahip olmayan yaprak düğümlerdir. Yaprak düğümü silmek için ebeveyn düğümün silinecek hedefi gösteren alanını boş olarak atamak yeterlidir. Bu işlemden sonra yaprak düğüm ağaç yapısı üzerinden kaybolacaktır.
Tek Çocuklu Bir Düğümü Çıkarma
Silinecek veri, yaprak düğüm yerine ağacın farklı noktalarında da bulunabilir. Daha önce hazırladığınız Sil metodunu geliştirerek tek çocuklu düğümleri çıkarabilmeyi sağlayacağız. Silinecek düğümün, tek çocuğu olduğunda kontrol edilmesi gereken dört koşul vardır.
1. Düğümün çocuğu sol çocuk olabilir. 2. Düğümün çocuğu sağ çocuk olabilir. 3. Silinecek düğüm, ebeveyn düğümün sol düğümü olabilir. 4. Silinecek düğüm, ebeveyn düğümün sağ düğümü olabilir
İki Çocuklu Bir Düğümü Silme
Bu bölüme kadar ikili arama ağacında çocuk düğümü olmayan veya tek çocuklu düğümleri kaldırdık. İki çocuk düğümü de dolu olan ögeleri kaldırmak, daha önceki kaldırma yöntemlerine göre biraz daha farklıdır. Öge kaldırıldıktan sonra yerine atanacak varis düğümün belirlenmesi gerekir. Varis belirleme işlemi için iki aday vardır. Bunlardan ilki, sol çocukların en sağındaki düğüm, diğeri ise sağ çocukların en solundaki düğümdür. Kaldırılan düğümün yerine bu iki düğümden birisi konursa ikili arama ağacının yapısı bozulmayacaktır.
VarisDugum metodunun çalışmasını adım adım incelemekte fayda var;
1. Metot ilk olarak ebeveyn ve varis düğümlerini, silinecek düğüme eşitleyerek başlar. mevcut
düğüm ise silinecek düğümün sağ çocuğuna eşitlenir. Bu sağ çocukların en küçüğünün varis olarak seçileceğini gösterir. 2. while döngüsü içerisinde algoritma adım adım, en soldaki düğüme ulaşmaya çalışır. mevcut düğüm boş olduğunda algoritma en sol düğüme ulaştı demektir. Buradaki en sol düğüm ikili arama ağacının en solu değil, silinecek düğümün sağ çocuklarının en soludur. 3. En soldaki düğüme ulaşıldıktan sonra varisin taşıma işlemi yapılır. Taşıma işleminde varisin silinecek düğümün sağ çocuğu olup olmadığı kontrol edilmelidir. Eğer sağ çocuk varis değil ise yapılması gereken iki işlem vardır. Bunlardan ilki, varisin ebeveyn düğümünden kaldırılmasıdır. Bu işlem yapılmadığında ikili ağaç yapısı kendisini tekrar edecektir. Bu kaldırma işlemi için varsa varisin sağ çocuk ağacı, ebeveynin sol çocuk ağacına atanır. Varisin sağ çocuk alanına ise silinecek düğümün sağ çocuk alanı atanır. 4. Varis düğümü return ile geri döndürülür.
VarisDugum metodu ile işimiz tamamlandıktan sonra Sil metodunda iki çocuklu düğümü silmek için gereken kodları yazabiliriz. Bu aşamada kontrol edilmesi gereken üç durum vardır;
1. Silinecek düğüm, kök düğüm olabilir. Varis kök düğüm olarak atanır. 2. Silinecek düğüm, ebeveyn düğümünün sol çocuğu olabilir. Ebeveynin sol çocuk alanına varis atanır. 3. Silinecek düğüm, ebeveyn düğümünün sağ çocuğu olabilir. Ebeveynin sağ çocuk alanına varis atanır. Varis düğümünün sağ çocuğu ile ilgili işlemler VarisDugum metodunda yapılmıştı. Sol çocuğuna ise silinecek düğümün sol çocuğu atanarak silme işlemi tamamlanır.