Cây AVL

#ifndef AVL_H
#define AVL_H

#include <stddef.h>

typedef struct ANode {
    int           data;
    int           height;      /* chiều cao ĐẾM NÚT: lá có height 1 */
    struct ANode *left, *right;
} ANode;

ANode *avl_chen(ANode *n, int v, int *loi);
ANode *avl_xoa(ANode *n, int v);
ANode *avl_tim(ANode *n, int v);
void   avl_huy(ANode *n);
int    avl_chieu_cao(const ANode *n);
int    avl_hop_le(const ANode *n);

#endif

#include <stdlib.h>

#include "avl.h"

/* Chiều cao ĐẾM NÚT: cây rỗng là 0, lá là 1.
   Quy ước này tránh số âm nên lưu vào trường int rất gọn. */
static int h(const ANode *n) { return n ? n->height : 0; }

/* Hệ số cân bằng: dương nghĩa là lệch trái, âm nghĩa là lệch phải. */
static int bf(const ANode *n) { return n ? h(n->left) - h(n->right) : 0; }

static void cap_nhat_h(ANode *n)
{
    int t = h(n->left);
    int p = h(n->right);

    n->height = 1 + (t > p ? t : p);
}

int avl_chieu_cao(const ANode *n) { return h(n); }

/* Xoay phải quanh y. Trả về gốc mới, tức x.

        y                x
       / \              / \
      x   c    ==>      a   y
     / \                   / \
    a   T                 T   c                      */
static ANode *xoay_phai(ANode *y)
{
    ANode *x = y->left;
    ANode *T = x->right;      /* cây con giữa, sẽ đổi chủ */

    x->right = y;
    y->left  = T;

    cap_nhat_h(y);            /* y ở DƯỚI nên cập nhật TRƯỚC */
    cap_nhat_h(x);

    return x;
}

/* Xoay trái quanh x. Trả về gốc mới, tức y.

      x                    y
     / \                  / \
    a   y      ==>        x   c
       / \               / \
      T   c             a   T                        */
static ANode *xoay_trai(ANode *x)
{
    ANode *y = x->right;
    ANode *T = y->left;

    y->left  = x;
    x->right = T;

    cap_nhat_h(x);            /* x ở DƯỚI nên cập nhật TRƯỚC */
    cap_nhat_h(y);

    return y;
}

LL: chèn 10, 20, 30 theo thứ tự giảm       Sau xoay phải quanh 30
        30                                        20
       /                                         /  \
      20                                       10    30
     /
    10

RR: chèn 30, 20, 10 theo thứ tự tăng       Sau xoay trái quanh 10
    10                                            20
      \                                          /  \
       20                                      10    30
         \
          30

LR: chèn 30, 10, 20                        Xoay trái quanh 10, rồi phải quanh 30
        30              30                        20
       /               /                         /  \
      10      ==>    20         ==>            10    30
        \           /
         20       10

RL: chèn 10, 30, 20                        Xoay phải quanh 30, rồi trái quanh 10
    10              10                            20
      \               \                          /  \
       30    ==>       20        ==>            10    30
      /                  \
     20                   30

/* Khôi phục cân bằng cho nút n sau khi cây con của nó thay đổi.
   Trả về gốc mới của cây con này. */
static ANode *can_bang(ANode *n)
{
    cap_nhat_h(n);

    int b = bf(n);

    /* Lệch trái quá mức */
    if (b > 1) {
        if (bf(n->left) < 0)               /* LR: con trái lệch phải */
            n->left = xoay_trai(n->left);

        return xoay_phai(n);               /* LL, hoặc LR sau bước trên */
    }

    /* Lệch phải quá mức */
    if (b < -1) {
        if (bf(n->right) > 0)              /* RL: con phải lệch trái */
            n->right = xoay_phai(n->right);

        return xoay_trai(n);               /* RR, hoặc RL sau bước trên */
    }

    return n;                              /* đã cân bằng, không đổi gì */
}

static ANode *an_tao(int v)
{
    ANode *n = malloc(sizeof *n);

    if (n == NULL) return NULL;

    n->data   = v;
    n->height = 1;
    n->left   = NULL;
    n->right  = NULL;

    return n;
}

/* Chèn v. Trả về gốc mới của cây con.
   Đặt *loi bằng -1 nếu hết bộ nhớ, 1 nếu khóa đã có, 0 nếu chèn được. */
ANode *avl_chen(ANode *n, int v, int *loi)
{
    if (n == NULL) {
        ANode *m = an_tao(v);

        *loi = (m == NULL) ? -1 : 0;

        return m;                  /* NULL nếu thất bại, cây con vẫn rỗng */
    }

    if      (v < n->data) n->left  = avl_chen(n->left,  v, loi);
    else if (v > n->data) n->right = avl_chen(n->right, v, loi);
    else { *loi = 1; return n; }   /* đã có, không đổi gì */

    if (*loi != 0) return n;       /* thất bại hoặc trùng, không cần cân bằng */

    return can_bang(n);            /* cập nhật chiều cao và xoay nếu cần */
}

/* Trả về chiều cao thật nếu cây hợp lệ, hoặc -1 nếu không.
   Kiểm cả ba điều: chiều cao lưu đúng, hệ số cân bằng trong khoảng,
   và tính chất BST. */
static int kiem(const ANode *n, long duoi, long tren)
{
    if (n == NULL) return 0;

    if (n->data <= duoi || n->data >= tren) return -1;      /* không phải BST */

    int t = kiem(n->left,  duoi, n->data);

    if (t < 0) return -1;

    int p = kiem(n->right, n->data, tren);

    if (p < 0) return -1;

    int d = t - p;

    if (d < -1 || d > 1) return -1;                         /* mất cân bằng */

    int cao = 1 + (t > p ? t : p);

    if (cao != n->height) return -1;                        /* height lưu sai */

    return cao;
}

int avl_hop_le(const ANode *n)
{
    return kiem(n, -2147483648L - 1, 2147483647L + 1) >= 0;
}

#include <stdio.h>

#include "avl.h"

int main(void)
{
    ANode *goc = NULL;
    int    loi = 0;

    printf("chen 10, 20, 30, 40, 50, 25 theo thu tu:\n");

    int nguon[] = { 10, 20, 30, 40, 50, 25 };

    for (size_t i = 0; i < sizeof nguon / sizeof nguon[0]; ++i) {
        goc = avl_chen(goc, nguon[i], &loi);

        if (loi < 0) { avl_huy(goc); return 1; }

        printf("  sau %2d: cao %d, goc %d, hop le %d\n",
               nguon[i], avl_chieu_cao(goc), goc->data, avl_hop_le(goc));
    }

    printf("\ncay:\n");
    avl_in(goc, "", 1, 0);

    avl_huy(goc);

    return 0;
}

static ANode *nho_nhat(ANode *n)
{
    while (n->left != NULL) n = n->left;

    return n;
}

/* Xóa v. Trả về gốc mới của cây con. Không tìm thấy thì cây không đổi. */
ANode *avl_xoa(ANode *n, int v)
{
    if (n == NULL) return NULL;

    if      (v < n->data) n->left  = avl_xoa(n->left,  v);
    else if (v > n->data) n->right = avl_xoa(n->right, v);
    else {
        /* Ba trường hợp y hệt Bài 24.6 */
        if (n->left == NULL || n->right == NULL) {
            ANode *con = n->left ? n->left : n->right;

            free(n);

            if (con == NULL) return NULL;      /* không con */

            return can_bang(con);              /* một con, con đã là AVL hợp lệ */
        }

        ANode *ke = nho_nhat(n->right);

        n->data  = ke->data;
        n->right = avl_xoa(n->right, ke->data);
    }

    return can_bang(n);      /* cân bằng lại ở MỌI tầng trên đường đi ngược */
}

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

#include "avl.h"
#include "bst.h"

#define N 1000000

int main(void)
{
    /* Trường hợp xấu nhất của BST: dữ liệu đã sắp */
    printf("=== chen %d khoa TANG DAN ===\n", N);

    clock_t t0 = clock();
    ANode  *a  = NULL;
    int     loi = 0;

    for (int i = 0; i < N; ++i) {
        a = avl_chen(a, i, &loi);

        if (loi < 0) return 1;
    }

    double g_avl = (double)(clock() - t0) / CLOCKS_PER_SEC;

    printf("AVL : %.3f s, chieu cao %d\n", g_avl, avl_chieu_cao(a));
    printf("BST : bo qua, cay suy bien se tran ngan xep\n");

    /* Tìm một triệu lần */
    t0 = clock();

    long thay = 0;

    for (int i = 0; i < N; ++i)
        if (avl_tim(a, rand() % N) != NULL) ++thay;

    printf("tim %d lan tren AVL: %.3f s (thay %ld)\n",
           N, (double)(clock() - t0) / CLOCKS_PER_SEC, thay);

    avl_huy(a);

    return 0;
}