İkili Arama Ağacı, verileri düzenlememize ve sıralamamıza destek olan çeşitli veri yapılarından biridir. Verileri bir hiyerarşide depolamanın etkili bir yoludur ve oldukca esnektir.
Bu makalede, özellikleri ve uygulamalarıyla beraber iyi mi çalıştığına daha yakından bakacağız.
İkili Arama Ağacı Nedir?
Fotoğraf Kredisi: Pat Hawks/Wikimedia Commons
İkili Arama Ağacı, Bağlı Listelere benzer şekilde düğümlerden oluşan bir veri yapısıdır. İki tür düğüm olabilir: alt ve üst düğüm. Kök düğüm, sol düğüm ve sağ düğüm olarak adlandırılan iki alt düğüme dallanma yapısının başlangıç noktasıdır.
Her düğüme yalnızca üst öğesi tarafınca başvurulabilir ve yöne bağlı olarak ağacın düğümlerinden geçebiliriz. İkili Arama Ağacı’nın üç ana özelliği vardır:
- Sol düğüm üst düğümünden daha ufak.
- Sağ düğüm üst düğümden büyük.
- Sol ve sağ alt ağaçlar İkili Arama Ağaçları olmalıdır.
Tüm düzeyler dolduğunda ve her düğümün bir sol ve sağ alt düğümü olduğunda Muhteşem İkili Arama Ağacı elde edilir.
İkili Arama Ağacının Temel İşlemleri
Artık İkili Arama Ağacı’nın ne olduğu hakkında daha iyi bir fikriniz var, aşağıdaki temel işlemlerine bakabiliriz.
1. Arama İşlemi
Arama, ağaçta bulunan belirli bir kıymeti bulmamızı sağlar. İki tür arama kullanabiliriz: genişlik-ilk arama (BFS) ve derinlik-ilk arama (DFS). Genişlik-ilk arama, kök düğümden süregelen ve hedef bulunana kadar yatay olarak, yana doğru geçiş meydana getiren bir arama algoritmasıdır. Her düğüm bu arama esnasında bir kez ziyaret edilir.
Öte taraftan, derinlik ilkin arama, kök düğümden başlayarak ve tek bir dalda emek vererek ağacı dikey olarak geçer. Amaç bulunursa, işlem sonlanmış olur. Sadece değilse, öteki düğümleri arar.
2. Ekleme İşlemi
Ekleme işlemi, yeni düğümün eklenmesi ihtiyaç duyulan konumu belirlemek için arama işlemini kullanır. İşlem kök düğümden adım atar ve hedefe ulaşılana kadar arama adım atar. Ekleme ile dikkate alınması ihtiyaç duyulan üç durum vardır.
- Durum 1: Düğüm olmadığında. Eklenecek düğüm kök düğüm olacaktır.
- Dava 2: Çocuk yok. Bu durumda, düğüm kök düğümle karşılaştırılacaktır. Daha büyükse, doğru çocuk olacaktır; aksi takdirde, sol çocuk olacak.
- Durum 3: Kök ve evlatları mevcut olduğunda. Yeni düğüm, sonraki düğümü ziyaret ettiğini belirlemek için yolundaki her düğümle karşılaştırılacaktır. Düğüm kök düğümden büyükse, sağ alt ağaçtan yada soldan aşağı doğru geçiş yapmış olacaktır. 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. Silme, bir düğümü kaldırdıktan sonrasında ağacın buna gore tekrardan düzenlenmesi gerektiği için zor olarak kabul edilir. Dikkate alınması ihtiyaç duyulan üç ana durum vardır:
- Durum 1: Yaprak düğümü siliniyor. Yaprak düğümü, alt öğesi olmayan bir düğümdür. Bu, başka bir düğümü etkilemediği için kaldırılması en kolay olandır; yalnız ulaşana ve silene kadar ağacı geçeriz.
- Durum 2: Bir alt öğeyle düğüm siliniyor. Bir düğümü olan bir üst öğeyi silmek, çocuğun konumunu almasına niçin olur ve sonraki tüm düğümler bir düzey yukarı göç eder. Ağaçların alt yapısında herhangi bir değişim olmayacaktır.
- Durum 3: İki alt düğüm içeren bir düğümü silme. İki alt öğesi olan bir düğümü kaldırmamız gerektiğinde, ilkin konumunu alabilen sonraki bir düğüm bulmalıyız. kaldırılan düğümün yerini iki düğüm alabilir, inorder ardılı yada öncülü. Sıralayıcı ardılı sağ alt ağacın en soldaki alt öğedir ve inorder öncülü sol alt ağacın en sağ alt alt öğedir. Ardıl/öncül içeriğini düğüme kopyalıyoruz ve inorder halefini/öncülüni sileriz.
İkili Arama Ağacında Iyi mi Geçnişi
Geçiş, İkili Arama Ağacı’nda gezindiğimiz işlemdir. Belirli bir öğeyi bulmak yada ağacın anahattını yazdırmak için yapılır. Daima kök düğümden başlarız ve öteki düğümlere ulaşmak için kenarları takip etmeliyiz. Her düğüm bir alt ağaç olarak kabul edilmelidir ve tüm düğümler ziyaret edilene kadar işlem yinelenir.
- Sıralı Geçiş: Sırayla geçiş, artan sırada bir harita üretecektir. Bu yöntemle, sol alt ağaçtan başlayıp kök ve sağ alt ağacına devam ediyoruz.
- Çapraz Geçiş Için Ön Sipariş: Bu yöntemde, kök düğüm ilkin ziyaret edilir, peşinden sol alt ağaç ve sağ alt ağaç.
- Sipariş Sonrası Geçiş: Bu geçiş, kök düğümü son olarak ziyaret etmeyi ihtiva eder. Ilkin sol alt ağaçtan, sonrasında sağ alt ağaçtan ve sonrasında kök düğümden başlarız.
Gerçek Dünya Uygulamaları
Peki, ikili arama ağacı algoritmalarını iyi mi kullanırız? Tahmin edilebilir, arama ve sıralamada son aşama verimlidirler. İkili ağaçların en büyük gücü organize yapılarıdır. Çözümleme etmemiz ihtiyaç duyulan veri miktarını geçiş başına yarı yarıya azaltarak aramanın dikkat çekici hızlarda yapılmasını sağlar.
İkili Arama Ağaçları, dinamik olarak değişen bir veri kümesini tertipli bir halde verimli bir halde korumamızı sağlar. Sık sık veri eklenen ve kaldırılan uygulamalar için oldukca yararlıdır. Video oyun motorları, nesneleri tertipli olarak işlemeye destek olmak için ikili alan kısmı olarak malum ağaçları temel alan bir algoritma kullanır. Microsoft Excel ve bir çok elektronik tablo yazılımı, temel veri yapısı olarak ikili ağaçları kullanır.
Mors alfabesi verileri kodlamak için ikili arama ağacı kullandığını bilmek sizi şaşırtabilir. İkili Arama Ağaçlarının bu kadar yararlı olmasının bir başka mühim sebebi de çoklu varyasyonlarıdır. Esneklikleri, her türlü problemi çözmek için oldukca sayıda varyant oluşturulmasına yol açmıştır. Muntazam kullanıldığında, İkili Arama Ağaçları mükemmel bir varlıktır.
İkili Arama Ağaçları: Muhteşem Başlangıç Noktası
Bir mühendisin uzmanlığını ölçmenin ana yollarından biri, veri yapılarını tanımaları ve uygulamalarıdır. Veri yapıları yararlıdır ve daha verimli bir sistem oluşturmanıza destek olabilir. İkili Arama Ağaçları, herhangi bir geliştirici için veri yapılarına mükemmel bir giriştir.