İkili Arama Ağacına Eleman Ekleme
İkili arama ağacı (BST), verileri hiyerarşik bir şekilde düzenleyen ve hızlı arama ve ekleme işlemlerine olanak tanıyan bir veri yapısıdır. Bir BST’ye eleman eklemek, ağacın yapısını korurken yeni elemanı doğru konuma yerleştirmeyi içerir.
BST’ye Eleman Ekleme Adımları
Bir BST’ye eleman eklemek için şu adımları izleyin:
- Başlangıç düğümünü bulun: Yeni elemanı eklemek için ağacın kök düğümünden başlayın.
- Yeni elemanı karşılaştırın: Yeni elemanı geçerli düğümle karşılaştırın.
- Sol veya sağ alt ağaca geçin: Yeni eleman geçerli düğümden küçükse sol alt ağaca, büyükse sağ alt ağaca geçin.
- Alt ağacın boş olup olmadığını kontrol edin: Alt ağacın boş olması durumunda, yeni elemanı geçerli düğümün alt düğümü olarak ekleyin.
- Alt ağacın boş olmaması durumunda: Adımları 2-4’ü alt ağaç için tekrarlayın.
Örnek
Aşağıdaki BST’ye 15 elemanını ekleyelim:
10
/ \
5 12
/ \ / \
2 7 11 14
- Başlangıç düğümünü bulun: Kök düğüm 10’dur.
- Yeni elemanı karşılaştırın: 15, 10’dan büyüktür.
- Sağ alt ağaca geçin: 15’i sağ alt ağaca ekleyeceğiz.
- Alt ağacın boş olup olmadığını kontrol edin: Sağ alt ağaç boştur.
- Yeni elemanı ekleyin: 15’i sağ alt ağacın alt düğümü olarak ekleyin.
Sonuç olarak, BST şu şekilde güncellenir:
10
/ \
5 12
/ \ / \
2 7 11 14
\
15
Karmaşıklık Analizi
BST’ye eleman ekleme işleminin ortalama zaman karmaşıklığı O(log n)’dir, burada n ağaçtaki düğüm sayısıdır. En kötü durum karmaşıklığı, ağaç tek taraflıysa O(n)’dir.