En Yaygın İkili Ağaç Mülakat Soruları ve Cevapları [Yeni Başlayanlar ve Deneyimliler İçin]

Tanıtım

Veri yapıları, nesne yönelimli programlamadaki en temel kavramlardan biridir. Basitçe açıklamak gerekirse, bir veri yapısı, bir bilgisayarda verilerin etkin bir şekilde işlenebilmesi için organize edilmesinin özel bir yoludur. Yığınlar, kuyruklar ve ağaçlar gibi kendine has özellikleri olan çeşitli veri yapıları vardır.

Ağaçlar, verileri hiyerarşik bir biçimde düzenlememizi sağlar. Böyle bir veri yapısı, bağlantılı listeler veya diziler gibi doğrusal veri yapılarından çok farklıdır. Bir ağaç, bilgi taşıyan düğümlerden oluşur.

İkili ağaç, yalnızca iki çocuğa sahip olabilen özel bir ağaç türüdür. Bu, bir ikili ağaçtaki belirli bir düğümün çocuğu, bir çocuğu veya iki çocuğu olabileceği, ancak daha fazla olamayacağı anlamına gelir. İkili ağaç, zor sorunları çözmemizi ve karmaşık kodlar oluşturmamızı sağlayan önemli bir veri yapısıdır.

Java Geliştiricisi veya yazılım mühendisi olarak bir işe başvuruyorsanız, görüşmeniz bu kavram etrafında dönen birkaç soru içerebilir. Adaylar genellikle ikili ağaçlara, ikili arama ağaçlarına ve ilgili programlara dayalı soruları yanıtlamakta zorlanırlar. Bu yazıda, ikili ağaçlarla ilgili en sık sorulan mülakat sorularından bazılarını inceleyeceğiz. Bu makale, konsepti daha iyi anlamanıza ve hayalinizdeki işi bulabilmeniz için sizi hazırlamanıza yardımcı olacak!

En İyi İkili Ağaç Mülakat Soruları ve Cevapları

Aşağıdaki bölüm, ikili ağaç kavramına dayalı olarak bir soru kataloğunu ve bunların beklenen yanıtlarını içerir.

1) Yaprak düğüm nedir?

İkili bir ağaçtaki veya hiç çocuğu olmayan bir ağaçtaki herhangi bir düğüme yaprak düğüm denir.

2) Kök düğüm nedir?

Bir ağaçtaki ilk düğüme veya en üstteki düğüme kök düğüm denir.

3) Java'da bir ikili ağacın en düşük ortak atasını (LCA) nasıl buluyorsunuz?

Bir ikili ağacın parçası olan n1 ve n2 düğümlerini ele alalım.

n1 ve n2'nin en düşük ortak atası (LCA), n1 ve n2'nin kökten en uzakta bulunan ortak atasıdır.

LCA'yı bulmak için aşağıdaki yöntemi takip edebilirsiniz.

1. a) Kök düğümden n1'e bir yol bulun ve bir dizide saklayın.
2. b) Kök düğümden n2'ye bir yol bulun ve bir dizide saklayın.
3. c) Her iki dizide de değer aynı olana kadar her iki yolu da geçin.

4) Belirli bir ikili ağacın başka bir ikili ağacın alt ağacı olup olmadığını nasıl kontrol edersiniz?

İkili bir T ağacımız olduğunu düşünün. Şimdi bir ikili ağaç S'nin T'nin bir alt ağacı olup olmadığını kontrol etmek istiyoruz.

Bunu yapmak için, önce T'de aynı zamanda S'de olan bir düğüm bulup bulmadığınızı kontrol etmeye çalışın.

Bu ortak düğümü bulduğunuzda, aşağıdaki düğümlerin de S'nin bir parçası olup olmadığını kontrol edin.

Evet ise, S'nin T'nin bir alt ağacı olduğunu güvenle söyleyebiliriz.

Mutlaka Okuyun: Veri Yapısı Proje Fikirleri ve Konuları

5) İkili bir ağaçta iki düğüm arasındaki mesafeyi nasıl buluyorsunuz?

İkili bir ağacın parçası olan iki düğüm n1 ve n2 düşünün.

n1 ve n2 arasındaki mesafe, bir düğümden diğerine ulaşmak için geçilmesi gereken minimum kenar sayısına eşittir.

Düğümler arasındaki en kısa mesafeyi geçtiğinize dikkat etmek önemlidir.

6) İkili arama ağacı nedir?

İkili arama ağacı (BST), her dahili düğümün bir anahtar içerdiği özel bir ikili ağaç türüdür. İkili arama ağacı için kural şudur:

1. a) Bir düğüm, düğümün sol alt ağacındaki tüm anahtarlardan daha büyük bir anahtara sahip olabilir.
2. b) Bir düğüm, düğümün sağ alt ağacındaki tüm anahtarlardan daha küçük bir anahtara sahip olabilir.

Dolayısıyla, n1, 8 anahtarına sahip bir düğümse, n1'in sol alt ağacındaki her düğüm 8'den küçük anahtarlar içerecek ve n1'in sağ alt ağacındaki her düğüm 8'den büyük anahtarlar içerecektir.

7) Kendi kendini dengeleyen ağaç nedir?

Kendinden dengeli ikili arama ağaçları, ekleme ve silme gibi işlemler gerçekleştiğinde yüksekliklerini otomatik olarak mümkün olduğunca küçük tutar.

Bir BST'nin kendi kendini dengeleyebilmesi için, BST'nin kurallarına sürekli olarak uyması önemlidir, böylece sol alt ağaç daha düşük değerli anahtarlara sahipken, sağ alt ağaç yüksek değerli anahtarlara sahip olur.

Bu, iki işlem kullanılarak yapılır:

– Sola dönüş

– Sağ dönüş

8) AVL ağacı nedir?

AVL ağacı adını mucitlerinden almıştır: Adelson, Velski ve Landis. Bir AVL ağacı, sol alt ağacının ve sağ alt ağacının yüksekliğini kontrol eden ve farkın 1'den fazla olmadığını garanti eden, kendi kendini dengeleyen bir ikili ağaçtır. Bu farka denge faktörü denir.

Böylece, BalanceFactor = yükseklik (Sol alt ağaç) – yükseklik (Sağ alt ağaç)

Denge faktörü 1'den fazlaysa, ağaç aşağıdaki tekniklerden bazıları kullanılarak dengelenir:

– Sola dönüş

– Sağ dönüş

– Sol-Sağ dönüş

– Sağ-Sağ rotasyon

Ayrıca Okuyun: Veri Yapısında Sıralama

9) Java'da ikili ağacı ikili arama ağacına nasıl dönüştürürsünüz?

İkili ağaç ve ikili arama ağacı arasındaki temel fark, sol alt ağacı takip eden BST'nin daha düşük anahtar değerlere sahip olması ve sağ alt ağacın daha yüksek anahtar değerler kuralına sahip olmasıdır. Bu, aşağıdaki gibi bir dizi çapraz geçiş tekniği kullanılarak yapılabilir:

1. Ağacın sıra dışı geçişini depolayan geçici bir dizi oluşturun
2. Geçici diziyi sıralayın. Burada herhangi bir sıralama algoritması kullanabilirsiniz.
3. Yine ağaç üzerinde bir sıra dışı geçiş gerçekleştirin.
4. Dizi öğelerini her bir ağaç düğümüne birer birer kopyalayın.

10) Java'da ikili arama ağacından bir düğümü nasıl silersiniz?

Bir BST için silme işlemi, özelliklerinin işlemden sonra korunması gerektiğinden zor olabilir. İşte olası üç duruma bir bakış:

1. Silinecek düğüm bir yaprak düğümdür.
   Düğümü kaldırmanız yeterlidir.
2. Kaldırılacak düğümün bir çocuğu var.

Bu durumda, çocuğu düğüme kopyalayın ve çocuğu silin.

1. Kaldırılacak düğümün iki çocuğu var.

Bu durumda, düğümün sıralı halefini bulun. Daha sonra içeriğini düğüme kopyalayabilir ve sipariş ardılını silebilirsiniz.

11) Kırmızı-Siyah ağaç veri yapısı nedir?

Kırmızı-Siyah ağaç, aşağıdaki özelliklere sahip, kendi kendini dengeleyen özel bir ağaç türüdür:

1. Her düğümün kırmızı veya siyah bir rengi vardır.
2. Kök her zaman siyahtır.
3. Kırmızı düğümün kırmızı ebeveyni veya kırmızı çocuğu olamaz.
4. Kök düğümden NULL düğüme giden her yol, aynı sayıda siyah düğüme sahiptir.

Mutlaka Okuyun: Veri Yapısı Proje Fikirleri ve Konuları

12) İki ağacın aynı olup olmadığını nasıl anlarsınız?

Aynı veri ve düzenlemeye sahiplerse, iki ikili ağaç aynıdır. Bu, her iki ağacı da geçerek ve verilerini ve düzenlemelerini karşılaştırarak yapılabilir.

İşte bunu yapmamızı sağlayan algoritma:

1. Kök düğümün verilerini kontrol edin ( tree1 data ==tree2 data)
2. Sol alt ağacı tekrar tekrar kontrol edin. sameTree'yi çağırın (ağaç1-> sol alt ağaç, ağaç2-> sol alt ağaç)
3. Benzer şekilde, sağ alt ağacı kontrol edin
4. a,b,c doğruysa, return1

Ödeme: İkili Ağaç Türleri

Son düşünceler

Bu makalede, en sık sorulan ikili arama ağacı mülakat sorularından bazılarını inceledik. Veri yapıları hakkında daha fazlasını keşfetmek, mantığı ve programlamayı daha iyi anlamanıza yardımcı olabilir. Bu makalede bahsedilen örneklere bakmayı deneyebilir ve temellerinizi oluşturmak için değerleri değiştirerek pratik yapabilirsiniz. Biraz pratikle, röportajınızı kırmak için harika bir konumda olacaksınız.

Veri bilimi hakkında bilgi edinmek istiyorsanız, IIIT-B & upGrad'ın çalışan profesyoneller için oluşturulmuş ve 10'dan fazla vaka çalışması ve proje, uygulamalı uygulamalı atölye çalışmaları, endüstri uzmanlarıyla mentorluk, 1 Endüstri danışmanlarıyla bire bir, en iyi firmalarla 400+ saat öğrenim ve iş yardımı.