BST'ye Ekleme
İkili arama ağacı oluşturun.
BST'ye Ekleme, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, C Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. C Academy kursu toplamda 4 dersten oluşur.
BST Sıralama Kuralı
İkili Arama Ağacı (BST), bir ek kurala sahip ikili ağaçtır: her düğüm için sol alt ağaçtaki tüm değerler daha küçük, sağ alt ağaçtaki tüm değerler daha büyüktür.
Arama, ekleme ve silme işlemlerini ağacın yüksekliğiyle orantılı sürede yapabilmemizi sağlayan şey bu sıralamadır.
Bir Değerin Yeri
Ekleme yapmak için kökten başlar ve karşılaştırırız. Yeni değer daha küçükse sola, daha büyükse sağa gideriz.
Yeni düğümün tam olarak ait olduğu boş konuma (NULL) ulaşana kadar devam ederiz.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/create_node Yardımcısı
Ekleme yeni yaprak düğümler oluşturur; bu nedenle düğüm ayırıp başlatan bir oluşturucuyu yeniden kullanırız.
Yeni eklenen düğüm her zaman yaprak olduğundan her iki çocuk da başlangıçta NULL olur.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Özyinelemeli Ekleme
En temiz ekleme yöntemi özyinelemelidir ve (gerekirse yeni) alt ağaç kökünü döndürür.
Alt ağaç boşsa yeni bir düğüm döndürürüz. Değilse sola veya sağa özyinelemeli olarak iner, sonucu yeniden bağlar ve ardından değişmemiş kökü döndürürüz.
Node *insert(Node *root, int value) {
if (root == NULL)
return create_node(value);
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
return root; /* equal: ignore duplicate */
}Kök Neden Döndürülür
Alt ağaç kökünü döndürmek, üst düğümün bağlantıyı tek satırda yeniden kurmasını sağlar: root->left = insert(root->left, v).
Alt ağaç boşsa döndürülen yeni düğüm çocuk olur. Boş değilse aynı kök döndürülür ve bağlantı değişmez.
/* The assignment does double duty:
* - empty case: stores the new node
* - non-empty: stores the same pointer back (no-op)
*/
root->left = insert(root->left, value);Yinelenen Değerleri Ele Alma
Gerçek BST'ler eşit değerler için ne yapılacağına karar vermelidir. Yaygın bir seçim, insert işlevimizin eşit durum için bir dal içermeyerek yaptığı gibi, yinelemeleri yok saymaktır.
Alternatif olarak her düğüm için bir sayaç tutulabilir veya yinelemeler her zaman bir tarafa gönderilebilir.
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
/* value == root->value -> do nothing */Bir BST Oluşturma
Bir değer dizisi eklemek, şekli ekleme sırasına bağlı olan bir ağaç oluşturur.
Burada sıralama kuralının geçerli olduğunu doğrulamak için birkaç sayı ekleyip kökün doğrudan çocuklarını yazdırırız.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return create_node(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int main(void){
Node *root = NULL;
int data[] = {10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,data[i]);
printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
return 0;
}Yinelemesiz Ekleme
Özyineleme kullanmadan da ekleme yapabilirsiniz. Boş bir konum bulana kadar bir göstericiyle aşağı inerken üst düğümü hatırlarız.
Ardından yeni düğümü üst düğümün doğru tarafına bağlarız.
void insert_iter(Node **rootp, int value) {
Node *cur = *rootp, *parent = NULL;
while (cur) {
parent = cur;
cur = (value < cur->value) ? cur->left : cur->right;
}
Node *n = create_node(value);
if (!parent) *rootp = n;
else if (value < parent->value) parent->left = n;
else parent->right = n;
}Ekleme Sırası Ağacın Şeklini Belirler
1,2,3,4,5 değerlerini sıralı biçimde eklemek, bağlı listeye benzeyen ve yüksekliği düğüm sayısına eşit olan yozlaşmış bir ağaç oluşturur.
Dengeli bir sırayla eklemek yüksekliği log(n) civarında tutar. Denge, arama hızını doğrudan etkiler.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Eklemenin Maliyeti
Her ekleme kökten bir yaprağa kadar tek bir yolu izlediği için ağacın yüksekliğiyle orantılı iş yapar.
Dengeli bir ağaçta bu yaklaşık log(n) karşılaştırmadır; yozlaşmış bir ağaçta ise n olabilir. Kendini dengeleyen ağaçların var olma nedeni budur.
Tam Ekleme Gösterimi
Bu program değerleri ekler, ardından beş farklı değerin saklandığını ve bir yinelenen değerin yok sayıldığını doğrulamak için düğümleri sayar.
Yinelenen 10 sayısı adedi artırmaz; çünkü insert eşit değerleri eklemez.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int main(void){
Node *root=NULL;
int d[]={10,5,15,10,20};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("count=%d\n", count(root));
return 0;
}Kısa Kontrol
Ekleme davranışı hakkında düşününüz.
Özet
BST ekleme işleminde yeni değer her düğümle karşılaştırılır; boş bir konum bulunana kadar daha küçük değerler için sola, daha büyük değerler için sağa gidilir.
Özyinelemeli biçim, alt ağacın kökünü döndürür; böylece üst düğüm bağlantıları düzgün bir şekilde yeniden kurabilir. Ekleme maliyeti ağacın yüksekliğiyle orantılıdır, bu nedenle ekleme sırası önemlidir.
Sıkça Sorulan Sorular
“BST'ye Ekleme” dersi ücretsiz mi?
Evet — “BST'ye Ekleme” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve C Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. C Academy kursu toplamda 4 dersten oluşur.
“BST'ye Ekleme” dersinde ne öğreneceğim?
İkili arama ağacı oluşturun. C Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
C Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te C Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“BST'ye Ekleme” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu C Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her C Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.