İkili Ağaca Harf Ekleme
İkili ağaçlar, verileri hiyerarşik bir yapıda düzenlemek için kullanılan yaygın bir veri yapısıdır. Her düğüm, bir değer ve sol ve sağ olmak üzere en fazla iki alt düğüme sahip olabilir. İkili ağaçlara harf eklemek, verileri ağaca doğru bir şekilde yerleştirmeyi gerektiren önemli bir işlemdir.
Harf Ekleme Algoritması
Bir ikili ağaca harf eklemek için aşağıdaki algoritmayı izleyin:
- Kök düğümü kontrol edin: Ağacın kök düğümü yoksa, yeni harfi içeren bir kök düğümü oluşturun.
- Harfi mevcut düğümle karşılaştırın: Eklenecek harf, mevcut düğümün değerinden daha küçükse, sol alt düğüme gidin. Daha büyükse, sağ alt düğüme gidin.
- Alt düğüm yoksa: Alt düğüm yoksa, yeni harfi içeren bir düğüm oluşturun ve mevcut düğüme bağlayın.
- Alt düğüm varsa: Alt düğüm varsa, 2. adıma dönün ve alt düğümle karşılaştırın.
Örnek
Aşağıdaki ikili ağaca “D” harfini ekleyelim:
A
/ \
B C
- “D” harfi “A” harfinden daha büyük olduğundan sağ alt düğüme gideriz.
- Sağ alt düğüm boş olduğundan, “D” harfini içeren bir düğüm oluşturur ve “A” düğümüne bağlarız.
Sonuç olarak, ikili ağaç şu şekilde olur:
A
/ \
B C
\
D
Karmaşıklık Analizi
İkili ağaca harf ekleme işleminin zaman karmaşıklığı, ağacın yüksekliğine bağlıdır. En kötü durumda, ağaç dengeli değilse ve eklenen harf en alt düğüme ekleniyorsa, karmaşıklık O(n) olur, burada n ağacın düğüm sayısıdır. En iyi durumda, ağaç dengeliyse ve eklenen harf köke ekleniyorsa, karmaşıklık O(1) olur.