Yığın, bir öğenin içinde olup olmadığını (O (logN) zaman karmaşıklığıyla birlikte aramak için kullanılabileceğini hatırlıyorum. Ama aniden detayları alamıyorum. Sadece getmin delete add ve benzerlerini bulabilirim.Öğede yığın halinde arama
Herkes bir ipucu verebilir mi?
Bir öğenin içeride olup olmadığını belirlemek için öbek içindeki her öğeyi aramanız gerekir.
Ancak bir optimizasyon mümkündür (burada en yüksek yığını varsayalım). Aradığınız öğeden daha düşük bir değere sahip bir düğüme eriştiyseniz, o düğümden daha fazla arama yapmanız gerekmez. Bununla birlikte, bu optimizasyonda bile arama hala O (N) 'dir (N/2 düğümlerini ortalama olarak kontrol etmek gerekir).
Aradığınız şeyin bir BST (ikili arama ağacı) olduğunu düşünüyorum.
Öncelikli bir sıranız varsa ve belirli bir öğe içerip içermediğini kontrol etmek istiyorsanız yardımcı olmaz. – finnw
Bu tamamen doğru mu? Örnek olarak aşağıdaki Yığını alın: '[5, 4, 1, 3]' Bu yığının (bir dizi biçiminde) 3 numaralı sayı için ararsam, 1'e basarım ve algoritmanıza göre burada durun. gerçekte olduğu zaman sonuç olarak yığın içinde değil mi? Burada bir şey mi eksik? –
Optimizasyon ile, kök 1'e sahip alt ağaç, daha fazla arama yapılamayacaktır, çünkü 3, başka bir alt ağaçta yer almaktadır. Doğrusal bir aramanın (özyineleşen bir tersine) yanlış bir cevap verebileceğini kabul ediyorum. –
@JamesSanders Doğrusal arama için bile her durumda geçerlidir. Tam ikili ağaç, 4'lük bir sol alt öğe olarak 3 değerine sahip olacak ve 1, 4 ile aynı yükseklikte olacaktır. Doğrusal bir arama yapıyor olsanız bile, en iyi duruma getirme işlemi 4> 3 olduğunu, dolayısıyla en azında olması gerektiğini söyler. , 4 ile aynı yükseklikte tüm diğer öğelere ek olarak, 4 çocuklarını karşılaştırın. – lee