Tìm trong BST

/* Tìm nút có data bằng v. Trả về NULL nếu không có.
   Bản LẶP: O(1) bộ nhớ, không sợ tràn ngăn xếp. */
TNode *bst_tim(TNode *r, int v)
{
    while (r != NULL) {
        if      (v == r->data) return r;
        else if (v <  r->data) r = r->left;
        else                   r = r->right;
    }

    return NULL;
}

/* Bản đệ quy, để so sánh. Cùng độ phức tạp nhưng tốn ngăn xếp. */
TNode *bst_tim_de_quy(TNode *r, int v)
{
    if (r == NULL || v == r->data) return r;

    return v < r->data ? bst_tim_de_quy(r->left,  v)
                       : bst_tim_de_quy(r->right, v);
}

/* Nút nhỏ nhất: đi hết sang trái. Trả về NULL nếu cây rỗng. */
TNode *bst_nho_nhat(TNode *r)
{
    if (r == NULL) return NULL;

    while (r->left != NULL) r = r->left;

    return r;
}

/* Nút lớn nhất: đi hết sang phải. */
TNode *bst_lon_nhat(TNode *r)
{
    if (r == NULL) return NULL;

    while (r->right != NULL) r = r->right;

    return r;
}

/* Nút kế tiếp của giá trị v theo thứ tự tăng dần.
   Không cần v phải có trong cây. Trả về NULL nếu không có nút nào lớn hơn v. */
TNode *bst_ke_tiep(TNode *r, int v)
{
    TNode *ung_vien = NULL;

    while (r != NULL) {
        if (r->data > v) {
            ung_vien = r;        /* ứng viên tốt nhất tới lúc này */
            r        = r->left;  /* thử tìm ứng viên nhỏ hơn nữa bên trái */
        } else {
            r = r->right;        /* r->data <= v, mọi thứ bên trái đều loại */
        }
    }

    return ung_vien;
}

/* Nút liền trước, đối xứng hoàn toàn. */
TNode *bst_lien_truoc(TNode *r, int v)
{
    TNode *ung_vien = NULL;

    while (r != NULL) {
        if (r->data < v) {
            ung_vien = r;
            r        = r->right;
        } else {
            r = r->left;
        }
    }

    return ung_vien;
}

typedef struct TNodeP {
    int             data;
    struct TNodeP  *left, *right, *cha;
} TNodeP;

/* Nút kế tiếp của một nút CỤ THỂ, không phải của một giá trị. */
TNodeP *ke_tiep_cua_nut(TNodeP *x)
{
    if (x == NULL) return NULL;

    /* Trường hợp 1: có cây con phải thì kế tiếp là nút nhỏ nhất trong đó */
    if (x->right != NULL) {
        x = x->right;

        while (x->left != NULL) x = x->left;

        return x;
    }

    /* Trường hợp 2: không có cây con phải thì đi lên cho tới khi
       gặp một tổ tiên mà x nằm trong cây con TRÁI của nó */
    TNodeP *p = x->cha;

    while (p != NULL && x == p->right) {
        x = p;
        p = p->cha;
    }

    return p;
}

/* Gọi ham cho mọi giá trị trong khoảng [thap, cao], theo thứ tự tăng dần.
   Cắt tỉa: không đi vào cây con chắc chắn nằm ngoài khoảng. */
void bst_duyet_khoang(const TNode *r, int thap, int cao,
                      void (*ham)(int, void *), void *ctx)
{
    if (r == NULL) return;

    /* Chỉ đi trái nếu còn giá trị nào trong đó có thể lớn hơn hoặc bằng thap */
    if (r->data > thap)
        bst_duyet_khoang(r->left, thap, cao, ham, ctx);

    if (r->data >= thap && r->data <= cao)
        ham(r->data, ctx);

    /* Chỉ đi phải nếu còn giá trị nào trong đó có thể nhỏ hơn hoặc bằng cao */
    if (r->data < cao)
        bst_duyet_khoang(r->right, thap, cao, ham, ctx);
}

/* Đếm số nút trong khoảng, cùng cách cắt tỉa. */
size_t bst_dem_khoang(const TNode *r, int thap, int cao)
{
    if (r == NULL) return 0;

    size_t d = 0;

    if (r->data > thap) d += bst_dem_khoang(r->left, thap, cao);
    if (r->data >= thap && r->data <= cao) ++d;
    if (r->data < cao)  d += bst_dem_khoang(r->right, thap, cao);

    return d;
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "bst.h"

static long tong_so_sanh;

static TNode *tim_dem(TNode *r, int v)
{
    while (r != NULL) {
        ++tong_so_sanh;

        if      (v == r->data) return r;
        else if (v <  r->data) r = r->left;
        else                   r = r->right;
    }

    return NULL;
}

int main(void)
{
    srand(2024);

    printf("%10s %10s %12s %12s\n",
           "n", "chieu cao", "so sanh TB", "log2(n)");

    for (long n = 1000; n <= 1000000; n *= 10) {
        TNode *goc = NULL;
        int   *khoa = malloc((size_t)n * sizeof *khoa);

        if (khoa == NULL) return 1;

        for (long i = 0; i < n; ++i) {
            khoa[i] = rand();

            if (bst_chen2(&goc, khoa[i]) < 0) { tree_huy(goc); return 1; }
        }

        tong_so_sanh = 0;

        long lan = 100000;

        for (long i = 0; i < lan; ++i)
            tim_dem(goc, khoa[rand() % n]);

        printf("%10ld %10d %12.1f %12.1f\n",
               n, tree_chieu_cao(goc),
               (double)tong_so_sanh / lan, log2((double)n));

        free(khoa);
        tree_huy(goc);
    }

    return 0;
}