Xóa khỏi BST

#include <stdlib.h>

#include "bst.h"

/* Nút nhỏ nhất của cây con gốc r. r phải khác NULL. */
static TNode *nho_nhat(TNode *r)
{
    while (r->left != NULL) r = r->left;

    return r;
}

/* Xóa nút có giá trị v khỏi cây gốc r.
   Trả về gốc MỚI của cây con đó, theo đúng mẫu ở Bài 24.4.
   Không tìm thấy v thì cây không đổi. */
TNode *bst_xoa(TNode *r, int v)
{
    if (r == NULL) return NULL;

    if      (v < r->data) r->left  = bst_xoa(r->left,  v);
    else if (v > r->data) r->right = bst_xoa(r->right, v);
    else {
        /* Đây là nút cần xóa */

        /* TH1: không con */
        if (r->left == NULL && r->right == NULL) {
            free(r);

            return NULL;
        }

        /* TH2: chỉ có con phải */
        if (r->left == NULL) {
            TNode *con = r->right;

            free(r);

            return con;
        }

        /* TH2: chỉ có con trái */
        if (r->right == NULL) {
            TNode *con = r->left;

            free(r);

            return con;
        }

        /* TH3: hai con.
           Lấy nút kế tiếp, tức nút nhỏ nhất của cây con PHẢI.
           Chép giá trị của nó lên, rồi xóa nó khỏi cây con phải. */
        TNode *ke = nho_nhat(r->right);

        r->data  = ke->data;
        r->right = bst_xoa(r->right, ke->data);
    }

    return r;
}

#include <stdio.h>

#include "bst.h"

int main(void)
{
    TNode *goc = NULL;
    int    nguon[] = { 50, 30, 70, 20, 40, 60, 80 };

    for (size_t i = 0; i < sizeof nguon / sizeof nguon[0]; ++i)
        goc = bst_chen(goc, nguon[i]);

    printf("ban dau     : "); trung_thu_tu(goc); printf("\n");

    goc = bst_xoa(goc, 20);      /* TH1: la */
    printf("sau xoa 20  : "); trung_thu_tu(goc); printf("\n");
    printf("van la BST  : %d\n", la_bst(goc));

    goc = bst_xoa(goc, 30);      /* TH2: mot con (40) */
    printf("sau xoa 30  : "); trung_thu_tu(goc); printf("\n");
    printf("van la BST  : %d\n", la_bst(goc));

    goc = bst_xoa(goc, 50);      /* TH3: hai con */
    printf("sau xoa 50  : "); trung_thu_tu(goc); printf("\n");
    printf("van la BST  : %d\n", la_bst(goc));
    printf("goc moi     : %d\n", goc->data);

    goc = bst_xoa(goc, 99);      /* khong co */
    printf("sau xoa 99  : "); trung_thu_tu(goc); printf("\n");

    printf("cay:\n");
    in_khung(goc, "", 1, 0);

    tree_huy(goc);

    return 0;
}

/* Lựa chọn A: nút kế tiếp, nhỏ nhất của cây con PHẢI */
TNode *ke = nho_nhat(r->right);

r->data  = ke->data;
r->right = bst_xoa(r->right, ke->data);

/* Lựa chọn B: nút liền trước, lớn nhất của cây con TRÁI */
TNode *truoc = lon_nhat(r->left);

r->data = truoc->data;
r->left = bst_xoa(r->left, truoc->data);

/* Không chép data, mà thật sự thay nút. Dài hơn nhưng cần thiết
   khi có con trỏ từ bên ngoài trỏ vào nút. */
TNode *bst_xoa_noi(TNode *r, int v)
{
    if (r == NULL) return NULL;

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

    if (r->left  == NULL) { TNode *c = r->right; free(r); return c; }
    if (r->right == NULL) { TNode *c = r->left;  free(r); return c; }

    /* Hai con: gỡ nút kế tiếp ra khỏi cây con phải */
    TNode *cha_ke = r;
    TNode *ke     = r->right;

    while (ke->left != NULL) { cha_ke = ke; ke = ke->left; }

    if (cha_ke != r) {
        cha_ke->left = ke->right;      /* ke không có con trái */
        ke->right    = r->right;
    }

    ke->left = r->left;                /* ke nhận cả hai cây con của r */

    free(r);

    return ke;                         /* ke thành gốc mới của cây con này */
}

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

#include "bst.h"

/* Chèn n khóa ngẫu nhiên, rồi lặp lại: xóa một khóa ngẫu nhiên
   và chèn một khóa ngẫu nhiên khác. Đo chiều cao theo thời gian. */
int main(void)
{
    const long n   = 10000;
    const long lan = 200000;

    srand(777);

    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();
        goc     = bst_chen(goc, khoa[i]);
    }

    printf("ban dau       : chieu cao %d\n", tree_chieu_cao(goc));

    for (long k = 0; k < lan; ++k) {
        long i = rand() % n;

        goc     = bst_xoa(goc, khoa[i]);
        khoa[i] = rand();
        goc     = bst_chen(goc, khoa[i]);

        if ((k + 1) % 50000 == 0)
            printf("sau %6ld luot: chieu cao %d\n", k + 1, tree_chieu_cao(goc));
    }

    free(khoa);
    tree_huy(goc);

    return 0;
}