İkili Arama Ağacı, verileri düzenlememize ve sıralamamıza yardımcı olan çeşitli veri yapılarından biridir. Verileri bir hiyerarşide depolamanın etkili bir yoludur ve çok esnektir.
Bu makalede, özellikleri ve uygulamalarıyla birlikte nasıl çalıştığına daha yakından bakacağız.
İkili Arama Ağacı Nedir?
İkili Arama Ağacı, Bağlantılı Listelere benzer şekilde düğümlerden oluşan bir veri yapısıdır. İki tür düğüm olabilir: ebeveyn ve çocuk. Kök düğüm, sol düğüm ve sağ düğüm olarak adlandırılan iki alt düğüme ayrılan yapının başlangıç noktasıdır.
Her düğüme yalnızca ebeveyni tarafından başvurulabilir ve yöne bağlı olarak ağacın düğümlerini geçebiliriz. İkili Arama Ağacının üç ana özelliği vardır:
- Sol düğüm, ebeveyninden daha küçüktür.
- Sağ düğüm, ebeveyninden daha büyüktür.
- Sol ve sağ alt ağaçlar İkili Arama Ağaçları olmalıdır.
Mükemmel İkili Arama Ağacı, tüm seviyeler dolduğunda elde edilir ve her düğümün bir sol ve sağ alt düğümü vardır.
İlişkili: Her Veri Bilimcisinin Kullanması Gereken Python İçin Veri Bilimi Kitaplıkları
İkili Arama Ağacının Temel İşlemleri
Artık bir İkili Arama Ağacının ne olduğu hakkında daha iyi bir fikriniz var, aşağıda temel işlemlerine bakabiliriz.
1. Arama İşlemi
Arama, ağaçta bulunan belirli bir değeri bulmamızı sağlar. İki tür arama kullanabiliriz: genişlik öncelikli arama (BFS) ve derinlik öncelikli arama (DFS). Genişlik öncelikli arama, kök düğümde başlayan ve hedef bulunana kadar yatay olarak yan yana ilerleyen bir arama algoritmasıdır. Bu arama sırasında her düğüm bir kez ziyaret edilir.
Derinlik öncelikli arama ise, kök düğümden başlayarak ve tek bir dalda ilerleyerek ağaçta dikey olarak hareket eder. Hedef bulunursa, işlem sona erer. Ancak değilse, diğer düğümleri arar.
2. Ekleme İşlemi
Ekleme işlemi, yeni düğümün eklenmesi gereken konumu belirlemek için arama işlemini kullanır. İşlem kök düğümden başlar ve arama hedefe ulaşılana kadar başlar. Ekleme ile ilgili dikkate alınması gereken üç durum vardır.
- Durum 1: Hiçbir düğüm olmadığında. Eklenecek düğüm, kök düğüm olacaktır.
- Durum 2: Hiç çocuk yok. Bu durumda, düğüm kök düğümle karşılaştırılacaktır. Daha büyükse, doğru çocuk olur; aksi takdirde sol çocuk olur.
- Durum 3: Kök ve çocukları mevcut olduğunda. Yeni düğüm, daha sonra hangi düğümü ziyaret edeceğini belirlemek için yolundaki her düğümle karşılaştırılacaktır. Düğüm, kök düğümden daha büyükse, sağ alt ağaçtan aşağı doğru veya soldan geçecektir. Benzer şekilde, hedefine ulaşana kadar sağa mı yoksa sola mı gideceğini belirlemek için her düzeyde karşılaştırmalar yapılır.
3. İşlemi Sil
Silme işlemi, ağaç içindeki belirli bir düğümü kaldırmak için kullanılır. Bir düğümü kaldırdıktan sonra, ağacın buna göre yeniden düzenlenmesi gerektiğinden, silme işlemi zor kabul edilir. Göz önünde bulundurulması gereken üç ana durum vardır:
- Durum 1: Bir yaprak düğümün silinmesi. Yaprak düğüm, çocuğu olmayan bir düğümdür. Bu, diğer düğümleri etkilemediği için çıkarılması en kolay olanıdır; biz sadece ağaca ulaşana kadar dolaşıyoruz ve onu siliyoruz.
- Durum 2: Tek çocuklu bir düğümün silinmesi. Bir düğüme sahip bir ebeveyni silmek, çocuğun konumunu almasına neden olur ve sonraki tüm düğümler bir seviye yukarı hareket eder. Alt ağaç yapısında herhangi bir değişiklik olmayacaktır.
- Durum 3: İki çocuklu bir düğümün silinmesi. İki çocuklu bir düğümü kaldırmamız gerektiğinde, önce yerini alabilecek bir sonraki düğümü bulmalıyız. İki düğüm, kaldırılan düğümün yerini alabilir, sıralı halef veya öncül. Sıralı ardıl, sağ alt ağacın en soldaki çocuğu ve sıralı selefi, soldaki alt ağacın en sağdaki çocuğudur. Ardıl/öncülün içeriğini düğüme kopyalarız ve ardıl/öncülü sileriz.
İlişkili: JavaScript ES6 Sınıfları ile Veri Yapıları Nasıl Oluşturulur
İkili Arama Ağacında Geçiş Nasıl Yapılır?
Geçiş, bir İkili Arama Ağacında gezindiğimiz süreçtir. Belirli bir öğeyi bulmak veya ağacın ana hatlarını yazdırmak için yapılır. Her zaman kök düğümden başlarız ve diğer düğümlere ulaşmak için kenarları takip etmemiz gerekir. Her düğüm bir alt ağaç olarak düşünülmeli ve süreç tüm düğümler ziyaret edilene kadar tekrarlanır.
- Sipariş İçi Geçiş: Sıralı hareket, artan sırada bir harita üretecektir. Bu yöntemle sol alt ağaçtan başlayıp kök ve sağ alt ağaçtan devam ediyoruz.
- Ön Sipariş Geçişi: Bu yöntemde önce kök düğüm, ardından sol alt ağaç ve sağ alt ağaç ziyaret edilir.
- Sipariş Sonrası Geçiş: Bu geçiş, en son kök düğümü ziyaret etmeyi içerir. Sol alt ağaçtan, ardından sağ alt ağaçtan ve ardından kök düğümden başlıyoruz.
Gerçek Dünya Uygulamaları
Peki, ikili arama ağacı algoritmalarını nasıl kullanırız? Tahmin edilebileceği gibi, arama ve sıralama konusunda son derece verimlidirler. İkili ağaçların en büyük gücü organize yapılarıdır. Analiz etmemiz gereken veri miktarını geçiş başına yarı yarıya azaltarak aramanın olağanüstü hızlarda yapılmasını sağlar.
İkili Arama Ağaçları, dinamik olarak değişen bir veri kümesini organize bir biçimde verimli bir şekilde korumamızı sağlar. Sık sık veri eklenen ve kaldırılan uygulamalar için çok faydalıdır. Video oyun motorları, nesnelerin düzenli bir şekilde oluşturulmasına yardımcı olmak için ikili alan bölümü olarak bilinen ağaçlara dayalı bir algoritma kullanır. Microsoft Excel ve çoğu elektronik tablo yazılımı, temel veri yapısı olarak ikili ağaçları kullanır.
Mors kodunun verileri kodlamak için ikili bir arama ağacı kullandığını bilmek sizi şaşırtabilir. İkili Arama Ağaçlarının bu kadar yararlı olmasının bir diğer önemli nedeni de çoklu varyasyonlarıdır. Esneklikleri, her türlü sorunu çözmek için çok sayıda varyantın oluşturulmasına yol açmıştır. Doğru kullanıldığında, İkili Arama Ağaçları harika bir varlıktır.
İkili Arama Ağaçları: Mükemmel Başlangıç Noktası
Bir mühendisin uzmanlığını ölçmenin ana yollarından biri, bilgi ve veri yapılarının uygulanmasıdır. Veri yapıları faydalıdır ve daha verimli bir sistem oluşturmaya yardımcı olabilir. İkili Arama Ağaçları, yeni başlayan herhangi bir geliştirici için veri yapılarına harika bir giriş niteliğindedir.
JavaScript dizilerini anlamak istiyor ancak bunlarla başa çıkamıyor musunuz? Rehberlik için JavaScript dizisi örneklerimize bakın.
Sonrakini Oku
- Programlama
- Programlama
- Programlama Araçları
Maxwell, boş zamanlarında yazar olarak çalışan bir yazılım geliştiricisidir. Yapay zeka dünyasıyla uğraşmayı seven hevesli bir teknoloji meraklısı. İşiyle meşgul olmadığında, kitap okuyor veya video oyunları oynuyor.
Haber bültenimize abone ol
Teknik ipuçları, incelemeler, ücretsiz e-kitaplar ve özel fırsatlar için bültenimize katılın!
Abone olmak için buraya tıklayın