Video: İkili Arama Ağaçları (Binary Search Tree) Veri Yapıları 10 2024
Özel bir ağaç yapısı, ikili öbek olup düğüm öğelerinin her birini özel bir sıraya yerleştirir. Arama ağaçları, verileri hızlıca aramanıza izin verir. Veri öğelerini edinmek, onları ağaçta sıralı bir sıraya yerleştirmek ve daha sonra bu ağacı aramak bilgi bulmanın en hızlı yollarından biridir.
Bir ikili yığında, kök düğüm her zaman en küçük değeri içerir. Dalları görüntülediğinizde üst düzey dalların her zaman alt düzey dal ve yapraklardan daha küçük bir değer olduğunu görürsünüz. Etki, ağacın dengeli tutulmasını ve öngörülebilir bir sırayla bulunmasını sağlar, böylece arama son derece verimli olur. Maliyet, ağacın dengeli tutulması içindir.
Uygulamaların yaptığı tüm görevler arasında arama yapmak, daha fazla zaman alıcı ve en çok ihtiyaç duyulan arama demektir. Verileri ekleme (ve daha sonra sıralama) biraz zaman gerektirse de, bir veri kümesinin oluşturulması ve sürdürülmesinin faydası, onu yararlı bir işi yapmak için kullanmanızdır; bu, önemli bilgileri aramak demektir. Sonuç olarak, bazen daha az verimli CRUD işlevselliği ve hatta daha az optimal sıralama yordamı ile uğraşabilirsiniz, ancak aramalar mümkün olduğunca verimli şekilde ilerlemelidir. Tek sorun, hiçbir arama mutlak verimlilikle her görevi yerine getirmediğinden, seçeneklerinizi arama rutinlerinin bir parçası olarak ne beklediğinize göre tartmanız gerekir.
İkili arama ağacı (BST) ve ikili yığın kullanımını içeren daha verimli iki arama yöntemi. Her iki arama tekniği, veri öğelerine erişmek için kullanılan anahtarları tutan ağaç benzeri bir yapıya dayanır. Bununla birlikte, iki yöntemin düzenlemesi farklıdır, bu nedenle bazılarının belirli görevleri yerine getirirken diğerine göre avantajları vardır. Bu şekil bir BST için düzenlemeyi gösterir.
Tuşların, solda daha az sayı, sağda daha büyük sayıların bulunduğu bir sırayı nasıl izlediğinizi not edin. Kök düğüm, anahtar aralığının ortasında olan ve BST'ye anahtarları depolamak için kolayca anlaşılmış dengeli bir yaklaşım sağlayan bir değer içerir. Bu düzenlemeyi burada gösterilen ikili yığının aksine karşılaştırın.
Her seviye bir önceki seviyeden daha düşük değerleri içerir ve kök ağaç için maksimum anahtar değerini içerir. Buna ek olarak, bu özel durumda, daha az değerler soldaki ve sağdaki daha büyük olarak görünür (bu düzen sıkı bir şekilde uygulanmaz). Şekilde aslında ikili maksimum yığın tasvir edilmiştir. Ayrıca, kökün en düşük anahtar değerini içerdiği ve her bir düzeyin yaprakların bir parçası olarak görünen en yüksek değerlerle daha yüksek değerlere inşa ettiği bir ikili min öbek yığıtı oluşturabilirsiniz.
Daha önce de belirtildiği gibi, BST, bir arama yapmak için kullanıldığında ikili öbek üzerinde bazı avantajlara sahiptir. Aşağıdaki liste, bu avantajların bazı önemli noktalarını sunmaktadır:
- Bir öğe aramak, bir ikili öbek için O (n) zamanının aksine O (log n) zamanını gerektirir.
- Sırayla öğeleri yazdırmak, bir ikili öbek için O (n log n) zamanının aksine yalnızca O (log n) zamanını gerektirir.
- Yer ve tavan bulmak, O (log n) zamanını gerektirir.
- Kth. En küçük / en büyük öğenin bulunması, ağaç doğru yapılandırıldığında O (log n) zamanını gerektirir.
Bu zamanların önemli olup olmadığı uygulamanıza bağlıdır. BST, arama yapmak için daha fazla vakit geçirdiğiniz durumlarda ve ağacın inşasına daha az zaman ayırdığınız durumlarda en iyi sonucu verir. Bir ikili yığın, anahtarların düzenli olarak değiştiği dinamik durumlarda en iyi çalışmaya eğilim gösterir. İkili yığın, aşağıdaki listede açıklandığı gibi avantajlar da sunar:
- Gerekli yapıları oluşturmak, daha az kaynak gerektirir, çünkü ikili yığınlar dizilere güvenir ve onları önbellekle daha uyumlu hale getirir.
- İkili yığın oluşturmak, O (n log n) zaman gerektiren BST ile karşılaştırıldığında O (n) zaman gerektirir.
- Ağacı uygulamak için işaretçiler kullanmak gerekli değildir.
- İkili yığın varyasyonlarına (örneğin, Fibonacci Yığını) güvenmek O (1) zamanın anahtar zamanlarını artırmak ve azaltmak gibi avantajlar sağlar.
