JavaScript ile Binary Search Tree
Ağaç, kolayca bulunması gereken verilerin depolanmasında son derece yararlı olan sıralı olmayan bir veri yapısıdır.Ağaç, bir hiyerarşide depolanan verileri temsil eden soyut bir modeldir.
Çok yaygın bir örnek, organizasyon hiyerarşisini gösteren bir aile ağacıdır.Bir ağaç, üst-alt ilişkileri olan düğümlerden (veriler) oluşur. Her düğüm bir ebeveynden (üst veya kök düğüm hariç) oluşur ve her düğümün sıfır veya iki çocuğu olabilir. Ağacın her bir öğesine düğüm, ağacın üst düğümü ise herhangi bir ebeveyn içermediği için kök olarak adlandırılır. Bir ağaçta mevcut iç ve dış düğümler vardır. En az bir çocuğu olan bir düğüme dahili düğüm adı verilir. Sıfır çocuğu olan bir düğüme harici düğüm veya yaprak denir.
Ağacın hiyerarşisi seviye ile temsil edilir. Kök eleman 0 seviyesindedir, çocukları 1. seviyededir vb. Ağaçtaki bir düğümün bir atası ve nesli olabilir. Düğümün ataları ebeveynler, büyük ebeveynler veya en üst düzey düğümlerdir. Düğümün torunları, çocuklar, torunlar veya düşük seviyeli düğümlerdir. Bir ağaç, kendi içinde tam bir ağaç olan ancak başka bir ana ağacın içinde bulunan bir alt ağaca da sahip olabilir. Herhangi bir düğümün derinliği, ataların sayısından oluşur ve ağacın yüksekliği, ataların 0. seviyeden veya kökten maksimum derinliğidir.
Binary Tree ile Binary Search Tree Arasındaki Farklar :
Binary Tree : Ağaçtaki bir düğümün biri solda diğeri sağda olmak üzere en fazla iki çocuğu olabilir. Verileri bu şekilde yapılandırmanın yolu bir ağaç oluşturmamıza yardımcı olur ve bunu kullanarak değerleri eklemek, aramak ve silmek için verimli algoritmalar yazabiliriz. Buna ikili ağaç denir.
Binary Search Tree :İkili arama ağacı, verileri sıralı bir sırayla depolayan ikili bir ağaçtır. Yalnızca solda daha az değerli düğümleri ve sağda daha büyük bir değere sahip düğümleri depolamamıza izin verir. İkili arama ağacı her zaman bir ikili ağaçtır, ancak bunun tersi her zaman doğru olamaz.
create bst :
insert :Ağaca bir düğüm eklemek için kontrol etmemiz gereken üç senaryo vardır.
- Kök öğe yoksa, köke ekleyin.
- Değerin kökünden küçük olup olmadığını ve sol düğümün boş olup olmadığını kontrol edin, ardından sola ekleyin, aksi takdirde aynı işlevi tekrar tekrar çağırarak bir seviyeye inin ve tekrar kontrol edin ve ekleyin vb.
- Değerin kökten daha büyük olup olmadığını ve sağ düğümün boş olup olmadığını kontrol edin, sonra onu ekleyin, yinelemeli olarak bir seviye alçaltın ve tekrar kontrol edin ve öğe doğru noktaya eklenene kadar devam edin.
find : Değerleri hem sol için hemde sağ için arama işlemi yapacağımız için yinelemeli (recursive) yapı kullanılmalı.
findMin :Daha küçük olan değer solda saklandığından, MİN değerini bulmak için en soldaki aşağıya ait verileri döndürmemiz gerekir.
findMax :Daha büyük değer sağ tarafta saklandıkça, MAKS değerini bulmak için en sağdaki soydan gelen verileri döndürmemiz gerekir.
remove :Bu en karmaşık yöntemlerden biridir çünkü bir düğümü kaldırırken birden çok durumu ele almamız gerekir. Bu tür karmaşık senaryoların üstesinden gelmek için, bunu etkili bir şekilde yönetmeye yardımcı olan bir yardımcı işlev kullanacağız. Bu yardımcı fonksiyon, atamalara ve sonunda köke atamamız gereken düğümü döndürecektir. Öncelikle, verilen anahtara sahip düğümün ağaçta olup olmadığını kontrol etmemiz gerekecek. Eğer bulunursa, ele almamız gereken dört farklı durum vardır.
- Ağaç boş ise
- Aradığımız değer root ise
- Aradığımız değer root değilse sola bakıcaz.
- Aradığımız değer root değilse sağa bakıcaz.
isPresent : Aradığımız Düğümün olup olmadığını kontrol eder.
Okuma işlemeri
Aranması gereken bir anahtar herhangi bir düğümde bulunabilir. Bu yüzden ağaçta olup olmadığını kontrol etmek için ağacın her bir düğümünü kontrol etmemiz gerekir. Bunun için, hem sol hem de sağ çocuğu kontrol edecek ve anahtar varsa doğru, aksi takdirde yanlış döndürecek olan aynı arama işlevini yinelemeli (recursicve) olarak çağıracağız.
1.Infix(inOrder) : Left->Node->Right || Right->Node->Left
2.Prefix(preOrder): Node->Left->Right || Node->Right->Left
3.Postfix(postOrder): Left->Right->Node || Right->Left->Node
read inOrder :
read preOrder :
read postOrder :
Bu içeriklerin devamı gelecek… JavaScript ile mutlu günler.
github :https://www.github.com/ckymn
linkedin :https://www.linkedin.com/in/ckymn/
Benim adım Muhammet,Türkiye’de Full Stack Developer’ım . Daha fazla makale için takip edin.🤓
