Algoritmalar
tr

İkili Arama Ağacı

Ağaçlar O(h) O(n)

Her sol alt ağacın daha küçük, her sağ alt ağacın daha büyük olduğu sıralı ağaç — ekleme, arama ve silme tek bir kök-yaprak yolunu izler.

50
1/31

Ağaç boş — 50 kök oluyor.

DeğişmezHer düğüm için sol alt ağacın tamamı küçük, sağ alt ağacın tamamı büyüktür — bu yüzden tek karşılaştırma ağacın yarısını eler.

bst.c
typedef struct Node {
    int key;
    struct Node *left, *right;
} Node;
 
Node *insert(Node *root, int key) {
    if (root == NULL)
        return newNode(key);
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    return root;
}
 
Node *search(Node *root, int key) {
    while (root && root->key != key)
        root = key < root->key ? root->left
                               : root->right;
    return root;
}
 
Node *deleteNode(Node *root, int key) {
    if (root == NULL) return NULL;
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (!root->left)  return root->right;
        if (!root->right) return root->left;
        Node *m = minNode(root->right);
        root->key = m->key;
        root->right = deleteNode(root->right, m->key);
    }
    return root;
}

İkili Arama Ağacı nasıl çalışır?

Değişmez kural — sol alt ağaç küçük, sağ alt ağaç büyük — her işlemi tek bir kök-yaprak yürüyüşüne çevirir. İki çocuklu düğüm silinirken sıradaki ardıl kopyalanır ve onun yerine o silinir.

En iyi durum

Dengeli ağaç: O(log n) yürüyüş.

En kötü durum

Sıralı eklemeler onu bağlı listeye düşürür: O(n).

Ne zaman kullanılır?

Sıralı eşlemeler: aralık sorguları, öncel/ardıl, sıralı gezinme — dengeleme eklenince.