Cây tìm kiếm nhị phân

#include <limits.h>
#include <stdio.h>

#include "tree.h"

/* Cách 1: truyền khoảng hợp lệ xuống. O(n), một lượt duyệt. */
static int trong_khoang(const TNode *r, long can_duoi, long can_tren)
{
    if (r == NULL) return 1;

    if (r->data <= can_duoi || r->data >= can_tren) return 0;

    return trong_khoang(r->left,  can_duoi, r->data)
        && trong_khoang(r->right, r->data,  can_tren);
}

int la_bst(const TNode *r)
{
    /* Dùng long để cận rộng hơn kiểu int, tránh vấn đề với INT_MIN và INT_MAX */
    return trong_khoang(r, (long)INT_MIN - 1, (long)INT_MAX + 1);
}

/* Cách 2: duyệt trung thứ tự, kiểm dãy có tăng nghiêm ngặt không.
   truoc giữ giá trị nút vừa thăm, khoi_tao cho biết đã thăm nút nào chưa. */
static int trung_tang(const TNode *r, long *truoc, int *khoi_tao)
{
    if (r == NULL) return 1;

    if (!trung_tang(r->left, truoc, khoi_tao)) return 0;

    if (*khoi_tao && r->data <= *truoc) return 0;

    *truoc    = r->data;
    *khoi_tao = 1;

    return trung_tang(r->right, truoc, khoi_tao);
}

int la_bst_2(const TNode *r)
{
    long truoc    = 0;
    int  khoi_tao = 0;

    return trung_tang(r, &truoc, &khoi_tao);
}

/* Chèn 1, 2, 3, 4, 5 vào một BST rỗng:

   1                Mỗi số mới đều lớn hơn tất cả số cũ,
    \               nên nó luôn đi sang phải và thành con
     2              phải của nút cuối cùng.
      \
       3            Kết quả: cây thành danh sách liên kết,
        \           chiều cao bằng n trừ 1.
         4
          \         Mọi thao tác trở thành O(n).
           5                                              */

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

#include "bst.h"

int main(void)
{
    srand(12345);

    printf("%10s %10s %10s %10s\n", "n", "cao TB", "log2(n)", "ty le");

    for (long n = 1000; n <= 1000000; n *= 10) {
        double tong = 0.0;
        int    lan  = 20;

        for (int k = 0; k < lan; ++k) {
            TNode *goc = NULL;

            for (long i = 0; i < n; ++i)
                if (bst_chen(&goc, rand()) != 0) { tree_huy(goc); return 1; }

            tong += tree_chieu_cao(goc);
            tree_huy(goc);
        }

        double tb = tong / lan;
        double lg = log2((double)n);

        printf("%10ld %10.1f %10.1f %10.2f\n", n, tb, lg, tb / lg);
    }

    return 0;
}