ค้นหาและคืนหน่วยความจำ

การค้นหาใน BST

การค้นหาแบบเรียกซ้ำ

Node *search(Node *root, int target) {
    if (root == NULL || root->value == target)
        return root;
    if (target < root->value)
        return search(root->left, target);
    return search(root->right, target);
}

การค้นหาแบบวนซ้ำ

Node *search_iter(Node *root, int target) {
    while (root != NULL) {
        if (target == root->value) return root;
        root = (target < root->value)
             ? root->left : root->right;
    }
    return NULL;  /* not found */
}

การค้นหาในการทำงานจริง

#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;
}
Node *search(Node *r,int t){
    if(!r||r->value==t) return r;
    return t<r->value ? search(r->left,t) : search(r->right,t);
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("7:%s 99:%s\n",
        search(root,7)?"found":"no",
        search(root,99)?"found":"no");
    return 0;
}

การหาค่าต่ำสุด

Node *find_min(Node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

เหตุใดการคืนหน่วยความจำจึงสำคัญ

คืนหน่วยความจำแบบหลัง

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

ลำดับที่ผิดและอันตราย

/* WRONG: use-after-free */
void bad_free(Node *root) {
    if (!root) return;
    free(root);                 /* freed here */
    bad_free(root->left);       /* reads freed memory! */
    bad_free(root->right);
}

หลีกเลี่ยงพอยน์เตอร์ห้อย

free_tree(root);
root = NULL;   /* avoid a dangling pointer */

นับโหนดที่คืนหน่วยความจำแล้ว

#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 free_count(Node *r){
    if(!r) return 0;
    int c = free_count(r->left) + free_count(r->right);
    free(r);
    return c + 1;
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("freed=%d\n", free_count(root));
    root = NULL;
    return 0;
}

ค้นหาและคืนหน่วยความจำร่วมกัน

/* lifecycle
 * 1. insert values     (allocate)
 * 2. search as needed   (read-only)
 * 3. free_tree(root)    (deallocate)
 * 4. root = NULL        (avoid dangling)
 */

ตรวจสอบอย่างรวดเร็ว

สรุปทบทวน