Hafta 11 — İleri Ağaçlar¶

/* Week 11 -- Advanced Trees
 * Binary search tree (BST): insert. Duplicates are ignored (tree unchanged).
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

Node *bst_insert(Node *root, int key) {
    Node *cur = root, *parent = NULL;
    while (cur != NULL) {
        parent = cur;
        if (key == cur->key) return root;             /* duplicate: tree unchanged */
        if (key < cur->key)  cur = cur->left;
        else                 cur = cur->right;
    }
    Node *n = malloc(sizeof(Node));
    n->key = key;
    n->left = NULL;
    n->right = NULL;
    if (parent == NULL) return n;                      /* empty tree: n is the new root */
    if (key < parent->key) parent->left = n;
    else                    parent->right = n;
    return root;
}

static int height(Node *n) {
    if (n == NULL) return -1;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}

static void print_inorder(Node *n) {
    if (n == NULL) return;
    print_inorder(n->left);
    printf(" %d", n->key);
    print_inorder(n->right);
}

static void free_tree(Node *n) {
    if (n == NULL) return;
    free_tree(n->left);
    free_tree(n->right);
    free(n);
}

static void run_scenario(const char *label, const int keys[], int n) {
    printf("-- %s --\n", label);
    Node *root = NULL;
    for (int i = 0; i < n; i++) {
        root = bst_insert(root, keys[i]);
        printf("insert(%d): inorder =", keys[i]);
        print_inorder(root);
        printf("  height = %d\n", height(root));
    }
    printf("\n");
    free_tree(root);
}

int main(void) {
    int normal[] = {50, 30, 70, 20, 40, 60, 80, 35, 65, 90};
    run_scenario("normal: 10 keys, a moderately mixed order", normal, 10);

    int hard[] = {10, -5, 25, 10, -20, 5, 17, 30, -5, 3, 22, 40, -15, 12};
    run_scenario("hard: 14 keys, negative values and a repeat", hard, 14);

    int dup[] = {8, 8, 3, 8, 3, 15, 3, 8, 15, 8};
    run_scenario("edge: 10 values, only 3 distinct keys", dup, 10);

    int sorted[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    run_scenario("edge: 10 keys in ascending order -- forms a near-chain", sorted, 10);

    int single[] = {42};
    run_scenario("edge: a single key", single, 1);

    return 0;
}

/* Week 11 -- Advanced Trees
 * Binary search tree (BST): insert. Duplicates are ignored (tree unchanged).
 * CEN207 Data Structures (formerly CE205)
 */
public class BstInsert {
    static class Node {
        int key;
        Node left;
        Node right;
    }

    static Node bstInsert(Node root, int key) {
        Node cur = root, parent = null;
        while (cur != null) {
            parent = cur;
            if (key == cur.key) return root;               // duplicate: tree unchanged
            if (key < cur.key)  cur = cur.left;
            else                cur = cur.right;
        }
        Node n = new Node();
        n.key = key;
        n.left = null;
        n.right = null;
        if (parent == null) return n;                       // empty tree: n is the new root
        if (key < parent.key) parent.left = n;
        else                   parent.right = n;
        return root;
    }

    static int height(Node n) {
        if (n == null) return -1;
        int l = height(n.left), r = height(n.right);
        return 1 + Math.max(l, r);
    }

    static void printInorder(Node n, StringBuilder sb) {
        if (n == null) return;
        printInorder(n.left, sb);
        sb.append(' ').append(n.key);
        printInorder(n.right, sb);
    }

    static void runScenario(String label, int[] keys) {
        System.out.println("-- " + label + " --");
        Node root = null;
        for (int key : keys) {
            root = bstInsert(root, key);
            StringBuilder sb = new StringBuilder();
            printInorder(root, sb);
            System.out.println("insert(" + key + "): inorder =" + sb + "  height = " + height(root));
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {50, 30, 70, 20, 40, 60, 80, 35, 65, 90};
        runScenario("normal: 10 keys, a moderately mixed order", normal);

        int[] hard = {10, -5, 25, 10, -20, 5, 17, 30, -5, 3, 22, 40, -15, 12};
        runScenario("hard: 14 keys, negative values and a repeat", hard);

        int[] dup = {8, 8, 3, 8, 3, 15, 3, 8, 15, 8};
        runScenario("edge: 10 values, only 3 distinct keys", dup);

        int[] sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        runScenario("edge: 10 keys in ascending order -- forms a near-chain", sorted);

        int[] single = {42};
        runScenario("edge: a single key", single);
    }
}

/* Week 11 -- Advanced Trees
 * Binary search tree (BST): search.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

static Node *bst_build_insert(Node *root, int key) {
    Node *cur = root, *parent = NULL;
    while (cur != NULL) {
        parent = cur;
        if (key == cur->key) return root;
        if (key < cur->key) cur = cur->left; else cur = cur->right;
    }
    Node *n = malloc(sizeof(Node));
    n->key = key; n->left = NULL; n->right = NULL;
    if (parent == NULL) return n;
    if (key < parent->key) parent->left = n; else parent->right = n;
    return root;
}

int probes;

int bst_search(Node *root, int key) {
    Node *cur = root;
    probes = 0;
    while (cur != NULL) {
        probes++;
        if (key == cur->key) return 1;
        if (key < cur->key) cur = cur->left;
        else                cur = cur->right;
    }
    return 0;
}

static void free_tree(Node *n) {
    if (n == NULL) return;
    free_tree(n->left);
    free_tree(n->right);
    free(n);
}

static void run_scenario(const char *label, const int keys[], int nk, const int finds[], int nf) {
    printf("-- %s --\n", label);
    Node *root = NULL;
    for (int i = 0; i < nk; i++) root = bst_build_insert(root, keys[i]);
    printf("tree built from %d keys\n", nk);
    for (int i = 0; i < nf; i++) {
        int found = bst_search(root, finds[i]);
        printf("search(%d): %s, %d probes\n", finds[i], found ? "found" : "not found", probes);
    }
    printf("\n");
    free_tree(root);
}

int main(void) {
    int normal_keys[] = {50, 30, 70, 20, 40, 60, 80, 35, 65, 90};
    int normal_finds[] = {65, 20, 90, 55, 100};
    run_scenario("normal: 10 keys, 3 hits and 2 misses", normal_keys, 10, normal_finds, 5);

    int hard_keys[] = {10, -5, 25, 40, -20, 5, 17, 30, 45, 3, 22, -15, 12, 60};
    int hard_finds[] = {-20, 60, 0, -5, 99};
    run_scenario("hard: 14 keys with negative values, 5 searches", hard_keys, 14, hard_finds, 5);

    int bound_keys[] = {50, 30, 70, 20, 40, 60, 80, 10, 45, 90};
    int bound_finds[] = {-1000, 1000, 50};
    run_scenario("edge: searching below the minimum and above the maximum", bound_keys, 10, bound_finds, 3);

    int chain_keys[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int chain_finds[] = {10, 1, 11};
    run_scenario("edge: searching for the last key in a chain built from ascending inserts (O(n))", chain_keys, 10, chain_finds, 3);

    int single_keys[] = {7};
    int single_finds[] = {7, 3};
    run_scenario("edge: a single node, search the root and a missing value", single_keys, 1, single_finds, 2);

    return 0;
}

/* Week 11 -- Advanced Trees
 * Binary search tree (BST): search.
 * CEN207 Data Structures (formerly CE205)
 */
public class BstSearch {
    static class Node {
        int key;
        Node left;
        Node right;
    }

    static Node bstBuildInsert(Node root, int key) {
        Node cur = root, parent = null;
        while (cur != null) {
            parent = cur;
            if (key == cur.key) return root;
            if (key < cur.key) cur = cur.left; else cur = cur.right;
        }
        Node n = new Node();
        n.key = key; n.left = null; n.right = null;
        if (parent == null) return n;
        if (key < parent.key) parent.left = n; else parent.right = n;
        return root;
    }

    static int probes;

    static boolean bstSearch(Node root, int key) {
        Node cur = root;
        probes = 0;
        while (cur != null) {
            probes++;
            if (key == cur.key) return true;
            if (key < cur.key) cur = cur.left;
            else                cur = cur.right;
        }
        return false;
    }

    static void runScenario(String label, int[] keys, int[] finds) {
        System.out.println("-- " + label + " --");
        Node root = null;
        for (int key : keys) root = bstBuildInsert(root, key);
        System.out.println("tree built from " + keys.length + " keys");
        for (int f : finds) {
            boolean found = bstSearch(root, f);
            System.out.println("search(" + f + "): " + (found ? "found" : "not found") + ", " + probes + " probes");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normalKeys = {50, 30, 70, 20, 40, 60, 80, 35, 65, 90};
        int[] normalFinds = {65, 20, 90, 55, 100};
        runScenario("normal: 10 keys, 3 hits and 2 misses", normalKeys, normalFinds);

        int[] hardKeys = {10, -5, 25, 40, -20, 5, 17, 30, 45, 3, 22, -15, 12, 60};
        int[] hardFinds = {-20, 60, 0, -5, 99};
        runScenario("hard: 14 keys with negative values, 5 searches", hardKeys, hardFinds);

        int[] boundKeys = {50, 30, 70, 20, 40, 60, 80, 10, 45, 90};
        int[] boundFinds = {-1000, 1000, 50};
        runScenario("edge: searching below the minimum and above the maximum", boundKeys, boundFinds);

        int[] chainKeys = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] chainFinds = {10, 1, 11};
        runScenario("edge: searching for the last key in a chain built from ascending inserts (O(n))", chainKeys, chainFinds);

        int[] singleKeys = {7};
        int[] singleFinds = {7, 3};
        runScenario("edge: a single node, search the root and a missing value", singleKeys, singleFinds);
    }
}

/* Week 11 -- Advanced Trees
 * Binary search tree (BST): delete (leaf / one child / two children with successor).
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

static Node *bst_build_insert(Node *root, int key) {
    Node *cur = root, *parent = NULL;
    while (cur != NULL) {
        parent = cur;
        if (key == cur->key) return root;
        if (key < cur->key) cur = cur->left; else cur = cur->right;
    }
    Node *n = malloc(sizeof(Node));
    n->key = key; n->left = NULL; n->right = NULL;
    if (parent == NULL) return n;
    if (key < parent->key) parent->left = n; else parent->right = n;
    return root;
}

Node *bst_delete(Node *root, int key) {
    Node *cur = root, *parent = NULL;
    while (cur != NULL && key != cur->key) {
        parent = cur;
        cur = (key < cur->key) ? cur->left : cur->right;
    }
    if (cur == NULL) return root;                     /* not found: no-op */
    if (cur->left != NULL && cur->right != NULL) {
        Node *succ = cur->right, *succParent = cur;
        while (succ->left != NULL) { succParent = succ; succ = succ->left; }
        cur->key = succ->key;                          /* copy successor key up */
        parent = succParent;
        cur = succ;                                    /* now splice out succ: <= 1 child */
    }
    Node *child = (cur->left != NULL) ? cur->left : cur->right;
    if (parent == NULL)           root = child;
    else if (parent->left == cur) parent->left  = child;
    else                          parent->right = child;
    free(cur);
    return root;
}

static void print_inorder(Node *n) {
    if (n == NULL) return;
    print_inorder(n->left);
    printf(" %d", n->key);
    print_inorder(n->right);
}

static void free_tree(Node *n) {
    if (n == NULL) return;
    free_tree(n->left);
    free_tree(n->right);
    free(n);
}

static void run_scenario(const char *label, const int keys[], int nk, const int dels[], int nd) {
    printf("-- %s --\n", label);
    Node *root = NULL;
    for (int i = 0; i < nk; i++) root = bst_build_insert(root, keys[i]);
    printf("tree built from %d keys, inorder =", nk);
    print_inorder(root);
    printf("\n");
    for (int i = 0; i < nd; i++) {
        root = bst_delete(root, dels[i]);
        printf("delete(%d): inorder =", dels[i]);
        print_inorder(root);
        printf("\n");
    }
    printf("\n");
    free_tree(root);
}

int main(void) {
    int normal_keys[] = {50, 30, 70, 20, 40, 60, 80, 35, 65, 90};
    int normal_dels[] = {35, 70, 50, 20};
    run_scenario("normal: 10 keys, 4 deletes (a mix of leaf, one-child, two-children)", normal_keys, 10, normal_dels, 4);

    int hard_keys[] = {10, -5, 25, 40, -20, 5, 17, 30, 45, 3, 22, -15, 12, 60};
    int hard_dels[] = {-5, 40, 10, 17, 60, 3};
    run_scenario("hard: 14 keys with negative values, 6 deletes (including the root)", hard_keys, 14, hard_dels, 6);

    int nf_keys[] = {50, 30, 70, 20, 40, 60, 80, 10, 45, 90};
    int nf_dels[] = {999, 30, -1000};
    run_scenario("edge: trying to delete a key that is not there (no-op)", nf_keys, 10, nf_dels, 3);

    int empty_keys[] = {5, 3, 8, 1, 4, 7, 9, 2, 6, 10};
    int empty_dels[] = {10, 6, 2, 9, 7, 4, 1, 8, 3, 5};
    run_scenario("edge: delete every key, down to an empty tree", empty_keys, 10, empty_dels, 10);

    int single_keys[] = {7};
    int single_dels[] = {7};
    run_scenario("edge: delete the only node", single_keys, 1, single_dels, 1);

    return 0;
}

/* Week 11 -- Advanced Trees
 * Binary search tree (BST): delete (leaf / one child / two children with successor).
 * CEN207 Data Structures (formerly CE205)
 */
public class BstDelete {
    static class Node {
        int key;
        Node left;
        Node right;
    }

    static Node bstBuildInsert(Node root, int key) {
        Node cur = root, parent = null;
        while (cur != null) {
            parent = cur;
            if (key == cur.key) return root;
            if (key < cur.key) cur = cur.left; else cur = cur.right;
        }
        Node n = new Node();
        n.key = key; n.left = null; n.right = null;
        if (parent == null) return n;
        if (key < parent.key) parent.left = n; else parent.right = n;
        return root;
    }

    static Node bstDelete(Node root, int key) {
        Node cur = root, parent = null;
        while (cur != null && key != cur.key) {
            parent = cur;
            cur = (key < cur.key) ? cur.left : cur.right;
        }
        if (cur == null) return root;                      // not found: no-op
        if (cur.left != null && cur.right != null) {
            Node succ = cur.right, succParent = cur;
            while (succ.left != null) { succParent = succ; succ = succ.left; }
            cur.key = succ.key;                             // copy successor key up
            parent = succParent;
            cur = succ;                                     // now splice out succ: <= 1 child
        }
        Node child = (cur.left != null) ? cur.left : cur.right;
        if (parent == null)            root = child;
        else if (parent.left == cur)   parent.left  = child;
        else                           parent.right = child;
        return root;
    }

    static void printInorder(Node n, StringBuilder sb) {
        if (n == null) return;
        printInorder(n.left, sb);
        sb.append(' ').append(n.key);
        printInorder(n.right, sb);
    }

    static void runScenario(String label, int[] keys, int[] dels) {
        System.out.println("-- " + label + " --");
        Node root = null;
        for (int key : keys) root = bstBuildInsert(root, key);
        StringBuilder sb0 = new StringBuilder();
        printInorder(root, sb0);
        System.out.println("tree built from " + keys.length + " keys, inorder =" + sb0);
        for (int d : dels) {
            root = bstDelete(root, d);
            StringBuilder sb = new StringBuilder();
            printInorder(root, sb);
            System.out.println("delete(" + d + "): inorder =" + sb);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normalKeys = {50, 30, 70, 20, 40, 60, 80, 35, 65, 90};
        int[] normalDels = {35, 70, 50, 20};
        runScenario("normal: 10 keys, 4 deletes (a mix of leaf, one-child, two-children)", normalKeys, normalDels);

        int[] hardKeys = {10, -5, 25, 40, -20, 5, 17, 30, 45, 3, 22, -15, 12, 60};
        int[] hardDels = {-5, 40, 10, 17, 60, 3};
        runScenario("hard: 14 keys with negative values, 6 deletes (including the root)", hardKeys, hardDels);

        int[] nfKeys = {50, 30, 70, 20, 40, 60, 80, 10, 45, 90};
        int[] nfDels = {999, 30, -1000};
        runScenario("edge: trying to delete a key that is not there (no-op)", nfKeys, nfDels);

        int[] emptyKeys = {5, 3, 8, 1, 4, 7, 9, 2, 6, 10};
        int[] emptyDels = {10, 6, 2, 9, 7, 4, 1, 8, 3, 5};
        runScenario("edge: delete every key, down to an empty tree", emptyKeys, emptyDels);

        int[] singleKeys = {7};
        int[] singleDels = {7};
        runScenario("edge: delete the only node", singleKeys, singleDels);
    }
}

/* Week 11 -- Advanced Trees
 * Why balancing matters: inserting the SAME set of keys in different orders gives wildly different BST
 * shapes. Sorted input degenerates into a chain -- height n-1, every operation O(n).
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

Node *bst_insert(Node *root, int key) {
    Node *cur = root, *parent = NULL;
    while (cur != NULL) {
        parent = cur;
        if (key == cur->key) return root;
        if (key < cur->key)  cur = cur->left;
        else                 cur = cur->right;
    }
    Node *n = malloc(sizeof(Node));
    n->key = key; n->left = NULL; n->right = NULL;
    if (parent == NULL) return n;
    if (key < parent->key) parent->left = n;
    else                    parent->right = n;
    return root;
}

static int height(Node *n) {
    if (n == NULL) return -1;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}

static void free_tree(Node *n) {
    if (n == NULL) return;
    free_tree(n->left);
    free_tree(n->right);
    free(n);
}

static int ilog2(int n) {
    int h = 0;
    while (n > 1) { n /= 2; h++; }
    return h;
}

static void run_scenario(const char *label, const int keys[], int n) {
    printf("-- %s --\n", label);
    Node *root = NULL;
    for (int i = 0; i < n; i++) {
        root = bst_insert(root, keys[i]);
        printf("insert(%d): height = %d  (ideal for %d nodes = %d)\n",
               keys[i], height(root), i + 1, ilog2(i + 1));
    }
    int h = height(root), ideal = ilog2(n);
    printf("final: n = %d, height = %d, ideal = %d\n\n", n, h, ideal);
    free_tree(root);
}

int main(void) {
    int normal[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    run_scenario("normal: 10 keys in ascending order -- forms a chain", normal, 10);

    int hard[] = {140, 130, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
    run_scenario("hard: 14 keys in descending order -- a chain the other way", hard, 14);

    int zigzag[] = {10, 20, 15, 30, 25, 40, 35, 50, 45, 60};
    run_scenario("edge: nearly sorted with small zig-zags (still deep)", zigzag, 10);

    int shuffled[] = {6, 9, 2, 10, 4, 8, 1, 7, 3, 5};
    run_scenario("edge: the SAME 10 keys shuffled -- much shallower", shuffled, 10);

    int single[] = {42};
    run_scenario("edge: a single key, height 0", single, 1);

    return 0;
}

/* Week 11 -- Advanced Trees
 * Why balancing matters: inserting the SAME set of keys in different orders gives wildly different BST
 * shapes. Sorted input degenerates into a chain -- height n-1, every operation O(n).
 * CEN207 Data Structures (formerly CE205)
 */
public class BstDegenerate {
    static class Node {
        int key;
        Node left;
        Node right;
    }

    static Node bstInsert(Node root, int key) {
        Node cur = root, parent = null;
        while (cur != null) {
            parent = cur;
            if (key == cur.key) return root;
            if (key < cur.key)  cur = cur.left;
            else                cur = cur.right;
        }
        Node n = new Node();
        n.key = key; n.left = null; n.right = null;
        if (parent == null) return n;
        if (key < parent.key) parent.left = n;
        else                   parent.right = n;
        return root;
    }

    static int height(Node n) {
        if (n == null) return -1;
        int l = height(n.left), r = height(n.right);
        return 1 + Math.max(l, r);
    }

    static int ilog2(int n) {
        int h = 0;
        while (n > 1) { n /= 2; h++; }
        return h;
    }

    static void runScenario(String label, int[] keys) {
        System.out.println("-- " + label + " --");
        Node root = null;
        for (int i = 0; i < keys.length; i++) {
            root = bstInsert(root, keys[i]);
            System.out.println("insert(" + keys[i] + "): height = " + height(root)
                    + "  (ideal for " + (i + 1) + " nodes = " + ilog2(i + 1) + ")");
        }
        int h = height(root), ideal = ilog2(keys.length);
        System.out.println("final: n = " + keys.length + ", height = " + h + ", ideal = " + ideal);
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        runScenario("normal: 10 keys in ascending order -- forms a chain", normal);

        int[] hard = {140, 130, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
        runScenario("hard: 14 keys in descending order -- a chain the other way", hard);

        int[] zigzag = {10, 20, 15, 30, 25, 40, 35, 50, 45, 60};
        runScenario("edge: nearly sorted with small zig-zags (still deep)", zigzag);

        int[] shuffled = {6, 9, 2, 10, 4, 8, 1, 7, 3, 5};
        runScenario("edge: the SAME 10 keys shuffled -- much shallower", shuffled);

        int[] single = {42};
        runScenario("edge: a single key, height 0", single);
    }
}