• Buradasın

    İkili arama ağacı yüksekliği nasıl hesaplanır?

    Yazeka

    Arama sonuçlarına göre oluşturuldu

    İkili arama ağacı yüksekliği, özyinelemeli bir fonksiyon kullanılarak hesaplanabilir 4. Bu fonksiyon, ağacın sol ve sağ alt dallarındaki düğümlerin yüksekliğini ayrı ayrı bulup, bu iki yükseklikten hangisi daha büyükse onu 1 ekleyerek geri döndürür 4.
    Örnek kod (C dili):
    struct node { int data; struct node* left; struct node* right; }; int height(struct node* node) { if (node == NULL) return 0; else { int left_height = height(node->left); int right_height = height(node->right); if (left_height > right_height) return(left_height + 1); else return(right_height + 1); } }
    Alternatif olarak, ikili arama ağacı yüksekliği, h(T) = max{h(TL), h(TR)} + 1 formülü ile de hesaplanabilir 3. Burada T ağacı, TL sol alt ağacı ve TR sağ alt ağacı ifade eder 3.
    5 kaynaktan alınan bilgiyle göre:

    Konuyla ilgili materyaller

    İkili arama algoritması nasıl çalışır?

    İkili arama algoritması, sıralı bir listede belirli bir değeri bulmak için şu adımları izler: 1. Listenin ortasındaki eleman alınır. 2. Bu eleman, aranan değerle karşılaştırılır. 3. Eğer eleman aranan değere eşitse, arama sona erer ve bulunan elemanın indeksi döndürülür. Eğer eleman aranan değerden küçükse, listenin sol yarısında arama yapılır. Eğer eleman aranan değerden büyükse, listenin sağ yarısında arama yapılır. 4. Liste daraltılarak 2. adımdan itibaren işlemler tekrar edilir. Bu yöntem, her adımda arama alanını yarıya indirdiği için oldukça hızlı çalışır. Örnek: 1001, 1010, 1023, 1034, 1050, 1075, 1100 şeklinde sıralı bir çalışan ID listesinde 1050 ID'sinin aranması: 1. Orta eleman 1050 (5. eleman) ile karşılaştırılır. 2. Aranan değer (1050) orta değere eşit olduğu için arama sona erer ve 5 değeri döndürülür. Dikkat edilmesi gerekenler: Listenin sıralı olması gerekir, aksi takdirde yanlış sonuçlar verir. Veri tiplerinin uyumlu olması gerekir (hepsi string veya hepsi integer olmalıdır). Tekrarlı elemanlarda, aynı değeri içeren birden fazla öğe varsa, genellikle bunlardan ilkini döndürür.

    İkili ve doğrusal arama arasındaki fark nedir?

    İkili ve doğrusal arama arasındaki temel farklar şunlardır: Zaman karmaşıklığı: Doğrusal aramanın zaman karmaşıklığı O(n) iken, ikili aramanın zaman karmaşıklığı O(log n)'dir. Ön koşul: Doğrusal arama, listenin sıralanmasını gerektirmezken, ikili arama yalnızca sıralanmış listelerde veya dizilerde kullanılabilir. Çalışma prensibi: Doğrusal arama, veri yapısındaki her öğeyi sırasıyla kontrol eder ve aranan öğeyi bulana kadar devam eder.